×

An effective new island model genetic algorithm for job shop scheduling problem. (English) Zbl 1349.90367

Summary: This paper presents an effective new island model genetic algorithm to solve the well-known job shop scheduling problem with the objective of minimizing the makespan. To improve the effectiveness of the classical island model genetic algorithm, we have proposed a new naturally inspired evolution model and a new naturally inspired migration selection mechanism that are capable of improving the search diversification and delaying the premature convergence. In the proposed evolution model, islands employ different evolution methods during their self-adaptation phases, rather than employing the same methods. In the proposed migration selection mechanism, worst individuals who are least adapted to their environments migrate first, hoping in finding a better chance to live in a more suitable environment that imposes a more suitable self-adaptation method on them. The proposed algorithm is tested on 52 benchmark instances, with the proposed evolution model and migration selection mechanism, and without them using the classical alternatives, and also compared with other algorithms recently reported in the literature. Computational results verify the improvements achieved by the proposed evolution model and migration selection mechanism, and show the superiority of the proposed algorithm over the others in terms of effectiveness.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Manag Sci, 34, 3, 391-401 (1988) · Zbl 0637.90051
[2] Applegate, D.; Cook, W., A computational study of the job shop scheduling problem, ORSA J Comput, 3, 2, 149-156 (1991) · Zbl 0755.90039
[3] Asadzadeh, L.; Zamanifar, K., An agent-based parallel approach for the job shop scheduling problem, Math Comput Model, 52, 11-12, 1957-1965 (2010) · Zbl 1207.90051
[4] Blackstone, J. H.; Phillips, D. T.; Hogg, G. L., A state-of-the-art survey of dispatching rules for manufacturing job shop operations, Int J Prod Res, 20, 1, 27-45 (1982)
[5] Blum, C.; Sampels, M., An ant colony optimization algorithm for shop scheduling problems, J Math Model Algorithms, 3, 3, 285-308 (2004) · Zbl 1146.90405
[6] Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Manag Sci, 35, 2, 164-176 (1989) · Zbl 0677.90036
[7] Cheng, R.; Gen, M.; Tsujimura, Y., A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation, Comput Ind Eng, 30, 4, 983-997 (1996)
[8] Darwin, C., On the origins of species by means of natural selection (1859), Murray: Murray London
[10] Della Croce, F.; Tadei, R.; Volta, G., A genetic algorithm for the job shop problem, Comput Oper Res, 22, 1, 15-24 (1995) · Zbl 0816.90081
[11] Engelbrecht, A. P., Computational intelligence: an introduction (2007), John Wiley & Sons: John Wiley & Sons West Sussex, England
[12] Fisher, H.; Thompson, G. L., Probabilistic learning combinations of local job-shop scheduling rules, (Muth, J.; Thompson, G., Industrial scheduling (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ), 225-251
[13] Gen, M.; Cheng, R., Genetic algorithms and engineering design (1997), John Wiley & Sons: John Wiley & Sons New York
[14] Goldberg, D., Genetic algorithms in search, optimization and machine learning (1989), Addison-Wesley: Addison-Wesley MA · Zbl 0721.68056
[15] Graham, R. L.; Lawler, E.; Lenstra, J.; Kan, A., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann Discret Math, 5, 287-326 (1979) · Zbl 0411.90044
[16] Gu, J.; Gu, X.; Gu, M., A novel parallel quantum genetic algorithm for stochastic job shop scheduling, J Math Anal Appl, 355, 1, 63-81 (2009) · Zbl 1174.90006
[17] Hertz, A.; Kobler, D., A framework for the description of evolutionary algorithms, Eur J Oper Res, 126, 1, 1-12 (2000) · Zbl 0970.90122
[18] Jain, A. S.; Meeran, S., Deterministic job-shop scheduling: past, present and future, Eur J Oper Res, 113, 2, 390-434 (1999) · Zbl 0938.90028
[20] Lageweg, B. J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Job-Shop scheduling by implicit enumeration, Manag Sci, 24, 4, 441-450 (1977) · Zbl 0373.90034
[21] Lawrence, S., Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement) (1984), Graduate School of Industrial Administration, Carnegie-Mellon University: Graduate School of Industrial Administration, Carnegie-Mellon University Pittsburgh, Pennsylvania
[22] Lian, Z.; Jiao, B.; Gu, X., A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan, Appl Math Comput, 183, 2, 1008-1017 (2006) · Zbl 1112.90029
[23] Lin, T. L.; Horng, S. J.; Kao, T. W.; Chen, Y. H.; Run, R. S.; Chen, R. J.; Kuo, I. H., An efficient job-shop scheduling algorithm based on particle swarm optimization, Expert Syst Appl, 37, 3, 2629-2636 (2010)
[24] Man, K. F.; Tang, K. S.; Kwong, S., Genetic algorithms: concepts and designs (1999), Springer: Springer London · Zbl 0926.68113
[25] Moraglio, A.; Ten Eikelder, H.; Tadei, R., Genetic local search for job shop scheduling problem (2005), University of Essex: University of Essex UK, Technical report CSM-435
[26] Nowicki, E.; Smutnicki, C., A fast taboo search algorithm for the job shop problem, Manag Sci, 42, 6, 797-813 (1996) · Zbl 0880.90079
[27] Ponnambalam, S. G.; Aravindan, P.; Rao, P. S., Comparative evaluation of genetic algorithms for job-shop scheduling, Prod Plan Control: Manag Oper, 12, 6, 560-574 (2001)
[28] Qi, J. G.; Burns, G. R.; Harrison, D. K., The application of parallel multipopulation genetic algorithms to dynamic job-shop scheduling, Int J Adv Manuf Technol, 16, 8, 609-615 (2000)
[29] Qing-dao-er-ji, R.; Wang, Y., A new hybrid genetic algorithm for job shop scheduling problem, Comput Oper Res, 39, 10, 2291-2299 (2012) · Zbl 1251.90178
[30] Satake, T.; Morikawa, K.; Takahashi, K.; Nakamura, N., Simulated annealing approach for minimizing the makespan of the general job-shop, Int J Prod Econ, 60-61, 515-522 (1999)
[31] Seo, M.; Kim, D., Ant colony optimisation with parameterised search space for the job shop scheduling proble, Int J Prod Res, 48, 4, 1143-1154 (2010) · Zbl 1197.90228
[32] Udomsakdigool, A.; Kachitvichyanukul, V., Multiple colony ant algorithm for job-shop scheduling problem, Int J Prod Res, 46, 15, 4155-4175 (2008) · Zbl 1153.90439
[33] Van Laarhoven, P. J.; Aarts, E. H.; Lenstra, J. K., Job shop scheduling by simulated annealing, Oper Res, 40, 1, 113-125 (1992) · Zbl 0751.90039
[34] Wang, L.; Zheng, D., An effective hybrid optimization strategy for job-shop scheduling problems, Comput Oper Res, 28, 6, 585-596 (2001) · Zbl 1017.90048
[35] Watanabe, M.; Ida, K.; Gen, M., A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem, Comput Ind Eng, 48, 4, 743-752 (2005)
[37] Yen, G. G.; Ivers, B., Job shop scheduling optimization through multiple independent particle swarms, Int J Intell Comput Cybern, 2, 1, 5-33 (2009) · Zbl 1183.68118
[38] Yusof, R.; Khalid, M.; Hui, G. T.; Md Yusof, S.; Othman, M. F., Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm, Appl Soft Comput, 11, 8, 5782-5792 (2011)
[39] Zhang, C.; Li, P.; Guan, Z.; Rao, Y., A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, Comput Oper Res, 34, 11, 3229-3242 (2007) · Zbl 1123.90041
[40] Zobolas, G.; Tarantilis, C.; Ioannou, G., Exact, heuristic and meta-heuristic algorithms for solving job shop scheduling problems, (Xhafa, F.; Abraham, A., Metaheuristics for scheduling in industrial and manufacturing applications (2008), Springer: Springer Berlin), 1-40 · Zbl 1151.90599
[41] Kurdi, M., A new hybrid island model genetic algorithm for job shop scheduling problem, Comput Ind Eng, 88, 273-283 (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.