Merging optimality conditions with genetic algorithm operators to solve single machine total weighted tardiness problem

Abstract

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.

Keywords

Sequencing and scheduling theory / genetic algorithms

References

[1] Bagchi S., Uckun S., Miyabe Y., Kawamura K.. Belew R., Booker L.. Exploring problem-specific recombination operators for job shop scheduling. Proceedings of the Fourth International Conference on Genetic Algorithms, 1991, Los Altos, CA: Morgan Kaufmann Publishers 10-17.

[2] Baker K. R.. Introduction to Sequencing and Scheduling, 1974, New York: John Wiley and Sons

[3] Biegel J. E., Davern J. J.. Genetic algorithm and job shop scheduling. Computers and Industrial Engineering, 1990, 19(1–4): 81-91.

[4] 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.

[5] 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.

[6] Cleveland G., Smith S. F.. Schaffer J.. Using genetic algorithms to schedule flow shop releases. Proceedings of the Third International Conference on Genetic Algorithms, 1989, Los Altos, CA: Morgan Kaufmann Publishers 160-169.

[7] Croce F. D., Tadei R., Volta G.. A genetic algorithm for the job shop problem. Computers and Operations Research, 1995, 22(1): 15-24.

[8] Dagli C., Sittisathanchai S.. Genetic neuro-scheduler for job shop scheduling. Computers and Industrial Engineering, 1993, 25(1–4): 267-270.

[9] Davern, J. J., “An Architecture for job shop scheduling with genetic algorithms”, Ph.D. Dissertation, University of Central Florida, 1994.

[10] 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.

[11] Davis L.. Grefenstette J. J.. Job shop scheduling with genetic algorithms. Proceedings of the First International Conference on Genetic Algorithms, 1985, Hillsdale, NJ: Lawrence Erlbaum Associates 136-140.

[12] Dorndorf U., Pesch E.. Evolution based learning in a job shop scheduling environment. Computers and Operations Research, 1995, 22(1): 25-40.

[13] Emmons H.. One machine sequencing to minimize mean flow time with minimum number tardy. Naval Research Logistic Quarterly, 1975, 22(3): 585-592.

[14] 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.

[15] Gonçalve J. F., Mendes J. J. M., Resende M. G. C.. A hybrid genetic algorithm for the job shop scheduling problem. AT&T Labs Research Technical Report TD-5EAL6J, 2002, 180 Park Avenune, Florham Park, NJ 07932 USA: AT&T Labs Research

[16] Gupta M., Gupta Y., Kumar A.. Minimizing flow time variance in a single machine system using genetic algorithms. European Journal of Operational Research, 1993, 70: 289-303.

[17] Holland, J. H., Adaptation in Natural and Artificial Systems, MIT Press, 1992.

[18] Jain A.S., Meeran S.. A state-of-the-Art review of job-shop scheduling techniques. European Journal of Operations Research, 1999, 113: 390-434.

[19] Koulamas C., Antony S., Jaen R.. A survey of simulated annealing applications to operations: research problems. OMEGA: The International Journal of Management Science, 1994, 22(1): 41-56.

[20] 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.

[21] Liepins G. E., Hilliard M. R., Palmer M., Morrow M.. Grefenstette J. J.. Greedy Genetics. Proceedings of the Second International Conference on Genetic Algorithms, 1987, Hillsdale, NJ: Lawrence Erlbaum Associates 90-99.

[22] Nakano R., Yamada T.. Belew R., Booker L.. Conventional genetic algorithm for job shop problems. Proceedings of the Fourth International Conference on Genetic Algorithms, 1991, Los Altos, CA: Morgan Kaufmann Publishers 474-479.

[23] Neppalli, V. R., “Optimized genetic algorithms approach to solve flow shop scheduling problem”. Master Thesis, Mississippi State University, 1994.

[24] Norman B. A., Bean J. C.. Random keys genetic algorithm for job shop scheduling, 1994, Department of Industrial and Operations Engineering, The University of Michigan: Ann Arbor

[25] Norman B., Bean J.. Scheduling operations on parallel machine tools. IIE Transactions, 2000, 32: 449-459.

[26] Pinedo, Michael., “Scheduling theory, algorithms, and systems”, Prentice-Hall, 1995.

[27] Ponnambalam S. G., Aravindan P., Sreenivasa R. P.. Comparative evaluation of genetic algorithms for job-shop scheduling. Production Planning & Control, 2001, 12(6): 560-574.

[28] Reeves C.. A Genetic algorithm for flowshop sequencing. Computers and Operations Research, 1995, 22(1): 5-13.

[29] Rubin P., Ragatz G. L.. Scheduling in a sequence dependent setup environment with genetic search. Computers and Operations Research, 1995, 22(1): 85-99.

[30] Sridhar H., Rajendran C.. A genetic algorithm for family and job scheduling in a flowline-based manufacturing cell. Computers and Industrial Engineering, 1995, 27(1–4): 469-472.

[31] Teresa, G.D., Jorge, P, Sousa, Cunha, “A genetic algorithm for the bus driver scheduling problem”, 4th Metaheuristics International Conference., 2001

[32] Vempati V. S., Chen C., Bullington S.. An effective heuristic for flow shop problems with total flow time as criterion. Computer and Industrial Engineering, 1993, 25(1–4): 219-222.

[33] Wainwright R. L.. Introduction to genetic algorithms: theory and applications. The Seventh Oklahoma Symposium on Artificial Intelligence, 1993, Stillwater: Oklahoma State University 18-19.

[34] Whitley D., Starkweather T., Fuguay D.. Schaffer J.. Scheduling problems and traveling salesman: the genetic edge recombination operator. Proceedings of the Third International Conference on Genetic Algorithms, 1989, Los Altos, CA: Morgan Kaufmann Publishers 133-140.

[35] 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.