A New Hybrid Scatter Search Algorithm for Solving the Flexible Job Shop Scheduling Problems

Abstract

Flexible job shop scheduling (FJSS) is derived by inheriting the features of the job-shop scheduling problem. FJSS has an extra routing sub-problem of the job-shop scheduling. FJSS is well known as an NP-hard problem in the literature. A new hybrid scatter search (HSS) method is proposed to solve the FJSS problem. The proposed HSS method is integrating a local and global search for generating an initial population. The performance of the proposed new HSS method is dependent on the selected parameters. These parameters are the size of the initial population and reference set; the number of subsets, reference set updating and population sub updating; reproduction, crossover, and mutation operators, and their ratio. A full factorial experimental design is made to determine the best values of control parameters and operators for the proposed new HSS to solve the FJSS problems. The proposed new HSS method is tested on a set of the well-known benchmark FJSS instances from the literature. The computational results indicated that the proposed new HSS is an effective method for solving the FJSS problems.

Keywords

• Flexible job shop scheduling problem
• Full factorial experimental design
• Hybrid scatter search method
• Makespan

References

1. References 1. Zhang, G, Gao, L, Shi, Y. 2011. An effective genetic algorithm for the flexible job-shop scheduling problem. Expert System with Application; (38): 3563-3573.
2. 2. Yazdani, M, Amiri, M, Zandieh, M. 2010. Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert System with Application; (37): 678-687.
3. 3. Rossi, R, Tarim, SA, Hnich, B, Prestwic, S, Karacaer, S. 2010. Scheduling internal audit activities: a stochastic combinatorial optimization problem. Journal of combinatorial optimization; (19): 325- 346.
4. 4. Karimi, H, Rahmati, SHA, Zandieh, M. 2012. An efficient knowledge-based algorithm for the flexible job shop scheduling problem. Knowledge-Based System; (36): 236-244.
5. 5. Hwang, S, Cheng, ST. 2001. Combinatorial optimization in real-time scheduling: Theory and Algorithms. Journal of combinatorial optimization; (5): 345- 375.
6. 6. Brucker, P, Schlie, R. 1990. Job-shop scheduling with multi-purpose machines. Computing; (45): 369-375.
7. 7. Kacem, I, Hammadi S, Borne P. 2002. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics; (32): 1-13.
8. 8. Tay, J, Wibowo, D. 2004. An Effective Chromosome Representation for Evolving Flexible Job Shop Schedules. In: Genetic and Evolutionary Computation GECCO - Eds: Deb K: Springer Berlin Heidelberg, 210-221.

9. 9. Ong, Z, Tay, J, Kwoh, C. 2005. Applying the Clonal Selection Principle to Find Flexible Job-Shop Schedules, Artificial Immune Systems. Eds: Jacob C, Pilat M, Bentley P, Timmis J: Springer Berlin Heidelberg, 442-455.
10. 10. Ho, N, Tay, J, Lai, E. 2007. An effective architecture for learning and evolving flexible job-shop schedules. European Journal of Operational Research; (179): 316-333.
11. 11. Gao, J, Sun, L, Gen, M. 2008. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computer Operation Research; (35): 2892-2907.
12. 12. Fattahi, P, Mehrabad, MS, Jolai, F. 2007. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing; (18): 331-342.
13. 13. Gholami, M, Zandieh, M. 2008. Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop. Journal of Intelligent Manufacturing; (20): 481-498.
14. 14. Xing, L, Chen, YW, Zhao, Q, Xiong, J. 2009. A knowledge-based ant colony optimization for flexible job shop scheduling problems. Applied Soft Computing; (10): 888-896.
15. 15. Zhang, G, Shao, X, Li, P, Gao, L. 2009. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering; (56): 1309-1318.
16. 16. Bagheri, A, Zandieh, M, Mahdavi, I, Yazdani, M. 2010. An artificial immune algorithm for the flexible job-shop scheduling problem. Future Generation Computer Systems; (26): 533-541.
17. 17. Guohui, Z, Liang, G, Yang, S. 2010. Genetic algorithm and tabu search for multi objective flexible job shop scheduling problems. International Conference on Computing, Control, and Industrial Engineering (CCIE); 251-254.
18. 18. Wang, S, Yu, J. 2010. An effective heuristic for flexible job-shop scheduling problem with maintenance activities. Computers & Industrial Engineering; (59): 436-447.
19. 19. Birgin, EG, Feofiloff, P, Fernandes, CG, EL. de Melo, Oshiro MTI, Ronconi DP. 2013. A MILP model for an extended version of the Flexible Job Shop Problem. Optimization Letters; (8): 1417-1431.
20. 20. Demir, Y, İşleyen, SK. 2013. Evaluation of mathematical models for flexible job-shop scheduling problems. Applied Mathematical Modelling; (37): 977-988.
21. 21. Yuan, Y, Xu, H. 2013. Flexible job shop scheduling using hybrid differential evolution algorithms. Computers & Industrial Engineering; (65): 246-260.
22. 22. Demir, Y, İşleyen SK. 2014. An effective genetic algorithm for flexible job-shop scheduling with overlapping in operations. International Journal of Production Research; (52): 3905-3921.
23. 23. Abdelmaguid, TF. 2015. A neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times. Applied Mathematical Computing; (260): 188-203.
24. 24. Gao, KZ, Suganthan, PN, Chua, TJ, Chong, CS, Cai, TX, Pan, QK. 2015. A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion. Expert System Applied; (42): 7652-7663.
25. 25. González, MA, Vela, CR, Varela, R. 2015. Scatter search with path relinking for the flexible job shop scheduling problem. European Journal Operation Research; (245): 35-45.
26. 26. Ishikawa, S, Kubota, R, Horio, K. 2015. Effective hierarchical optimization by a hierarchical multi-space competitive genetic algorithm for the flexible job-shop scheduling problem. Expert System with Application; (42): 9434-9440. 27. Singh, MR, Mahapatra, SS. 2016. A quantum behaved particle swarm optimization for flexible job shop scheduling. Computers & Industrial Engineering; (93): 36-44.
27. 28. Zabihzadeh, SS, Rezaeian, J. 2016. Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time. Applied Soft Computing; (40): 319-330. 29. Li, X, Peng, Z, Du, B, Guo, J, Xu, W, Zhuang. 2017. Hybrid artificial bee colony algorithm with a rescheduling strategy for solving flexible job shop scheduling problems. Computers and Industrial Engineering; (113): 10- 26.
28. 30. Shen, L, Dauzère-Pérès, S, Neufeld, JS. 2018. Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research; (265): 503-516.
29. 31. Min, D, Dunbing, T, Adriana, G, Salido, MA. 2019. Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints. Robotics-Integrated Manufacturing; (59): 143-157.
30. 32. Li, JQ, Deng, JW, Li, CY, Han, YY, Tian, J, Zhang, B, Wang, CG. 2020. An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times. Knowledge-Based Systems; (200): 106032.
31. 33. Özgüven, C, Özbakır, L, Yavuz, Y. 2010. Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling; (34): 1539-1548.
32. 34. Engin, O, Yılmaz, MK, Baysal, ME, Sarucan, A, 2013. Solving fuzzy job shop scheduling problems with availability constraints using a scatter search method. Journal of Multi-Valued Logic and Soft Computing; (21): 317-334.
33. 35. Engin, O, Kahraman, C, Yılmaz, MK, 2009. A Scatter Search Method for Multi Objective Fuzzy Permutation Flow Shop Scheduling Problem: A Real-World Application, 169-189, Computational Intelligence in Flow Shop and Job Shop Scheduling, Springer, Uday K. Chakraborty (Ed.) , ISBN:978-3-642-02836-6
34. 36. Marti, R. 2003. Principles of Scatter Search, Leeds School of Business, University of Colorado, Campus Box 419, Boulder, CO.
35. 37. Naderi, B, Ruiz, R. 2014. A scatter search algorithm for the distributed permutation flow shop scheduling problem. European Journal Operation Research; (239): 323-334.
36. 38. Cano, DB, Santana, JB, Rodriguez, CC, DelAmo IJG, Torres MG, Garcia, FJM, Batista, BM, Perez, JAM, Vega, JMM, Martin, RR. 2004. Nature-inspired components of the Scatter Search, Technical Report.
37. 39. Oktay, S, Engin, O. 2006. Scatter search method for solving industrial problems: literature survey. Journal of Engineering and Natural Sciences; (3): 144- 155. 40. Glover, F, 1998. A template for scatter search and path relinking, Artificial Evolution; (1363): 3-51.
38. 41. Glover, F, Laguna, M, Marti, R. 2000. Fundamentals of scatter search and path relinking. Control Cybernetics; (29): 653-684.
39. 42. Marti, R. 2006. Scatter search - Wellsprings and challenges. European Journal Operation Research; (169): 351-358.
40. 43. Marti, R, Laguna, M, Glover, F. 2006. Principles of scatter search. European Journal Operation Research; (169): 359-372.
41. 44. Engin, O, Ceran, G, Yılmaz, MK. 2011. An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems. Applied Soft Computing; 11(3): 3056-3065.
42. 45. Kahraman, C, Engin, O, Kaya, I, Yılmaz, MK. 2008. An application of effective genetic algorithms for solving hybrid flow shop scheduling problems. International Journal of Computational Intelligence Systems; 1(2): 134- 147.
43. 46. Fattahi, P, Jolai, F, Arkat, J. 2009. Flexible job shop scheduling with overlapping in operations. Applied Mathematical Modelling; (33): 3076-3087.
44. 47. Xia, W, Wu, Z, 2005. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering; 48(2): 409-425.