Adaptive Large Neighborhood Search Heuristic for Mixed Blocking Flowshop Scheduling Problem

Abstract

Traditional permutation flowshop scheduling problem (PFSP), which has unlimited buffer space, has been interested over the fifty years by several authors to account for many industrial applications. However, some industries, such as the aerospace industry and other sectors processing industrial waste, have different blocking conditions due to the limited or lack of buffer area between their machines. In this study, a mixture of different blocking types is considered to solve PFSP with the total flow time criterion regarding several blocking types. A constraint programming model is proposed to solve the PFSP with mixed blocking constraints (MBFSP). Due to the problem's NP-hard nature of the problem, an adaptive large neighborhood search heuristic is proposed to solve the large size instances. The results of the proposed algorithm are very competitive.

Keywords

• Flowshop Scheduling
• Adaptive Large Neighborhood Search
• Constraint Programming

References

1. Blazewicz, J., H. Ecker, K., Pesch, E., Schmidt, G., & Wȩglarz, J. (2007). Handbook on scheduling. From theory to applications. International Handbook on Information Systems. https://doi.org/10.1007/978-3-540-32220-7
2. Caraffa, V., Ianes, S., P. Bagchi, T., & Sriskandarajah, C. (2001). Minimizing makespan in a blocking flowshop using genetic algorithms. International Journal of Production Economics, 70(2), 101–115. https://doi.org/10.1016/S0925-5273(99)00104-8
3. Cheng, C.-Y., Lin, S.-W., Pourhejazy, P., Ying, K.-C., & Zheng, J.-W. (2020). Minimizing Total Completion Time in Mixed-Blocking Permutation Flowshops. IEEE Access, 8, 142065–142075. https://doi.org/10.1109/ACCESS.2020.3014106
4. Grabowski, Jozef, & Pempera, J. (2000). Sequencing of jobs in some production system. European Journal of Operational Research, 125(3), 535–550. https://doi.org/10.1016/S0377-2217(99)00224-6
5. Grabowski, Józef, & Pempera, J. (2007). The permutation flow shop problem with blocking. A tabu search approach. Omega, 35(3), 302–311. https://doi.org/10.1016/J.OMEGA.2005.07.004
6. Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Annals of Discrete Mathematics, 5, 287–326. https://doi.org/10.1016/S0167-5060(08)70356-X
7. Hall, N. G., & Sriskandarajah, C. (1996). A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process. Oper. Res., 44(3), 510–525. https://doi.org/10.1287/opre.44.3.510
8. Hall, N., & Sriskandarajah, C. (2000). Minimizing Cycle Time in a Blocking Flowshop. Operations Research, 48, 177–180. https://doi.org/10.1287/opre.48.1.177.12451

9. Johnson, S. M. (1954). Optimal Two and Three Stage Production Schedules With Set-Up Time Included. Naval Research Logistics Quarterly, 1, 61–68. https://doi.org/10.1002/nav.3800010110
10. Khorramizadeh, M., & Riahi, V. (2015). A Bee Colony Optimization Approach for Mixed Blocking Constraints Flow Shop Scheduling Problems. Mathematical Problems in Engineering, 2015, 612604. https://doi.org/10.1155/2015/612604
11. Kizilay, D. (2018). Integrating the Optimization of Quay and Yard Operations in Container Terminals. Yasar University.
12. Kizilay, D., Eliiyi, D. T., & Van Hentenryck, P. (2018). Constraint and Mathematical Programming Models for Integrated Port Container Terminal Operations. In W.-J. van Hoeve (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research (pp. 344–360). Springer International Publishing.
13. Lin, S. W., Cheng, C. Y., Pourhejazy, P., & Ying, K. C. (2021). Multi-temperature simulated annealing for optimizing mixed-blocking permutation flowshop scheduling problems. Expert Systems with Applications, 165, 113837. https://doi.org/10.1016/j.eswa.2020.113837
14. Martinez, S., Dauzère-Pérès, S., Guéret, C., Mati, Y., & Sauer, N. (2006). Complexity of flowshop scheduling problems with a new blocking constraint. European Journal of Operational Research, 169(3), 855–864. https://doi.org/https://doi.org/10.1016/j.ejor.2004.08.046
15. Mccormick, S., Pinedo, M., J. Shenker, S., & Wolf, B. (1989). Sequencing in an Assembly Line With Blocking to Minimize Cycle Time. Operations Research, 37, 925–935. https://doi.org/10.1287/opre.37.6.925
16. Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95. https://doi.org/10.1016/0305-0483(83)90088-9
17. Newton, M. A. H., Riahi, V., Su, K., & Sattar, A. (2019). Scheduling blocking flowshops with setup times via constraint guided and accelerated local search. Computers & Operations Research, 109, 64–76. https://doi.org/10.1016/J.COR.2019.04.024
18. Osman, I., & Potts, C. (1989). Simulated annealing for permutation flow-shop scheduling. Omega, 17(6), 551–557. https://doi.org/10.1016/0305-0483(89)90059-5
19. Pan, Q.-K., & Ruiz, R. (2012). An estimation of distribution algorithm for lot-streaming flow shop problems with setup times. Omega, 40(2), 166–180. https://doi.org/10.1016/J.OMEGA.2011.05.002
20. Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & Operations Research, 34(8), 2403–2435. https://doi.org/10.1016/J.COR.2005.09.012
21. Qian, B., Wang, L., Huang, D., Wang, W., & Wang, X. (2009). An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers & Operations Research, 36(1), 209–233. https://doi.org/10.1016/J.COR.2007.08.007
22. Riahi, V., Khorramizadeh, M., Hakim Newton, M. A., & Sattar, A. (2017). Scatter search for mixed blocking flowshop scheduling. Expert Systems with Applications, 79, 20–32. https://doi.org/https://doi.org/10.1016/j.eswa.2017.02.027
23. Riahi, V., Newton, M. A. H., Su, K., & Sattar, A. (2019). Constraint guided accelerated search for mixed blocking permutation flowshop scheduling. Computers & Operations Research, 102, 102–120. https://doi.org/10.1016/J.COR.2018.10.003
24. Ronconi, D P, & Armentano, V. A. (2001). Lower bounding schemes for flowshops with blocking in-process. Journal of the Operational Research Society, 52(11), 1289–1297. https://doi.org/10.1057/palgrave.jors.2601220
25. Ronconi, Débora P. (2004). A note on constructive heuristics for the flowshop problem with blocking. International Journal of Production Economics, 87(1), 39–48. https://doi.org/10.1016/S0925-5273(03)00065-3
26. Ruiz-Torres, A. J., Ho, J. C., & Ablanedo-Rosas, J. H. (2011). Makespan and workstation utilization minimization in a flowshop with operations flexibility. Omega, 39(3), 273–282. https://doi.org/10.1016/J.OMEGA.2010.07.004
27. Sawik, T. (1995). Scheduling flexible flow lines with no in-process buffers. International Journal of Production Research - INT J PROD RES, 33, 1357–1367. https://doi.org/10.1080/00207549508930214
28. Sawik, T. J. (1993). A scheduling algorithm for flexible flow lines with limited intermediate buffers. Applied Stochastic Models and Data Analysis, 9, 127–138.
29. Shaw, P. (1998). Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. In M. Maher & J.-F. Puget (Eds.), Principles and Practice of Constraint Programming --- CP98 (pp. 417–431). Springer Berlin Heidelberg.
30. Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278–285. https://doi.org/10.1016/0377-2217(93)90182-M
31. Tasgetiren, M. F., Kizilay, D., Pan, Q.-K., & Suganthan, P. N. (2017). Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion. Computers and Operations Research, 77. https://doi.org/10.1016/j.cor.2016.07.002
32. Tasgetiren, M. F., Pan, Q.-K., Kizilay, D., & Gao, K. (2016). A Variable Block Insertion Heuristic for the Blocking Flowshop Scheduling Problem with Total Flowtime Criterion. Algorithms, 9(4). https://doi.org/10.3390/a9040071
33. Tasgetiren, M. F., Pan, Q.-K., Kizilay, D., & Suer, G. (2015). A populated local search with differential evolution for blocking flowshop scheduling problem. 2015 IEEE Congress on Evolutionary Computation, CEC 2015 - Proceedings. https://doi.org/10.1109/CEC.2015.7257235
34. Trabelsi, W, Sauvey, C., & Sauer, N. (2011). Complexity and Mathematical Model for Flowshop Problem Subject to Different Types of Blocking Constraint. IFAC Proceedings Volumes, 44(1), 8183–8188. https://doi.org/https://doi.org/10.3182/20110828-6-IT-1002.01887
35. Trabelsi, Wajdi, Sauvey, C., & Sauer, N. (2010). Heuristic methods for problems with blocking constraints solving jobshop scheduling.
36. Trabelsi, Wajdi, Sauvey, C., & Sauer, N. (2012). Heuristics and metaheuristics for mixed blocking constraints flowshop scheduling problems. Computers & Operations Research, 39(11), 2520–2527. https://doi.org/https://doi.org/10.1016/j.cor.2011.12.022
37. Vallada, E., & Ruiz, R. (2010). Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. Omega, 38(1–2), 57–67. https://doi.org/10.1016/J.OMEGA.2009.04.002
38. Vallada, E., Ruiz, R., & Framinan, J. M. (2015). New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research, 240(3), 666–677. https://doi.org/https://doi.org/10.1016/j.ejor.2014.07.033
39. Zhang, G., Xing, K., & Cao, F. (2018). Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion. Engineering Applications of Artificial Intelligence, 76, 96–107. https://doi.org/10.1016/J.ENGAPPAI.2018.09.005