An Effective Hybrid Genetic Algorithm for Job Shop Scheduling Problem

Authors: Bin Cai, Shilong Wang, Haibo Hu

Abstract:

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.

Keywords: Genetic algorithm, Job shop scheduling problem, Local search, Meta-heuristic algorithm

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333580

References:

[1] T. Yamada and R. Nakano, "A genetic algorithm applicable to large-scale job-shop problems," in Proc. PPSN, Amsterdam, 1992, pp. 283-292.
[2] C. Bierwirth, "A generalized permutation approach for job shop scheduling with genetic algorithms," OR Spektrum. Vol. 17, Issue 2-3, pp. 87-92. 1995.
[3] 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.
[4] S. Kobayashi, I. Ono, and M. Yamamura, "An efficient genetic algorithm for job shop scheduling problems," in Proc. ICGA, 1995, pp.506-511.
[5] 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.
[6] E. Nowicki, C. Smutnicki C, "A fast taboo search algorithm for the job shop problem," Management Science, Vol. 42, pp.797-813, 1996.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] B. M. Ombuki and M. Ventresca. "Local search genetic algorithms for the job shop scheduling problem," Appl. Intell., vol. 21, pp.99-109, 2004.
[13] 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.
[14] 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.
[15] M. Pinedo, "Scheduling theory, algorithms, and system," 2nd ed. Prentice Hall, Upper Saddle River, New Jersey, 2002, pp. 21-25.
[16] 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.
[17] 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.
[18] J. E. Beasley, “OR-Library: Distributing test problems by electronic mail,” J. Oper. Res. Soc., vol. 41, no. 11, pp. 1069–1072, 1990.
[19] 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.
[20] I. Sabuncuoglu and M. Bayiz, “Job shop scheduling with beam search,” Eur. J. Oper. Res., vol. 118, no. 2, pp. 390–412, Oct. 1999.
[21] 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.
[22] J. Adams, E. Balas, D. Zawack, “The shifting bottleneck procedure for job shop scheduling,” Manag Sci, Vol.34, pp391-401, 1988.