Erken ve Geç Teslim Hedefleriyle Beklemesiz Akış Tipi Atölye Çizelgeleme Problemini Çözmek İçin Kesin Bir Çözüm Algoritması

Abstract

Beklemesiz akış tipi atölye çizelgeleme problemi (BATAÇP), işlerin belirli bir makine sırasını takip ettiği geleneksel akış tipi atölye yapılandırmasının bir uzantısıdır. BATAÇP, akış tipi atölye problemine, ardışık makineler arasında işlerin beklemesine izin vermeyen bir kısıtlama ekleyerek genişletilmiştir. BATAÇP ile ilgili son çalışmalar, genellikle en sona çizelgelenen işin tamamlanma süresi, toplam akış zamanı ve toplam tamamlanma süresi gibi geleneksel hedeflere odaklanmıştır. Ancak, erken tamamlanma ve gecikme hedeflerinin birlikte kullanıldığı çözüm yaklaşımlarına yönelik sınırlı çalışmalar bulunmaktadır. BATAÇP, NP-zor olarak sınıflandırılmakta olup, büyük problem örnekleri için optimal çözümler bulmak hesaplama açısından zorluklar yaratmaktadır. Bunun üstesinden gelmek için, tavlama benzetimi, tabu arama ve parçacık sürüsü optimizasyonu gibi sezgisel ve meta-sezgisel yöntemler yaygın olarak kullanılarak yaklaşık-optimal çözümler bulunmaktadır. Bununla birlikte, mevcut literatürde bu problem için kesin çözüm yöntemleri oldukça azdır. Bu boşluğu doldurmak amacıyla, bu makale BATAÇP için yeni bir karma tam sayılı programlama (KTP) modeli tanıtmaktadır ve erken tamamlanma ve gecikme hedeflerini minimize etmek amacıyla bu yeni model üzerine inşa edilmiş bir dal-kesme (DK) algoritması sunmaktadır. Önerilen DK algoritması, güçlü üst sınırlar elde etmek için bir sezgisel yaklaşım ile birleştirilmiştir. Algoritma, problem alanını sistematik bir şekilde keşfederek ve kesme düzlemi teknikleri kullanarak matematiksel formülasyonları iyileştirmektedir. Algoritmanın performansı, kapsamlı bir kıyaslama problem örnekleri seti kullanılarak test edilmekte ve sonuçlar, literatürde bulunan KTP modeli ile karşılaştırılmaktadır. Hesaplamalı deneyler, önerilen DK algoritmasının hem çözüm kalitesi hem de hesaplama verimliliği açısından etkin olduğunu göstermektedir.

Keywords

• Beklemesiz Akış Tipi Atölye Çizelgeleme Problemi
• Dal-Kesme Algoritması
• Karma Tam Sayılı Programlama Modeli
• Sezgisel Algoritmalar

An Exact Solution Algorithm to Solve the No-Wait Flow Shop Scheduling Problem with Earliness and Tardiness Objectives

Abstract

The no-wait flow shop scheduling problem (NWFSP) is an extension of the traditional flow shop configuration, where jobs follow a fixed sequence of machines. The NWFSP extends the flow shop problem by incorporating a constraint that does not allow jobs to wait between subsequent machines. Recent studies on the NWFSP have primarily focused on traditional objectives, such as makespan, total flow time, and total completion time. However, there are limited studies addressing the simultaneous use of earliness and tardiness objectives. Classified as NP-hard, the NWFSP poses significant computational challenges when seeking optimal solutions for large problem instances. To overcome this, heuristic and metaheuristic algorithms, including simulated annealing, tabu search, and particle swarm algorithm, are commonly used to find near-optimal solutions. Nevertheless, exact solution methods for this problem remain scarce in existing literature. To fill this gap, this paper introduces a novel mixed-integer programming (MIP) model for the NWFSP and presents a branch-and-cut (BC) algorithm built upon this new model, with the objective of minimizing earliness and tardiness. The BC algorithm is combined with a heuristic approach to provide strong upper bounds. It systematically explores the problem space and improves mathematical formulations using cutting plane techniques. The algorithm’s performance is tested using a comprehensive set of benchmark problem instances, with results compared to a MIP model from the literature. Computational experiments demonstrate that the proposed BC algorithm is effective both in terms of solution quality and computational efficiency.

Keywords

• No-Wait Flow Shop Scheduling Problem
• Branch-and-Cut Algorithm
• Mixed-Integer Programming Model
• Heuristic Algorithms

References

1. Pan, Q.K., Wang, L. 2012. Effective Heuristics for the Blocking Flowshop Scheduling Problem with Makespan Minimization, Omega, Vol. 40, no. 2, pp. 218-229.
2. Lin, S.W., Ying, K.C. 2013. Minimizing Makespan in a Blocking Flowshop using a Revised Artificial Immune System Algorithm, Omega, Vol. 41, no. 2, pp. 383-389.
3. Shabtay, D., Arviv, K., Stern, H., Edan, Y. 2014. A Combined Robot Selection and Scheduling Problem for Flow-Shops with No-Wait Restrictions, Omega, Vol. 43, no. 1, pp. 96-107.
4. Pan, Q.K., Ruiz, R. 2014. An Effective Iterated Greedy Algorithm for the Mixed No-Idle Permutation Flowshop Scheduling Problem, Omega, Vol. 44, no. 1, pp. 41-50.
5. Yenisey, M.M., Yagmahan, B. 2014. Multi-Objective Permutation Flowshop Scheduling Problem: Literature Review, Classification and Current Trends, Omega, Vol. 45, no. 1, pp. 119-135.
6. Aldowaisan, T., Allahverdi, A. 2004. New Heuristics for m-Machine No-Wait Flowshop to Minimize Total Completion Time, Omega, Vol. 32, no. 5, pp. 345-352.
7. Sapkal, S.U., Laha, D. 2013. A Heuristic for No-Wait Flow Shop Scheduling, International Journal of Advanced Manufacturing Technology, Vol. 68, no. 5-8, pp. 1327-1338.
8. Allahverdi, A. 2016. A Survey of Scheduling Problems with No-Wait in Process, European Journal of Operational Research, Vol. 255, pp. 665-686.

9. Graham, R., Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G. 1979. Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey, Annals of Discrete Mathematics, Vol. 5, pp. 287-326.
10. Röck, H. 1984. The Three-Machine No-Wait Flow Shop is NP-Complete, Journal of the ACM, Vol. 31, no. 2, pp. 336-345.
11. Aldowaisan, T., Allahverdi, A. 2012. Minimizing Total Tardiness in No-Wait Flowshops, Foundations of Computing and Decision Sciences, Vol. 37, pp. 149-162.
12. Liu, G., Song, S., Wu, C. 2013. Some Heuristics for No-Wait Flowshops with Total Tardiness Criterion, Computers & Operations Research, Vol. 40, pp. 521-525.
13. Ding, J., Song, S., Zhang, R., Gupta, J.N., Wu, C. 2015. Accelerated Methods for Total Tardiness Minimisation in No-Wait Flowshops, International Journal of Production Research, Vol. 53, pp. 1002-1018.
14. Javadi, B., Saidi-Mehrabad, M., Haji, A., Mahdavi, I., Jolai, F., Mahdavi-Amiri, N. 2008. No-Wait Flow Shop Scheduling using Fuzzy Multi-Objective Linear Programming, Journal of the Franklin Institute, Vol. 345, pp. 452-467.
15. Tavakkoli-Moghaddam, R., Rahimi-Vahed, A.R., Mirzaei, A.H. 2008. Solving a Multi-Objective No-Wait Flow Shop Scheduling Problem with an Immune Algorithm, International Journal of Advanced Manufacturing Technology, Vol. 36, pp. 969-981.
16. Abdollahpour, S., Rezaian, J. 2017. Two New Meta-Heuristics for No-Wait Flexible Flow Shop Scheduling Problem with Capacitated Machines, Mixed Make-to-Order and Make-to-Stock Policy, Soft Computing, Vol. 21, pp. 3147-3165.
17. Gao, F., Liu, M., Wang, J.-J., Lu, Y.-Y. 2018. No-Wait Two-Machine Permutation Flow Shop Scheduling Problem with Learning Effect, Common Due Date and Controllable Job Processing Times, International Journal of Production Research, Vol. 56, pp. 2361-2369.
18. Li, Z., Zhong, R.Y., Barenji, A.V., Liu, J.J., Yu, C.X., Huang, G.Q. 2021. Bi-Objective Hybrid Flow Shop Scheduling with Common Due Date, Operations Research, Vol. 21, pp. 1153-1178.
19. Lv, D.-Y., Wang, J.-B. 2021. Study on Resource-Dependent No-Wait Flow Shop Scheduling with Different Due-Window Assignment and Learning Effects, Asia-Pacific Journal of Operational Research, Vol. 38, p. 2150008.
20. Allali, K., Aqil, S., Belabid, J. 2022. Distributed No-Wait Flow Shop Problem with Sequence Dependent Setup Time: Optimization of Makespan and Maximum Tardiness, Simulation Modelling Practice and Theory, Vol. 116, p. 102455.
21. Huang, R.-H., Yang, C.-L., Liu, S.-C. 2015. No-Wait Flexible Flow Shop Scheduling with Due Windows, Mathematical Problems in Engineering, Vol. 2015, p. 456719.
22. Arabameri, S., Salmasi, N. 2013. Minimization of Weighted Earliness and Tardiness for No-Wait Sequence-Dependent Setup Times Flowshop Scheduling Problem, Computers & Industrial Engineering, Vol. 64, pp. 902-916.
23. Schaller, J., Valente, J.M. 2020. Minimizing Total Earliness and Tardiness in a No-Wait Flow Shop, International Journal of Production Economics, Vol. 224, p. 107542.
24. Schaller, J., Valente, J.M.S. 2022. Scheduling in a No-Wait Flow Shop to Minimise Total Earliness and Tardiness with Additional Idle Time Allowed, International Journal of Production Research, Vol. 60, pp. 5488-5504.
25. Guevara-Guevara, A.F., Gómez-Fuentes, V., Posos-Rodríguez, L.J., Remolina-Gómez, N., González-Neira, E.M. 2022. Earliness/Tardiness Minimization in a No-Wait Flow Shop with Sequence-Dependent Setup Times, Journal of Project Management, Vol. 7, pp. 177-190.
26. Zhu, N., Zhao, F., Wang, L., Ding, R., Xu, T. 2022. A Discrete Learning Fruit Fly Algorithm Based on Knowledge for the Distributed No-Wait Flow Shop Scheduling with Due Windows, Expert Systems with Applications, Vol. 198, p. 116921.
27. Qian, B., Zhang, Z.-Q., Hu, R., Jin, H.-P., Yang, J.-B. 2022. A Matrix-Cube-Based Estimation of Distribution Algorithm for No-Wait Flow-Shop Scheduling With Sequence-Dependent Setup Times and Release Times, IEEE Transactions on Systems, Man, and Cybernetics: Systems, pp. 1-12.
28. Ingber, L. 1993. Simulated Annealing: Practice Versus Theory, Mathematical and Computer Modelling, Vol. 18, pp. 29-57.
29. Karacan, I., Senvar, O., Bulkan, S. 2023. A Novel Parallel Simulated Annealing Methodology to Solve the No-Wait Flow Shop Scheduling Problem with Earliness and Tardiness Objectives, Processes, Vol. 11, p. 454.
30. Bagchi, T.P., Gupta, J.N., Sriskandarajah, C. 2006. A Review of TSP Based Approaches for Flowshop Scheduling, European Journal of Operational Research, Vol. 169, no. 3, pp. 816-854.
31. Lin, S.-W., Ying, K.-C. 2016. Optimization of Makespan for No-Wait Flowshop Scheduling Problems using Efficient Matheuristics, Omega, Vol. 64, pp. 115-125.
32. Ruiz, R., Pan, Q.K., Naderi, B. 2019. Iterated Greedy Methods for the Distributed Permutation Flowshop Scheduling Problem, Omega, Vol. 83, pp. 213-222.
33. Naderi, B., Ruiz, R. 2010. The Distributed Permutation Flowshop Scheduling Problem, Computers & Operations Research, Vol. 37, no. 4, pp. 754-768.
34. Valente, J.M., Alves, R.A. 2005. Beam Search Algorithms for the Early/Tardy Scheduling Problem with Release Dates, Journal of Manufacturing Systems, Vol. 24, pp. 35-46.
35. Avci, M., Avci, M.G., Hamzadayı, A. 2022. A Branch-and-Cut Approach for the Distributed No-Wait Flowshop Scheduling Problem, Computers & Operations Research, Vol. 148, p. 106009.