A No-Wait Flowshop Scheduling Problem with Batch Delivery System

Öz

This study investigates the no-wait permutation flowshop scheduling problem (NWPFSP). This type of problem adds constraints to the permutation flow type scheduling problem in that jobs are prohibited from waiting between machines during processing. The NWFSP is a common problem type in industry. After processing jobs on machines, products are distributed to several customers. It is recommended that products be transferred immediately after they are finished on a production line to avoid delays. However, this approach may lead to high distribution costs. Consequently, a balance between distribution costs and delay must be considered when making operational decisions. Grouping products for delivery is an effective way to reduce the cost of distribution and is called batch delivery (BD) in literature. For this reason, the integration of the NWFSP with the batch delivery (BD) is addressed by minimizing the total delay and batch delivery costs. This problem is called the No-Wait Flowshop Scheduling Problem with Batch Delivery (NWFSPBD). For this integrated production and distribution problem, the Mixed-Integer Linear Programming Model (MILPM) and Constraint Programming Model (CPM) were developed. These two mathematical models were tested on the instance sets that were produced regarding the related literature. Since the problem is complex, both models have difficulty obtaining an optimal solution within the specified time limit. However, when the results of the CPM are compared with the results of the MILPM, it finds either the same or better results for each data set. Therefore, the CPM has high applicability as it can achieve better results.

Anahtar Kelimeler

• No-wait Flowshop Scheduling Problem
• Batch Delivery
• Mixed-integer Linear Programming
• Constraint Programming

Toplu Teslimat Sistemi ile Beklemesiz Akış Tipi Çizelgeleme Problemi

Öz

Bu çalışma, beklemesiz permütasyon akıştipi çizelgeleme problemini (BAÇP) araştırmaktadır. Bu problem tipi, permütasyon akış tipi çizelgeleme problemine, işlem sırasında makineler arasında işlerin beklemenin yasak olduğu kısıtını eklemektedir. BAÇP endüstride çokça karşılaşılan bir problem tipidir. İşler makinelerde işlendikten sonra üretilen ürünler müşterilere dağıtılmalıdır. Gecikmeleri önlemek için ürünlerin bir üretim hattında biter bitmez tedarik edilmesi tavsiye edilir ancak bu yaklaşım yüksek dağıtım maliyetlerine yol açabilir. Sonuç olarak, operasyonel kararlar alınırken, dağıtım maliyetleri ile gecikme arasında bir denge göz önünde bulundurulmalıdır. Ürünleri teslimat için gruplandırmak, literatürde toplu teslimat (TT) olarak adlandırılmaktadır ve dağıtım maliyetini azaltmak için etkili bir yoldur. Bu sebeple, bu çalışmada, BAÇP ve toplu teslimat (TT) ile ürünlerin birden fazla müşteriye teslim edilmesinin entegrasyonu, toplam gecikme ve toplu teslimat maliyetlerini en aza indirecek şekilde düşünülmüştür. Çalışılan bu problem, “Toplu Teslimat ile Beklemesiz Akış Tipi Çizelgeleme Problemi” (BAÇP-TT) olarak adlandırılmıştır. Ele alınan bu entegre üretim ve dağıtım problemi için karma tamsayılı doğrusal programlama modeli (KTDPM) ve kısıt programlama modeli (KPM) geliştirilmiştir. Geliştirilen iki matematiksel model, literatürden yararlanılarak üretilen veri setleri üzerinde çalıştırılarak test edilmiştir. Problemin karmaşık yapısı nedeniyle her iki model de belirlenen zaman sınırı içerisinde optimal çözümü elde etmekte zorluk çekmektedir. Ancak KPM’nin sonuçları KTDPM’nin sonuçlarıyla karşılaştırıldığında her veri seti için ya aynı ya da daha iyi sonuçlar elde edilmiştir. Bu nedenle KPM’nin bu problem için uygulanabilirliği yüksektir.

Anahtar Kelimeler

• Beklemesiz Akış Tipi Çizelgeleme Problemi
• Toplu Teslimat
• Karma-Tamsayılı Doğrusal Programlama
• Kısıt Programlama

Kaynakça

1. Ahmadizar, F., and S. Farhadi. 2015. “Single-Machine Batch Delivery Scheduling with Job Release Dates, Due Windows and Earliness, Tardiness, Holding and Delivery Costs.” Computers & Operations Research 53: 194–205.
2. Aldowaisan, T., and A. Allahverdi. 2012. “Minimizing Total Tardiness in No-Wait Flowshops.” Foundations of Computing and Decision Sciences 37 (3). Versita: 149–62. doi:10.2478/v10209-011-0009-6.
3. Aldowaisan, T, and A Allahverdi. 2015. “No-Wait Flowshops to Minimize Total Tardiness with Setup Times.” Intelligent Control and Automation 6: 38–44. doi:10.4236/ica.2015.61005.
4. Cheng, T. C. E., and H. G. Kahlbacher. 1993. “Scheduling with Delivery and Earliness Penalties.” Asia-Pacific Journal of Operational Research 10 (2): 145–52.
5. Gao, Kai-zhou, Quan-ke Pan, and Jun-qing Li. 2011. “Discrete Harmony Search Algorithm for the No-Wait Flow Shop Scheduling Problem with Total Flow Time Criterion.” The International Journal of Advanced Manufacturing Technology 56 (5–8). Springer-Verlag: 683–92. doi:10.1007/s00170-011-3197-6.
6. Gao, Kai-Zhou, Quan-Ke Pan, Jun-Qing Li, Yu-Ting Wang, and Jing Liang. 2012. “A Hybrid Harmony Search Algorithm for the No-Wait Flow-Shop Schdeuling Problems.” Asia-Pacific Journal of Operational Research 29 (02). World Scientific Publishing Co. & Operational Research Society of Singapore: 1250012. doi:10.1142/S0217595912500121.
7. Guo, Z., D. Zhang, S. Y. S. Leung, and L. Shi. 2016. “A Bi-Level Evolutionary Optimization Approach for Integrated Production and Transportation Scheduling.” Applied Soft Computing 42: 215–28.
8. Hall, Nicholas G., and Chelliah Sriskandarajah. 1996. “A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process.” Operations Research 44 (3). INFORMS Inst.for Operations Res.and the Management Sciences: 510–25. doi:10.1287/opre.44.3.510.

9. Hamidinia, A., Khakabimamaghani, S., Mazdeh, M. M., and M. Jafari. 2012. “A Genetic Algorithm for Minimizing Total Tardiness/Earliness of Weighted Jobs in a Batched Delivery System.” Computers & Industrial Engineering 62 (1): 29–38.
10. Hentenryck, Pascal Van. 2002. “Constraint and Integer Programming in OPL.” INFORMS J. on Computing 14 (4). Linthicum, MD, USA: INFORMS: 345–372.
11. Karabulut, Korhan, Hande Öztop, Damla Kizilay, M Fatih Tasgetiren, and Levent Kandiller. 2022. “An Evolution Strategy Approach for the Distributed Permutation Flowshop Scheduling Problem with Sequence-Dependent Setup Times.” Computers & Operations Research 142: 105733. doi:https://doi.org/10.1016/j.cor.2022.105733.
12. Kizilay, Damla, Zeynel Abidin Çil, Hande Öztop, and İclal Bağcı. 2023. “A Novel Mathematical Model for Mixed-Blocking Permutation Flow Shop Scheduling Problem with Batch Delivery BT - Towards Industry 5.0.” In , edited by Numan M Durakbasa and M Güneş Gençyılmaz, 453–61. Cham: Springer International Publishing.
13. Kizilay, Damla, Pascal Van Hentenryck, and Deniz T. Eliiyi. 2020. “Constraint Programming Models for Integrated Container Terminal Operations.” European Journal of Operational Research 286 (3). Elsevier B.V.: 945–62. doi:10.1016/j.ejor.2020.04.025.
14. Lin, Shih-Wei, and Kuo-Ching Ying. 2016. “Optimization of Makespan for No-Wait Flowshop Scheduling Problems Using Efficient Matheuristics.” Omega 64 (October). Pergamon: 115–25. doi:10.1016/J.OMEGA.2015.12.002.
15. Liu, P., and X. Lu. 2016. “Integrated Production and Job Delivery Scheduling with an Availability Constraint.” International Journal of Production Economics 176: 1–6.
16. Mazdeh, M. M., M. Rostami, and M. H. Namaki. 2013. “Minimizing Maximum Tardiness and Delivery Costs in a Batched Delivery System.” Computers & Industrial Engineering 66 (4): 675–82.
17. Öztop, Hande, M Fatih Tasgetiren, Levent Kandiller, and Quan-Ke Pan. 2022. “Metaheuristics with Restart and Learning Mechanisms for the No-Idle Flowshop Scheduling Problem with Makespan Criterion.” Computers & Operations Research 138: 105616. doi:https://doi.org/10.1016/j.cor.2021.105616.
18. Pan, Q.-K., M.F. Tasgetiren, and Y.-C. Liang. 2008. “A Discrete Particle Swarm Optimization Algorithm for the No-Wait Flowshop Scheduling Problem.” Computers & Operations Research 35 (9). Pergamon: 2807–39. doi:10.1016/J.COR.2006.12.030.
19. Pereira, M. T., and M. S. Nagano. 2022. “Hybrid Metaheuristics for the Integrated and Detailed Scheduling of Production and Delivery Operations in No-Wait Flow Shop Systems.” Computers & Industrial Engineering, 108255.
20. Rahman, H. F., Janardhanan, M. N., L. P. Chuen, and S. G. Ponnambalam. 2021. “Flowshop Scheduling with Sequence Dependent Setup Times and Batch Delivery in Supply Chain.” Computers & Industrial Engineering 158: 107378.
21. Reddi, S. S., and C. V. Ramamoorthy. 1972. “On the Flow-Shop Sequencing Problem with No Wait in Process.” Journal of the Operational Research Society 23 (3): 323–31.
22. Röck, Hans. 1984. “The Three-Machine No-Wait Flow Shop Is NP-Complete.” Journal of the ACM 31 (2): 336–45. doi:10.1145/62.65.
23. Vallada, Eva, Rubén Ruiz, and Jose M Framinan. 2015. “New Hard Benchmark for Flowshop Scheduling Problems Minimising Makespan.” European Journal of Operational Research 240 (3): 666–77. doi:https://doi.org/10.1016/j.ejor.2014.07.033.
24. Wang, G., and T. E. Cheng. 2000. “Parallel Machine Scheduling with Batch Delivery Costs.” International Journal of Production Economics 68 (2): 177–83.
25. Wang, K., H. Luo, F. Liu, and X. Yue. 2017. “Permutation Flow Shop Scheduling with Batch Delivery to Multiple Customers in Supply Chains.” IEEE Transactions on Systems, Man, and Cybernetics: Systems 48 (10): 1826–37.
26. Wang, X., and T. C. E. Cheng. 2009. “Heuristics for Parallel-Machine Scheduling with Job Class Setups and Delivery to Multiple Customers.” International Journal of Production Economics 119 (1): 199–206.
27. Wismer, D. A. 1972. “Solution of the Flowshop-Scheduling Problem with No Intermediate Queues.” Operations Research 20 (3). INFORMS: 689–97. doi:10.1287/opre.20.3.689.
28. Yamada, Tuane Tonani, Marcelo Seido Nagano, and Hugo Hissashi Miyata. 2021. “Minimization of Total Tardiness in No-Wait Flowshop Production Systems with Preventive Maintenance.” International Journal of Industrial Engineering Computations 12 (4). Growing Science: 415–26. doi:10.5267/J.IJIEC.2021.5.002.
29. Yang, X. 2000. “Scheduling with Generalized Batch Delivery Dates and Earliness Penalties.” IIE Transactions 32 (8): 735–41.
30. Yüksel, Damla. 2019. “Bi-Objective No-Wait Permutation Flowshop Scheduling Problems.” Yaşar University.