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

doi:10.1007/s40436-016-0140-y

Abstract

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.

Key words: Job-shop scheduling problem (JSP), Adaptive crossover, Adaptive mutation, Multi-population, Elite replacing strategy

Lei Wang, Jing-Cao Cai, Ming Li. An adaptive multi-population genetic algorithm for job-shop scheduling problem[J]. Advances in Manufacturing, 2016, 4(2): 142-149.

TrendMD

References

1. Pezzella F, Morganti G, Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 35(10):3202-3212
2. Gao L, Li X, Wen X et al (2015) A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem. Comput Ind Eng 88:417-429
3. Nasser SP, Behrooz G (2013) A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling. J Manuf Syst 32(4):771-780
4. Garey MR, Johnson DS, Sethi R (1976) The complexity of flow shop and job shop scheduling. Math Oper Res 1(2):117-129
5. Lin TL, Horng SJ, Kao TW et al (2010) An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Syst Appl 37(3):2629-2636
6. Goncalves JF, Mendes JJDM, Resende MGC (2005) A hybrid genetic algorithm for the job shop scheduling problem. Eur J Oper Res 167(1):77-95
7. Park BJ, Choi HR, Kim HS (2003) A hybrid genetic algorithm for the job shop scheduling problems. Comput Ind Eng 45(4):597-613
8. Wang L, Zheng DZ (2001) An effective hybrid optimization strategy for job shop scheduling problems. Comput Oper Res 28(6):585-596
9. Watanabe M, Ida K, Gen M (2005) A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Comput Ind Eng 48(4):743-752
10. Nowicki E, Smutnicki C (2005) An advanced tabu search algorithm for the job shop problem. J Sched 8(2):145-159
11. Ponnambalam SG, Aravindan P, Rajesh SV (2000) A tabu search algorithm for job shop scheduling. Int J Adv Manuf Technol 16(10):765-771
12. Ge HW, Sun L, Liang YC et al (2008) An effective PSO and AISbased hybrid intelligent algorithm for job-shop scheduling. IEEE Trans Syst Man Cybern (Part A) 38(2):358-368
13. Udomsakdigool A, Kachitvichyanukul V (2008) Multiple colony ant algorithm for job-shop scheduling problem. Int J Prod Res 46(15):4155-4175
14. Suresh RK, Mohanasundaram KM (2005) Pareto archived simulated annealing for job shop scheduling with multiple objectives. Int J Adv Manuf Technol 29(1):184-196
15. Li Y, Chen YA (2010) Genetic algorithm for job shop scheduling. J Softw 5(3):269-274
16. Mattfeld DC, Bierwirth C (2004) An efficient genetic algorithm for job shop scheduling with tardiness objectives. Eur J Oper Res 155(3):616-630
17. Gao L, Zhang GH, Zhang LP et al (2011) An efficient memetic algorithm for solving the job shop scheduling problem. Comput Ind Eng 60(4):699-705
18. Liu TK, Tsai T, Chou JH (2006) Improved genetic algorithm for the job-shop scheduling problem. Int J Adv Manuf Technol 27(9):1021-1029
19. Ahmadizar F, Farahani MH (2012) A novel hybrid genetic algorithm for the open shop scheduling problem. Int J Adv Manuf Technol 62(5):775-787
20. Wang L, Zheng DZ (2002) A modified genetic algorithm for job shop scheduling. Int J Adv Manuf Technol 20(1):72-76
21. Zhang CY, Li G, Rao YQ et al (2005) A new hybrid GA/SA algorithm for the job shop scheduling problem. Lect Notes Comput Sci 3448:246-259
22. Zhang CY, Rao YQ, Li PG (2008) An effective hybrid genetic algorithm for the job shop scheduling problem. Int J Adv Manuf Technol 39(9-10):965-974
23. Yusof R, Khalid M, Hui GT et al (2011) Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm. Appl Soft Comput 11(8):5782-5792
24. Ren Q, Wang Y (2012) A new hybrid genetic algorithm for job shop scheduling problem. Comput Oper Res 39(10):2291-2299
25. Lei DM, Guo XP (2015) An effective neighborhood search for scheduling in dual-resource constrained interval job shop with environmental objective. Int J Prod Econ 159:296-303
26. Kurdi M (2015) A new hybrid island model genetic algorithm for job shop scheduling problem. Comput Ind Eng 88:273-283
27. Kurdi M (2016) An effective new island model genetic algorithm for job shop scheduling problem. Comput Oper Res 67:132-142
28. Asadzadeh L, Zamanifar K (2010) An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Math Comput Modell 52(11-12):1957-1965
29. Gen M, Cheng R (1997) Genetic algorithms and engineering design. Wiley, New York
30. Srinivas M, Patnaik LM (1994) Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans Syst Man Cybern 24(4):656-667
31. Muth JF, Thompson GL (1963) Industrial scheduling. Englewood Cliffs, New Jersey
32. Croce FD, Tadei R, Volta G (1995) A genetic algorithm for the job shop problem. Comput Oper Res 22(1):15-24
33. Van PJM, Aarts EHL, Lenstra JK (1992) Job shop scheduling by simulated annealing. Oper Res 40(1):113-125
34. Dell M, Trubian M (1993) Applying tabu search to the job shop scheduling problem. Ann Oper Res 40(3):231-252