PARALLEL MACHINE SCHEDULING PROBLEM UNDER DIFFERENT PERFORMANCE CRITERIA

Year 2023, Volume: 11 Issue: 3, 1030 - 1053, 28.09.2023

Hilmiye Betül Dikmen , Fatih Balcı , Ecem Çetin , Yasemin Ilgın , Hakan Kaya , Yusuf Baran Kartal , Feyzagül Osmanlı , Ayça Mine Özen , Ece Sürücü , Damla Kızılay

https://doi.org/10.21923/jesd.1244549

Abstract

A parallel machine scheduling problem, which has a very important place among production planning activities, determines which resources will be produced on which machine in which order. Active use of resources and ensuring customer satisfaction in the production environment is directly related to selecting the objective function and whether the work is well-scheduled. In the scheduling problem discussed in this study, non-identical parallel machines, setup times of machines and jobs, and sequence-dependent adjustment times between jobs are considered. It is aimed to contribute to the literature by analyzing how these mostly used objective functions affect each other and how they are affected by various constraints. A mixed integer programming model was established as the solution method of the study, and sensitivity analyzes were performed by creating a simple interface for the results obtained. Since the handled problem is in the NP-hard class, heuristic methods have been applied for large-sized data sets. In this context, six different neighborhood search heuristics were compared for all objective functions, and it was then analyzed which neighborhood search heuristic worked better for which objective function. Sensitivity analyzes were carried out by examining the feasible solutions obtained with the developed algorithm.

Keywords

Parallel Machine Scheduling, Sequence Dependent Setup Times, Mixed Integer Programming Model, Neighborhood Search Heuristics.

Project Number

1919B012112285

FARKLI PERFORMANS KRİTERLERİ ALTINDA PARALEL MAKİNE ÇİZELGELEME PROBLEMİ

Abstract

Üretim planlama faaliyetleri arasında oldukça önemli bir yere sahip olan paralel makine çizelgeleme problemi, işlerin hangi kaynaklar kullanılarak üretileceğinin ve hangi makineye hangi sırada atanacağının belirlenmesidir. Üretim ortamında kaynakların aktif kullanımı ve müşteri memnuniyeti sağlama gibi amaçları gerçekleştirmek, işlerin çizelgelenmesinin iyi bir şekilde yapılıp yapılmaması ile ilgili olmasının yanı sıra amaç fonksiyonu seçimi ile de doğrudan ilişkilidir. Bu çalışmada ele alınan çizelgeleme probleminde, özdeş olmayan paralel makineler, makine ve işlerin hazırlık zamanları ve işler arasındaki sıra bağımlı ayar zamanları düşünülmüştür. Çalışmada, literatürde sıkça yer alan ve firmalar/araştırmacılar tarafından optimize edilmeye çalışılan amaç fonksiyonlarının birbirlerini nasıl etkilediği ve çeşitli kısıtlardan nasıl etkilendiği analiz edilerek literatüre katkı sağlanması hedeflenmiştir. Çalışmanın çözüm yöntemi olarak karma tamsayılı programlama modeli kurulmuş, elde edilen sonuçlar için basit bir ara yüz oluşturularak duyarlılık analizleri yapılmıştır. Ele alınan problemin NP-zor sınıfında bulunması sebebiyle büyük boyutlu veri setleri için sezgisel yöntemlere başvurulmuştur. Bu kapsamda altı farklı komşuluk arama sezgiseli kullanılarak sezgisel yöntemlerin sonuçları tüm amaç fonksiyonları için karşılaştırılmış olup, hangi komşuluk arama sezgiselinin hangi amaç fonksiyonu için daha iyi çalıştığı analiz edilmiştir. Geliştirilen algoritma ile elde edilen olurlu çözümler incelenerek amaç fonksiyonlarının duyarlılık analizleri gerçekleştirilmiştir.

Keywords

Paralel Makine Çizelgeleme, Sıra Bağımlı Ayar Süreleri, Karma Tamsayılı Programlama Modeli, Komşuluk Arama Sezgiseli

Supporting Institution

TÜBİTAK

Project Number

1919B012112285

Thanks

2021/2 başvuru dönemi 2209-A Üniversite Öğrencileri Araştırma Projeleri Destekleme Programı kapsamında projemizi destekleyen TÜBİTAK'a teşekkürlerimizi sunarız.

References

• Afzalirad, M. ve Rezaeian, J., 2016. Resource-Constrained Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, Precedence Constraints And Machine Eligibility Restrictions. Computers and Industrial Engineering, 98, 40–52. doi:10.1016/j.cie.2016.05.020
• Akyol, E. ve Saraç, T., 2017. Paralel Makina Çizelgeleme Problemi için bir Karma Tamsayılı Programlama Modeli: Ortak Kaynak Kullanımı, A Mix Integer Programming Model for Parallel Machine Scheduling Problem: Using Shared Resource. Gazi Üniversitesi Fen Bilimleri Dergisi, 5(3), 109–126.
• Alcan, P. ve Balişgil, H., 2012. A Genetic Algorithm Application Using Fuzzy Processing Times İn Non-İdentical Parallel Machine Scheduling Problem. Advances in Engineering Software, 45(1), 272–280. doi:10.1016/j.advengsoft.2011.10.004
• Bektur, G. ve Saraç, T., 2016. Iki Paralel Enjeksiyon Makinasinin Kreyn Kisiti Altinda Çizelgelenmesi. Journal of the Faculty of Engineering and Architecture of Gazi University, 31(4), 903–911. doi:10.17341/gazimmfd.278445
• Berthier, A.., Yalaoui a, A.., Chehade a, H.., Yalaoui a, F.., Amodeo a, L.. & Bouillot, C.. (2022). Unrelated parallel machines scheduling with dependent setup times in textile industry. Computers & Industrial Engineering, 174. https://doi.org/10.1016/j.cie.2022.108736
• Croce, D., T’kindt, V. & Ploton, O., 2021. Parallel machine scheduling with minimum number of tardy jobs: Approximation and exponential algorithms. Mathematics and Computation, 397. https://doi.org/10.1016/j.amc.2020.125888
• Çevi̇kcan, E., Durmuşoğlu, M. B. ve Baskak, M., 2009. Paralel Makinalarda Ürün Tasarımı Özellikleri İle İş Çizelgelemenin Bütünleştirilmesi. Endüstri Mühendisliği Dergisi, 4(22), 13–34.
• Eren T,Güner E., 2002. Tek ve paralel makinalı problemlerde çok ölçütlü çizelgeleme problemleri için bir literatür taraması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 17(4), 37 - 69.
• Eren, T., 2012. Makine-Bağımlı Bozulma Etkili Paralel Makineli Çizelgelemede Toplam Yüklemeyi Minimize Etme. International Journal of Engineering Research and Development, 4(1), 22–24.
• Eren, T. ve Güner, E., 2006. Paralel Makineli Çizelgelemede Toplam Tamamlanma Zamanı ve Maksimum Gecikmenin Enküçüklenmesi. J. Fac.Eng.Arch. Selcuk Univ, 21, 1–2.
• Ertem, M., Özçelik, F. ve Saraç, T., 2021. Stokastik İlişkisiz Paralel Makine Çizelgeleme Problemi için bir Matematiksel Model. European Journal of Science and Technology, (29), 278–283. doi:10.31590/ejosat.1017475
• Karabulut, M. A. ve Saraç, T., 2019. Kapasite Kısıtlı Esnek Atölye Tipi Çizelgeleme Problemi İçin Üç Aşamalı Bir Çözüm Yaklaşımı Ve Bir İşletmede Uygulanması. Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi, 27(3), 233–241. doi:10.31796/ogummf.613268
• Kaya, S. ve Fığlalı, N., 2016. Çok Amaçlı Optimizasyon Problemlerinde Pareto Optimal Kullanımı. Social Siences Research Journal, 5(2), 9-18, ISSN: 214775237
• Kaya, S., & Karaçizmeli, İ.H., 2018. Hazırlık Zamanlı Ortak Teslim Tarihli Özdeş Paralel Makine Çizelgeleme Problemlerinin Çok Amaçlı Çözümü, Harran Üniversitesi Mühendislik Dergisi, 3(3): 205-213.
• Kılıç, M. (2021). Bir tekstil firmasının boyahane bölümünde paralel makine çizelgeleme problemi için bir matematiksel model önerisi ve farklı çizelgeleme kurallarının karşılaştırılması. Necmettin Erbakan Üniversitesi, Fen Bilimleri Enstitüsü Endüstri Mühendisliği Anabilim Dalı, Konya
• Lee, J.H., Yu, J.M. & Lee, D.H., 2013. A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness. Int J Adv Manuf Technol 69, 2081–2089. https://doi.org/10.1007/s00170-013-5192-6
• Lenstra, J.K.., Kan, A.H.G. Rinnooy. & Brucker, P., 1977. Complexity of Machine Scheduling Problems. Annals of Discrete Mathematics, 1, 343-362. https://doi.org/10.1016/S0167-5060(08)70743-X
• Lin, Y. K. ve Hsieh, F. Y., 2014. Unrelated Parallel Machine Scheduling With Setup Times And Ready Times. International Journal of Production Research, 52(4), 1200–1214. doi:10.1080/00207543.2013.848305
• Mensendiek, A., Gupta, Jatinder N.D. & Herrmann, J., 2015. Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness. European Journal of Operational Research, 243(2), 514-522. https://doi.org/10.1016/j.ejor.2014.12.002
• Mokotoff, E. ve Chretienne, P., 2002. A Cutting Plane Algorithm For The Unrelated Parallel Machine Scheduling Problem. European Journal of Operational Research, 141(3), 515–525. doi:10.1016/S0377-2217(01)00270-3
• Najat, A., Yuan, C., Gursel, S. & Tao, Y., 2019. Minimizing the Number of Tardy Jobs on Identical Parallel Machines Subject to Periodic Maintenance. Procedia Manufacturing, 38, 1409-1416. https://doi.org/10.1016/j.promfg.2020.01.147
• Pinedo, M. L., 2002. Scheduling: Theory, Algorithms, and Systems. New Jersey, USA, Prentice Hall. doi: 10.1007/978-0-387-78935-4
• Saraç, T., & Özçelik, F., 2023. A matheuristic algorithm for multi-objective unrelated parallel machine scheduling problem Çok amaçli ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma. Journal of the Faculty of Engineering and Architecture of Gazi University , vol.38, no.3, 1953-1966.
• Sarıçiçek, İ., 2018. Özdeş olmayan paralel makina çizelgeleme problemlerinin çözümü için bir karar destek sistemi. Pamukkale University Journal of Engineering Sciences, 24(1), 108–116. doi:10.5505/pajes.2017.48658
• Skutella, M., Sviridenko, M. ve Uetz, M., 2016. Unrelated Machine Scheduling With Stochastic Processing Times. Mathematics of Operations Research, 41(3), 851–864. doi:10.1287/moor.2015.0757
• Türker, A. K. ve Çağrı, S., 2011. Sıra Bağımlı Hazırlık Operasyonları İçin Tek Ekipli Paralel Makinalarda Çizelgeleme Problemine Karma Yaklaşım. Gazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi, 26(4), 731–740.
• Vallada, E., Ruiz, R. ve Framinan, J. M., 2015. New Hard Benchmark For Flowshop Scheduling Problems Minimising Makespan. European Journal of Operational Research, 240(3), 666–677. doi:10.1016/j.ejor.2014.07.033
• Yang, S. J., 2013. Unrelated Parallel-Machine Scheduling With Deterioration Effects And Deteriorating Multi-Maintenance Activities For Minimizing The Total Completion Time. Applied Mathematical Modelling, 37(5), 2995–3005. doi:10.1016/j.apm.2012.07.029
• Yeh, W., Lai, P., Lee, W. & Chuang, M., 2014. Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effects. Information Sciences, 269, 142-158. https://doi.org/10.1016/j.ins.2013.10.023