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

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.

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.

Cite this paper

nullT. Abdelmaguid, "Representations in Genetic Algorithm for the Job Shop Scheduling Problem: A Computational Study,"*Journal of Software Engineering and Applications*, Vol. 3 No. 12, 2010, pp. 1155-1162. doi: 10.4236/jsea.2010.312135.

nullT. Abdelmaguid, "Representations in Genetic Algorithm for the Job Shop Scheduling Problem: A Computational Study,"

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.

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