Scientific Research

An Academic Publisher

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

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.

Share and Cite:

T. 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.Conflicts of Interest

The authors declare no conflicts of interest.

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

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.