An adaptive multi-population genetic algorithm for job-shop scheduling problem

Abstract

Job-shop scheduling problem (JSP) is a typical NP-hard combinatorial optimization problem and has a broad background for engineering application. Nowadays, the effective approach for JSP is a hot topic in related research area of manufacturing system. However, some JSPs, even for moderate size instances, are very difficult to find an optimal solution within a reasonable time because of the process constraints and the complex large solution space. In this paper, an adaptive multi-population genetic algorithm (AMGA) has been proposed to solve this problem. Firstly, using multi-populations and adaptive crossover probability can enlarge search scope and improve search performance. Secondly, using adaptive mutation probability and elite replacing mechanism can accelerate convergence speed. The approach is tested for some classical benchmark JSPs taken from the literature and compared with some other approaches. The computational results show that the proposed AMGA can produce optimal or near-optimal values on almost all tested benchmark instances. Therefore, we can believe that AMGA can be considered as an effective method for solving JSP.

Keywords

Job-shop scheduling problem (JSP) / Adaptive crossover / Adaptive mutation / Multi-population / Elite replacing strategy

References

[1] Pezzella F, Morganti G, Ciaschetti G. A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res, 2008, 35(10): 3202-3212.

[2] Gao L, Li X, Wen X, et al. A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem. Comput Ind Eng, 2015, 88: 417-429.

[3] Nasser SP, Behrooz G. A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling. J Manuf Syst, 2013, 32(4): 771-780.

[4] Garey MR, Johnson DS, Sethi R. The complexity of flow shop and job shop scheduling. Math Oper Res, 1976, 1(2): 117-129.

[5] Lin TL, Horng SJ, Kao TW, et al. An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Syst Appl, 2010, 37(3): 2629-2636.

[6] Goncalves JF, Mendes JJDM, Resende MGC. A hybrid genetic algorithm for the job shop scheduling problem. Eur J Oper Res, 2005, 167(1): 77-95.

[7] Park BJ, Choi HR, Kim HS. A hybrid genetic algorithm for the job shop scheduling problems. Comput Ind Eng, 2003, 45(4): 597-613.

[8] Wang L, Zheng DZ. An effective hybrid optimization strategy for job shop scheduling problems. Comput Oper Res, 2001, 28(6): 585-596.

[9] 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, 2005, 48(4): 743-752.

[10] Nowicki E, Smutnicki C. An advanced tabu search algorithm for the job shop problem. J Sched, 2005, 8(2): 145-159.

[11] Ponnambalam SG, Aravindan P, Rajesh SV. A tabu search algorithm for job shop scheduling. Int J Adv Manuf Technol, 2000, 16(10): 765-771.

[12] Ge HW, Sun L, Liang YC et al (2008) An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling. IEEE Trans Syst Man Cybern (Part A) 38(2):358–368

[13] Udomsakdigool A, Kachitvichyanukul V. Multiple colony ant algorithm for job-shop scheduling problem. Int J Prod Res, 2008, 46(15): 4155-4175.

[14] Suresh RK, Mohanasundaram KM. Pareto archived simulated annealing for job shop scheduling with multiple objectives. Int J Adv Manuf Technol, 2005, 29(1): 184-196.

[15] Li Y, Chen YA. Genetic algorithm for job shop scheduling. J Softw, 2010, 5(3): 269-274.

[16] Mattfeld DC, Bierwirth C. An efficient genetic algorithm for job shop scheduling with tardiness objectives. Eur J Oper Res, 2004, 155(3): 616-630.

[17] Gao L, Zhang GH, Zhang LP, et al. An efficient memetic algorithm for solving the job shop scheduling problem. Comput Ind Eng, 2011, 60(4): 699-705.

[18] Liu TK, Tsai T, Chou JH. Improved genetic algorithm for the job-shop scheduling problem. Int J Adv Manuf Technol, 2006, 27(9): 1021-1029.

[19] Ahmadizar F, Farahani MH. A novel hybrid genetic algorithm for the open shop scheduling problem. Int J Adv Manuf Technol, 2012, 62(5): 775-787.

[20] Wang L, Zheng DZ. A modified genetic algorithm for job shop scheduling. Int J Adv Manuf Technol, 2002, 20(1): 72-76.

[21] Zhang CY, Li G, Rao YQ, et al. A new hybrid GA/SA algorithm for the job shop scheduling problem. Lect Notes Comput Sci, 2005, 3448: 246-259.

[22] Zhang CY, Rao YQ, Li PG. An effective hybrid genetic algorithm for the job shop scheduling problem. Int J Adv Manuf Technol, 2008, 39(9–10): 965-974.

[23] Yusof R, Khalid M, Hui GT, et al. Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm. Appl Soft Comput, 2011, 11(8): 5782-5792.

[24] Ren Q, Wang Y. A new hybrid genetic algorithm for job shop scheduling problem. Comput Oper Res, 2012, 39(10): 2291-2299.

[25] Lei DM, Guo XP. An effective neighborhood search for scheduling in dual-resource constrained interval job shop with environmental objective. Int J Prod Econ, 2015, 159: 296-303.

[26] Kurdi M. A new hybrid island model genetic algorithm for job shop scheduling problem. Comput Ind Eng, 2015, 88: 273-283.

[27] Kurdi M. An effective new island model genetic algorithm for job shop scheduling problem. Comput Oper Res, 2016, 67: 132-142.

[28] Asadzadeh L, Zamanifar K. An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Math Comput Modell, 2010, 52(11–12): 1957-1965.

[29] Gen M, Cheng R. Genetic algorithms and engineering design, 1997, New York: Wiley

[30] Srinivas M, Patnaik LM. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans Syst Man Cybern, 1994, 24(4): 656-667.

[31] Muth JF, Thompson GL. Industrial scheduling, 1963, New Jersey: Englewood Cliffs

[32] Croce FD, Tadei R, Volta G. A genetic algorithm for the job shop problem. Comput Oper Res, 1995, 22(1): 15-24.

[33] Van PJM, Aarts EHL, Lenstra JK. Job shop scheduling by simulated annealing. Oper Res, 1992, 40(1): 113-125.

[34] Dell M, Trubian M. Applying tabu search to the job shop scheduling problem. Ann Oper Res, 1993, 40(3): 231-252.

Funding

National Natural Science Foundation of China http://dx.doi.org/10.13039/501100001809(Grant No. 51305001)