Representations in Genetic Algorithm for the Job Shop Scheduling Problem: A Computational Study

Tamer F. Abdelmaguid

.

DOI: 10.4236/jsea.2010.312135                

Abstract

Due to the NP-hardness of the job shop scheduling problem (JSP), many heuristic approaches have been proposed; among them is the genetic algorithm (GA). In the literature, there are eight different GA representations for the JSP; each one aims to provide subtle environment through which the GA’s reproduction and mutation operators would succeed in finding near optimal solutions in small computational time. This paper provides a computational study to compare the performance of the GA under six different representations.

Keywords

Job Shop Scheduling, Genetic Algorithm, Mathematical Models, Genetic Representation

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. Holland, “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, 1975.
[2]	D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison-Wesley, New York, 1989.
[3]	M. Gen and R. Cheng, “Genetic Algorithms and Engineering Design,” Wiley, New York, 1997.
[4]	M. Pinedo, “Scheduling-Theory, Algorithms, and Analysis,” Prentice-Hall, New Jersey, 2002.
[5]	M. R. Garey, D. S. Johnson and R. Sethi, “The Complexity of Flow Shop and Job-Shop Scheduling,” Mathematics of Operations Research, Vol. 1, No. 2, 1976, pp. 117-129. doi:10.1287/moor.1.2.117
[6]	Y. N. Sotskov and N. V. Shakhlevich, “NP-Hardness of Shop Scheduling Problems with Three Jobs,” Discrete Applied Mathematics, Vol. 59, No. 3, 1995, pp. 237-266. doi:10.1016/0166-218X(93)E0169-Y
[7]	R. Cheng, M. Gen and Y. Tsujimura, “A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms-I. Representation,” Computers and Industrial Engineering, Vol. 30, No. 4, 1996, pp. 983-997. doi:10.1016 /0360-8352(96)00047-2
[8]	E. J. Anderson, C. A. Glass and C. N. Potts, “Local Search in Combinatorial Optimization,” Princeton University Press, Princeton, 2003.
[9]	B. Roy and B. Sussmann, “Les Problemes d’ Ordonnancement Avec Constraints Disjonctives,” SEMA, Note D.S., Paris, 1964.
[10]	T. F. Abdelmaguid, “Permutation-Induced Acyclic Networks for the Job Shop Scheduling Problem,” Applied Mathematical Modeling, Vol. 33, No. 3, 2009, pp. 1560-1572. doi:10.1016/j.apm.2008.02.004
[11]	J. Carlier and E. Pinson, “An Algorithm for Solving the Job-Shop Problem,” Management Science, Vol. 35, No. 2, 1989, pp. 164-176. doi:10.1287/mnsc.35.2.164
[12]	J. Adams, E. Balas and D. Zawack, “The Shifting Bottleneck Procedure for Job Shop Scheduling,” Management Science, Vol. 34, No. 3, 1988, pp. 391-401. doi:10.128 7/mnsc.34.3.391
[13]	H. Bowman, “The Schedule-Sequencing Problem,” Operations Research, Vol. 7, No. 5, 1959, pp. 621-624. doi: 10.1287/opre.7.5.621
[14]	H. M. Wagner, “An Integer Linear-Programming Model for Machine Scheduling,” Naval Research Logistics Quarterly, Vol. 6, No. 2, 1959, pp. 131-140. doi:10.1002 /nav.3800060205
[15]	A. S. Manne, “On the Job-Shop Scheduling Problem,” Operations Research, Vol. 8, No. 2, 1960, pp. 219-223. doi:10.1287/opre.8.2.219
[16]	H. Tamaki and Y. Nishikawa, “A Paralleled Genetic Algorithm Based on a Neighborhood Model and its Application to the Jobshop Scheduling,” Proceedings Of the 2nd International Conference on Parallel Problem Solving from Nature, Amsterdam, 28-30 September 1992, pp. 579-588.
[17]	M. Gen, Y. Tsujimura and E. Kubota, “Solving Job-Shop Scheduling Problems by Genetic Algorithm,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, San Antonio, 2-5 October 1994, pp. 1577-1582.
[18]	J. Bean, “Genetic Algorithms and Random Keys for Sequencing and Optimization,” ORSA Journal of Computing, Vol. 6, No. 2, 1994, pp. 154-160.
[19]	L. Davis, “Job Shop Scheduling with Genetic Algorithm,” Proceedings Of the 1st International Conference on Genetic Algorithms, Pittsburgh, 24-26 July 1985, pp. 136-140.
[20]	F. D. Groce, R. Tadei and G. Volta, “A Genetic Algorithm for the Job Shop Problem,” Computers and Operations Research, Vol. 22, No. 1, 1995, pp. 15-24. doi:10. 1016/0305-0548(93)E0015-L
[21]	T. Yamada and R. Nakano, “A Genetic Algorithm Applicable to Large-Scale Job-Shop Problems,” Proceedings of the 2nd International Conference on Parallel Problem Solving from Nature, Amsterdam, 28-30 September 1992, pp. 283-292.
[22]	U. Dorndorf and E. Pesch, “Evolution Based Learning in a Job Shop Scheduling Environment,” Computers and Operations Research, Vol. 22, No. 1, 1995, pp. 25-40. doi:10.1016/0305-0548(93)E0016-M
[23]	B. Giffler and G. L. Thompson, “Algorithms for Solving Production Scheduling Problems,” Operations Research, Vol. 8, No. 4, 1960, pp. 487-503.
[24]	C. W. Holsapple, V. S. Jacob, R. Pakath and J. S. Zaveri, “Genetics-Based Hybrid Scheduler for Generating Static Schedules in Flexible Manufacturing Contexts,” IEEE Trans. Systems, Man, and Cybernetics, Vol. 23, No. 4, 1993, pp. 953-971. doi:10.1109/21.247881
[25]	D. Goldberg and R. Lingle, “Alleles, Loci and the Traveling Salesman Problem,” Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications, Los Angeles, 1985, pp. 154-159.
[26]	L. Davis, “Applying Adaptive Algorithms to Epistatic Domains,” Proceedings of the 9th International Joint Conference on Artificial Intelligence, 1985, pp. 162-164.
[27]	G. Syswerda, “Uniform Crossover in Genetic Algorithms,” Proceedings of the 3rd International Conference on Genetic Algorithms, San Mateo, 1989, pp. 2-9.
[28]	J. E. Beasley, “Job Shop Scheduling,” 2008. http://people. brunel. ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html.