Merging optimality conditions with genetic algorithm operators to solve single machine total weighted tardiness problem
Tóm tắt
In this paper, a constrained genetic algorithm (CGA) is proposed to solve the single machine total weighted tardiness problem. The proposed CGA incorporates dominance rules for the problem under consideration into the GA operators. This incorporation should enable the proposed CGA to obtain close to optimal solutions with much less deviation and much less computational effort than the conventional GA (UGA). Several experiments were performed to compare the quality of solutions obtained by the three versions of both the CGA and the UGA with the results obtained by a dynamic programming approach. The computational results showed that the CGA was better than the UGA in both quality of solutions obtained and the CPU time needed to obtain the close to optimal solutions. The three versions of the CGA reduced the percentage deviation by 15.6%, 61.95%, and 25% respectively and obtained close to optimal solutions with 59% lower CPU time than what the three versions of the UGA demanded. The CGA performed better than the UGA in terms of quality of solutions and computational effort when the population size and the number of generations are smaller.
Tài liệu tham khảo
Bagchi, S., Uckun, S., Miyabe, Y., and Kawamura, K., “Exploring problem-specific recombination operators for job shop scheduling”, In Belew, R. and Booker, L. Editors Proceedings of the Fourth International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, pp10–17, 1991.
Baker, K. R., Introduction to Sequencing and Scheduling, New York, John Wiley and Sons, 1974.
Biegel, J. E. and Davern, J. J., “Genetic algorithm and job shop scheduling”, Computers and Industrial Engineering, Vol. 19, No. (1–4), pp 81–91, 1990.
Chen, Chuen-Lung, Vempati, V. S., and Aljaber, N., “An application of genetic algorithms for flow shop problems”, European Journal of Operational Research, No. 80, pp 389–396, 1995.
Cheng, R., Gen, M. and Tsujimura, Y., “A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies”, Computers & Industrial Engineering, No. 36, pp 343–364, 1999.
Cleveland, G. and Smith, S. F., “Using genetic algorithms to schedule flow shop releases”, In Schaffer, J. Editor Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, pp 160–169, 1989.
Croce, F. D., Tadei, R., and Volta, G., “A genetic algorithm for the job shop problem”, Computers and Operations Research, Vol. 22, No. 1, pp 15–24, 1995.
Dagli, C. and Sittisathanchai, S., “Genetic neuro-scheduler for job shop scheduling.” Computers and Industrial Engineering, Vol. 25, No. (1–4), pp 267–270, 1993.
Davern, J. J., “An Architecture for job shop scheduling with genetic algorithms”, Ph.D. Dissertation, University of Central Florida, 1994.
David, M. M., Hui-Chuan, C., Jessica, M., and Qiang, L., “A hybrid genetic algorithm for the single machine scheduling problem”, Journal of Heuristics, Vol. 5, No. 4, 1999.
Davis, L., “Job shop scheduling with genetic algorithms”, In Grefenstette, J. J. Editor, Proceedings of the First International Conference on Genetic Algorithms, Hillsdale, NJ, Lawrence Erlbaum Associates, pp 136–140, 1985.
Dorndorf, U. and Pesch, E., “Evolution based learning in a job shop scheduling environment”, Computers and Operations Research, Vol. 22, No. 1, pp 25–40, 1995.
Emmons, H., “One machine sequencing to minimize mean flow time with minimum number tardy”, Naval Research Logistic Quarterly, Vol. 22, No. 3, pp 585–592, 1975.
Falkenauer, E. and Bouffouix, S., “A genetic algorithm for job shop”. In Proceedings of the 1991 IEEE International Conference on Robotics and Automation, pp 824–829, 1991.
Gonçalve, J. F., Mendes, J. J. M., and Resende, M. G. C., “A hybrid genetic algorithm for the job shop scheduling problem”, AT&T Labs Research Technical Report TD-5EAL6J, AT&T Labs Research, 180 Park Avenune, Florham Park, NJ 07932 USA, 2002.
Gupta, M., Gupta, Y., and Kumar, A., “Minimizing flow time variance in a single machine system using genetic algorithms”, European Journal of Operational Research, Vol. 70, pp 289–303, 1993.
Holland, J. H., Adaptation in Natural and Artificial Systems, MIT Press, 1992.
Jain, A.S. and Meeran, S., “A state-of-the-Art review of job-shop scheduling techniques”, European Journal of Operations Research, Vol. 113, pp 390–434, 1999.
Koulamas, C., Antony, S., and Jaen, R., “A survey of simulated annealing applications to operations: research problems”, OMEGA: The International Journal of Management Science, Vol. 22, No. 1, pp 41–56, 1994.
Lee, C. and Herrmann, J., “Decision support systems for dynamic job shop scheduling”, In Proceeding of the 1993 NSF Design and Manufacturing Systems Conference 2, Charlotte, NC, pp 1119–1123, 1993.
Liepins, G. E., Hilliard, M. R., Palmer, M., Morrow, M., “Greedy Genetics”, In Grefenstette, J. J. Editor, Proceedings of the Second International Conference on Genetic Algorithms, Hillsdale, NJ, Lawrence Erlbaum Associates, pp 90–99, 1987.
Nakano, R. and Yamada, T., “Conventional genetic algorithm for job shop problems”, In Belew, R. and Booker, L. Editors. Proceedings of the Fourth International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, pp 474–479, 1991.
Neppalli, V. R., “Optimized genetic algorithms approach to solve flow shop scheduling problem”. Master Thesis, Mississippi State University, 1994.
Norman, B. A. and Bean, J. C., “Random keys genetic algorithm for job shop scheduling”, Technical Report 94-5, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1994.
Norman, B. and J. Bean, J., “Scheduling operations on parallel machine tools”, IIE Transactions, Vol. 32, pp 449–459, 2000.
Pinedo, Michael., “Scheduling theory, algorithms, and systems”, Prentice-Hall, 1995.
Ponnambalam, S. G., Aravindan, P., Sreenivasa, R. P., “Comparative evaluation of genetic algorithms for job-shop scheduling”, Production Planning & Control, Vol. 12, No. 6, pp 560–574, 2001.
Reeves, C., “A Genetic algorithm for flowshop sequencing”, Computers and Operations Research, Vol. 22, No. 1, pp 5–13, 1995.
Rubin, P. and Ragatz, G. L., “Scheduling in a sequence dependent setup environment with genetic search”, Computers and Operations Research, Vol. 22, No. 1, pp 85–99, 1995.
Sridhar, H. and Rajendran, C., “A genetic algorithm for family and job scheduling in a flowline-based manufacturing cell”, Computers and Industrial Engineering, Vol. 27, No. (1–4), pp 469–472, 1995.
Teresa, G.D., Jorge, P, Sousa, Cunha, “A genetic algorithm for the bus driver scheduling problem”, 4th Metaheuristics International Conference., 2001
Vempati, V. S., Chen, C., and Bullington, S., “An effective heuristic for flow shop problems with total flow time as criterion”, Computer and Industrial Engineering, Vol. 25, No. (1–4), pp 219–222, 1993.
Wainwright, R. L., “Introduction to genetic algorithms: theory and applications”, Tutorial Session, In The Seventh Oklahoma Symposium on Artificial Intelligence, Oklahoma State University, Stillwater, November, pp 18–19, 1993.
Whitley, D., Starkweather, T., and Fuguay D., “Scheduling problems and traveling salesman: the genetic edge recombination operator”, In Schaffer, J. Editor Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, pp 133–140, 1989.
Yajie Tian, Nobuo, S., Changzheng, X. Tetsuo, S., “A combined algorithm for solving job shop scheduling problems”, Preprints of IFAC 15th Triennial World Congress, 2002.