Non-Identical Parallel Machine Scheduling Problem with Sequence-Dependent Setup Time: An Application in a Corrugated Cardboard Factory

Year 2022, Volume: 14 Issue: 2, 552 - 560, 31.07.2022

Sümeyye Ünlu , Hacı Mehmet Alakaş

https://doi.org/10.29137/umagd.1059071

Abstract

The problem of non-identical parallel machine scheduling has been one of the issues that attracted the attention of enterprises recently. Being able to do a job very effectively and quickly depends on scheduling. Any extra time spent, such as the processing times of the machines, the preparation times for product transitions, affects the production speed and capacity. In this study, non-identical parallel machine scheduling problem with sequence dependent setup time is discussed. The study was carried out practically in a company that produces corrugated cardboard. The aim of the study is to minimize the total completion time (Cmax). There are two parallel machines in the company that are used in the same operations but are not identical according to their features. Machine differences are speed, capacity, preparation times for product transitions and technical features. 112 order-product information and information about the preparation times made on the machines were obtained from the enterprise. In line with the information received, the processing times of the incoming orders and the preparation times of the preparations made during the product transitions were calculated. These calculated data were transferred to the created mathematical model and solved with the ILOG Cplex Optimization program. As a result of the solution, a two-week production schedule suitable for the enterprise was obtained.

Keywords

non-ıdentical parallel machine scheduling, sequence dependent setup time, total completion time

Sıra Bağımlı Hazırlık Süreli Özdeş Olmayan Paralel Makine Çizelgeleme Problemi: Oluklu Mukavva Fabrikasında Bir Uygulama

Abstract

Özdeş olmayan paralel makine çizelgeleme problemi son zamanlarda işletmelerin ilgisini çeken konulardan birisi olmuştur. İşletmeye gelene bir işin son derece etkin ve hızlı şekilde yapılabilmesi çizelgelemeye bağlıdır. Makinelerin işlem süreleri, ürün geçişlerinde yapılan hazırlık süreler gibi fazladan harcanan her süre üretim hızı ve kapasitesini etkilemektedir. Yapılan bu çalışmada sıra bağımlı hazırlık süreli özdeş olmayan paralel makine çizelgeleme problemi ele alınmıştır. Çalışma oluklu mukavva üretimi gerçekleştiren işletmede uygulamalı olarak gerçekleştirilmiştir. Çalışmanın amacı toplam tamamlanma zamanı (Cmax) minimizasyonudur. Firmada aynı operasyonlarda kullanılan fakat sahip oldukları özelliklere göre özdeş olmayan iki adet paralel makine bulunmaktadır. Makine farklılıkları ise hız, kapasite, ürün geçişlerindeki hazırlık süreleri ve teknik özellikleridir. İşletmeden 112 adet sipariş- ürün bilgisi ve makinelerde yapılan hazırlık sürelerinin bilgisi alınmıştır. Alınan bilgiler doğrultusunda gelen siparişlerin işlem süreleri ve ürün geçişleri esnasında yapılan hazırlıkların hazırlık süreleri matrisi hesaplanmıştır. Bu hesaplanan veriler oluşturulan matematiksel modele aktarılarak, ILOG Cplex Optimization programı ile çözülmüştür. Çözüm sonucunda işletme için uygun iki haftalık üretim çizelgesi elde edilmiştir.

Keywords

Özdeş olmayan paralel makine çizelgeleme, sıra bağımlı hazırlık süresi, toplam tamamlanma zamanı

References

• Arnaout, J. P., Rabadi, G., & Musa, R. (2010). A Two-Stage Ant Colony Optimization Algorithm To Minimize The Makespan On Unrelated Parallel Machines With Sequence-Dependent Setup Times. Journal Of Intelligent Manufacturing, 21(6), 693-701.
• Bank, J., & Werner, F. (2001). Heuristic Algorithms For Unrelated Parallel Machine Scheduling With A Common Due Date, Release Dates, And Linear Earliness And Tardiness Penalties. Mathematical And Computer Modelling, 33(4-5), 363-383.
• Chen, J. F. (2009). Scheduling On Unrelated Parallel Machines With Sequence-And Machine-Dependent Setup Times And Due-Date Constraints. The International Journal Of Advanced Manufacturing Technology, 44(11), 1204-1212.
• French, S. (1982). Sequencing And Scheduling: An Introduction To The Mathematics Of The Job-Shop. New York: Ellis Horwood Series.
• Furugi, A. (2021). Makine Uygunluk Kısıtlaması Ve Sıra Bağımlı Kurulum Süresi İle Özdeş Olmayan Paralel Makine Çizelgeleme Problemi İçin Tabu Arama Algoritması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36(3), 1539-1550.
• Herr, O., & Goel, A. (2016). Minimising Total Tardiness For A Single Machine Scheduling Problem With Family Setups And Resource Constraints. European Journal Of Operational Research, 248(1), 123-135.
• Hulett, M., Damodaran, P., & Amouie, M. (2017). Scheduling Non-İdentical Parallel Batch Processing Machines To Minimize Total Weighted Tardiness Using Particle Swarm Optimization. Computers & Industrial Engineering, 113, 425-436.
• Kyparisis, G. J., & Koulamas, C. (2006). Flexible Flow Shop Scheduling With Uniform Parallel Machines. European Journal Of Operational Research, 168(3), 985-997.
• Lee, S. M., & Asllani, A. A. (2004). Job Scheduling With Dual Criteria And Sequence-Dependent Setups: Mathematical Versus Genetic Programming. Omega, 32(2), 145-153.
• Liao, T. W., Chang, P. C., Kuo, R. J., & Liao, C. J. (2014). A Comparison Of Five Hybrid Metaheuristic Algorithms For Unrelated Parallel-Machine Scheduling And İnbound Trucks Sequencing İn Multi-Door Cross Docking Systems. Applied Soft Computing, 21, 180-193.
• Liaw, C. F., Lin, Y. K., Cheng, C. Y., & Chen, M. (2003). Scheduling Unrelated Parallel Machines To Minimize Total Weighted Tardiness. Computers & Operations Research, 30(12), 1777-1789.
• Perez-Gonzalez, P., Fernandez-Viagas, V., García, M. Z., & Framinan, J. M. (2019). Constructive Heuristics For The Unrelated Parallel Machines Scheduling Problem With Machine Eligibility And Setup Times. Computers & Industrial Engineering, 131, 131-145.
• Pinedo, M. L. (2008). Scheduling: theory, algorithms, and systems. Springer
• Rocha, P. L., Ravetti, M. G., Mateus, G. R., & Pardalos, P. M. (2008). Exact Algorithms For A Scheduling Problem With Unrelated Parallel Machines And Sequence And Machine-Dependent Setup Times. Computers & Operations Research, 35(4), 1250-1264.
• Sarıçiçek, İ. (2018). Özdeş Olmayan Paralel Makina Çizelgeleme Problemlerinin Çözümü İçin Bir Karar Destek Sistemi. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 24(1), 108-116.
• Silva, C., & Magalhaes, J. M. (2006). Heuristic Lot Size Scheduling On Unrelated Parallel Machines With Applications İn The Textile İndustry. Computers & Industrial Engineering, 50(1-2), 76-89.
• Tran, T. T., Araujo, A., & Beck, J. C. (2016). Decomposition Methods For The Parallel Machine Scheduling Problem With Setups. Informs Journal On Computing, 28(1), 83-95.
• Turkcan, A., Akturk, M. S., & Storer, R. H. (2003). Non-İdentical Parallel Cnc Machine Scheduling. International Journal Of Production Research, 41(10), 2143-2168.
• Vallada, E., & Ruiz, R. (2011). A Genetic Algorithm For The Unrelated Parallel Machine Scheduling Problem With Sequence Dependent Setup Times. European Journal Of Operational Research, 211(3), 612-622.
• Weng, M. X., Lu, J., & Ren, H. (2001). Unrelated Parallel Machine Scheduling With Setup Consideration And A Total Weighted Completion Time Objective. International Journal Of Production Economics, 70(3), 215-226.