SavedAdd your journal

Journals / International Journal of Pure and Applied Sciences / 2026 / Volume: 7 Issue: 1

Adaptive Large Neighborhood Search Heuristic for Mixed Blocking Flowshop Scheduling Problem

Damla Kızılay(IZMIR DEMOCRACY UNIVERSITY)0000-0002-6561-8819
Zeynel Abidin Çil(IZMIR DEMOCRACY UNIVERSITY)0000-0002-7270-9321
Pages
—
Publication Date
2021-06-30
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The results of the proposed algorithm are very competitive.

📌 3 Key Takeaways

🎯
Objective & Hypothesis: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.
📊
Key Findings & Data: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.
💡
Conclusion & Impact:The results of the proposed algorithm are very competitive.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Flowshop Scheduling · Adaptive Large Neighborhood Search · Constraint Programming

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.

🔖

Cite This Article

Kızılay, D., Çil, Z. A. (2021). Adaptive Large Neighborhood Search Heuristic for Mixed Blocking Flowshop Scheduling Problem. International Journal of Pure and Applied Sciences, Volume: 7 Issue: 1. https://doi.org/10.29132/ijpas.911146

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (39)

  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