Adaptive Large Neighborhood Search Heuristic for Mixed Blocking Flowshop Scheduling Problem

Year 2021, Volume: 7 Issue: 1, 152 - 162, 30.06.2021

Damla Kızılay , Zeynel Abidin Çil

https://doi.org/10.29132/ijpas.911146

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

• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Kizilay, D. (2018). Integrating the Optimization of Quay and Yard Operations in Container Terminals. Yasar University.
• 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.
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Sawik, T. J. (1993). A scheduling algorithm for flexible flow lines with limited intermediate buffers. Applied Stochastic Models and Data Analysis, 9, 127–138.
• 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.
• 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
• 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
• 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
• 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
• 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
• Trabelsi, Wajdi, Sauvey, C., & Sauer, N. (2010). Heuristic methods for problems with blocking constraints solving jobshop scheduling.
• 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
• 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
• 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
• 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