An Effective Hybrid Genetic Algorithm for Job Shop Scheduling Problem
The job shop scheduling problem (JSSP) is well known as one of the most difficult combinatorial optimization problems. This paper presents a hybrid genetic algorithm for the JSSP with the objective of minimizing makespan. The efficiency of the genetic algorithm is enhanced by integrating it with a local search method. The chromosome representation of the problem is based on operations. Schedules are constructed using a procedure that generates full active schedules. In each generation, a local search heuristic based on Nowicki and Smutnicki-s neighborhood is applied to improve the solutions. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333580Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1233
 T. Yamada and R. Nakano, "A genetic algorithm applicable to large-scale job-shop problems," in Proc. PPSN, Amsterdam, 1992, pp. 283-292.
 C. Bierwirth, "A generalized permutation approach for job shop scheduling with genetic algorithms," OR Spektrum. Vol. 17, Issue 2-3, pp. 87-92. 1995.
 F. D. Croce, R. Tadei, and G. Volta, "A genetic algorithm for the job shop problem," Comput Oper Res, vol. 22, pp. 15-24, 1995.
 S. Kobayashi, I. Ono, and M. Yamamura, "An efficient genetic algorithm for job shop scheduling problems," in Proc. ICGA, 1995, pp.506-511.
 P. J. M. van Laarhoven, E. H. L. Aarts, and J. K. Lenstra, "Job shop scheduling by simulated annealing," Operations Res., vol. 40, pp.113-125, 1992.
 E. Nowicki, C. Smutnicki C, "A fast taboo search algorithm for the job shop problem," Management Science, Vol. 42, pp.797-813, 1996.
 S. Binato, W. J. Hery, D. M. Loewenstern, and M. G. C. Resende, "A GRASP for job shop scheduling," in Essays and Surveys in Metaheuristics. Boston, MA: Kluwer, 2001, pp. 59-80.
 A. S. Jain and S. Meeran "Deterministic job-shop scheduling: past, present and future," European Journal of Operational Research, vol. 113, pp.390-434, 1999.
 R. Cheng, M. Gen and Y. Tsujimura, "A tutorial survey of job-shop scheduling problems using genetic algorithms-I. representation," Comput Ind Eng, Vol. 30, No. 4, pp. 983-997, 1996.
 R. Cheng, M. Gen and Y. Tsujimura, "A tutorial survey of job-shop scheduling problems using genetic algorithms - Part II: hybrid genetic search strategies," Comput Ind Eng, vol. 36, no. 2, pp. 343-364, 1999.
 L. Wang and D. Z. Zheng. "A modified genetic algorithm for job shop scheduling," Int. J. Adv. Manuf. Technol., vol. 20, pp.72-76, 2002.
 B. M. Ombuki and M. Ventresca. "Local search genetic algorithms for the job shop scheduling problem," Appl. Intell., vol. 21, pp.99-109, 2004.
 J. F. Goncalves , J. J. D. M. Mendes and M. G. C. Resende. "A hybrid genetic algorithm for the job shop scheduling problem," Eur. J. Oper. Res., Vol. 167, p77-95, 2005.
 K. Premalatha. and A.M. Natarajan. "Hybrid PSO and GA for global maximization," Int J Open Probl Comput Sci Math, Vol. 2, No. 4. pp. 597-608, 2010.
 M. Pinedo, "Scheduling theory, algorithms, and system," 2nd ed. Prentice Hall, Upper Saddle River, New Jersey, 2002, pp. 21-25.
 C.Y. Zhang, Y.Q. Rao and P.G Li, “An effective hybrid genetic algorithm for the job shop scheduling problem,” Int J Adv Manuf Technol, Vol.39, pp965-974, 2008.
 G. Shi, “A genetic algorithm applied to a classic job-shop scheduling problem,” Int J Syst Sci, vol. 28, no. 1, pp. 25-32, 1997.
 J. E. Beasley, “OR-Library: Distributing test problems by electronic mail,” J. Oper. Res. Soc., vol. 41, no. 11, pp. 1069–1072, 1990.
 R. M. Aiex, S. Binato, and M. G. C. Resende, “Parallel GRASP with path-relinking for job shop scheduling,” Parallel Comput., vol. 29, no. 4, pp. 393–430, Apr. 2003.
 I. Sabuncuoglu and M. Bayiz, “Job shop scheduling with beam search,” Eur. J. Oper. Res., vol. 118, no. 2, pp. 390–412, Oct. 1999.
 W. P. W. Nuijten and E. H. L. Aarts, “Computational study of constraint satisfaction for multiple capacitated job shop scheduling,” Eur. J. Oper. Res., vol. 90, no. 2, pp. 269–284, Apr. 1996.
 J. Adams, E. Balas, D. Zawack, “The shifting bottleneck procedure for job shop scheduling,” Manag Sci, Vol.34, pp391-401, 1988.