Research ArticleOpen AccessGoogle Scholar indexed
Representations in Genetic Algorithm for the Job Shop Scheduling Problem: A Computational Study
- 1
Journal of Software Engineering and Applications·Volume 03 (2010)·Pages 1155–1162·Published 31 December 2010·DOI10.4236/jsea.2010.312135
Copy link · social · email
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.
KeywordsJob Shop SchedulingGenetic AlgorithmMathematical ModelsGenetic Representation
- J. Holland, “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, 1975.
- D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison-Wesley, New York, 1989.
- M. Gen and R. Cheng, “Genetic Algorithms and Engineering Design,” Wiley, New York, 1997.
- M. Pinedo, “Scheduling-Theory, Algorithms, and Analysis,” Prentice-Hall, New Jersey, 2002.
- 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
- 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
- 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
- E. J. Anderson, C. A. Glass and C. N. Potts, “Local Search in Combinatorial Optimization,” Princeton University Press, Princeton, 2003.
- B. Roy and B. Sussmann, “Les Problemes d’ Ordonnancement Avec Constraints Disjonctives,” SEMA, Note D.S., Paris, 1964.
- 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
- 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
- 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
- H. Bowman, “The Schedule-Sequencing Problem,” Operations Research, Vol. 7, No. 5, 1959, pp. 621-624. doi: 10.1287/opre.7.5.621
- 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
- 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