Comparison of Two Matheuristic Algorithms for the Flexible Job-Shop Scheduling Problem with Lot-Streaming

Abstract

In flexible job-shop scheduling problems (FJSP), splitting into sub-lots of jobs and performing them on different machines enables businesses to satisfy customer demands more quickly and to use their machines more efficiently. In this study, the FJSP with lot-streaming is discussed. The objective function is to minimize the makespan. To solve the considered problem, matheuristic simulated annealing algorithm (MSA) and matheuristic variable neighborhood search algorithm (MVNS) are proposed. In the problem addressed, it is necessary to determine which machines the jobs will be assigned to, in which sequence they will be processed, and what the sub-lot sizes will be. The proposed algorithms determine the sub-lot sizes by the mathematical model. In this way, the advantage of heuristic algorithms to quickly search the solution space and the advantage of mathematical models to obtain the optimum solution in sub-problems are considered together. To show the performance of the proposed algorithms, randomly generated test problems and a mathematical model taken from the literature are used. Additionally, the performances of MTB and MDKA are compared.

Keywords

• Lot- Streaming
• Flexible Job Shop Scheduling
• Matheuristic Algorithm
• Simulated Annealing
• Variable Neighborhood Search

İşlerin Bölünebildiği Esnek Atölye Çizelgeme Problemi için İki Matsezgisel Algoritmanın Karşılaştırılması

Abstract

Esnek atölye çizelgeme problemlerinde (EAÇP) işlerin alt partilere bölünerek farklı makinelerde gerçekleştirilmesi, işletmelerin müşteri taleplerini daha hızlı bir şekilde karşılamasını ve makinelerin de daha verimli kullanılmasını sağlamaktadır. Bu çalışmada, işlerin bölünmesine izin verilen EAÇP problemi ele alınmıştır. Amaç, son işin tamamlanma zamanının enküçüklenmesidir. Problemin çözümü için hem matsezgisel tavlama benzetimi algoritması (MTB) hem de matsezgisel değişken komşuluk arama algoritması (MDKA) önerilmiştir. Ele alınan problemde işlerin hangi makinelere atanacağı, hangi sırada işleneceği ve alt parti büyüklüklerinin ne olacağının belirlenmesi gerekmektedir. Önerilen algoritmalarda alt parti büyüklüklerinin ne olacağı matematiksel model ile belirlenmektedir. Böylelikle sezgisel algoritmaların hızlı bir şekilde çözüm uzayında arama yapması avantajı ile matematiksel modellerin alt problemlerdeki en iyi çözümü elde etmesi avantajı bir araya getirilmiştir. Önerilen algoritmaların performansını gösterebilmek için rassal türetilen test problemleri ve literatürden alınan bir matematiksel model kullanılmıştır. Ayrıca MTB’nin ve MDKA’nın performansları da kıyaslanmıştır.

Keywords

• İş Bölünmesi
• Esnek Atölye Çizelgeleme
• Matsezgisel Algoritma
• Tavlama Benzetimi
• Değişken Komşuluk Arama

References

1. [1] J. W. Stevenson, Production/Operations Management, Irwin, 1996.
2. [2] H. Liu, A. Abraham ve Z. Wang, "A multi-swarm approach to multi-objective flexible job-shop scheduling problems", Fundamenta Informaticae, cilt 95, sayı 4, s. 465-489, 2009, doi: 10.3233/FI-2009-160.
3. [3] H. P. Zhang, J. H. Ye, X. P. Yang, N. W. Muruve ve J. T. Wang, “Modified binary particle swarm optimization algorithm in lot-splitting scheduling involving multiple techniques”, International Journal of Simulation Modelling, cilt 17, sayı 3, s. 534-542, Eylül 2018, doi: 10.2507/IJSIMM17(3)CO13.
4. [4] D. Lei ve X. Guo, "Scheduling job shop with lot streaming and transportation through a modified artificial bee colony", International Journal of Production Research, cilt 51, sayı 16, s. 4930-4941, Ağustos 2013, doi: 10.1080/00207543.2013.784404.
5. [5] C. H. Liu, L. S. Chen ve P. S. Lin, “Lot streaming multiple jobs with values exponentially deteriorating over time in a job-shop environment”, International Journal of Production Research, cilt 51, sayı 1, s. 202–214, 2013, doi: 10.1080/00207543.2012.657255.
6. [6] X. L. Xu, L. Li, L. X. Fan, J. Zhang, X. H. Yang ve W. L. Wang, “Hybrid discrete differential evolution algorithm for lot splitting with capacity constraints in flexible job scheduling”, Mathematical Problems in Engineering, 2013, doi: 10.1155/2013/986218.
7. [7] F. Defersha ve M. Chen, “Jobshop lot streaming with routing flexibility, sequence-dependent setups, machine release dates and lag time”, International Journal of Production Research, cilt 50, sayı 8, s. 2331–2352, 2012, doi: 10.1080/00207543.2011.574952.
8. [8] D. Rooyani ve F. Defersha, “A two-stage multi-objective genetic algorithm for a flexible job shop scheduling problem with lot streaming”, Algorithms, cilt 15, sayı 7, Temmuz 2022, doi: 10.3390/a15070246.

9. [9] F. Daneshamooz, P. Fattahi ve S. M. H. Hosseini, “Scheduling in a flexible job shop followed by some parallel assembly stations considering lot streaming”, Engineering Optimization, cilt 54, sayı 4, s. 614-633, Nisan 2022, doi: 10.1080/0305215X.2021.1887168.
10. [10] F. Abderrabi vd., “Flexible job shop scheduling problem with sequence dependent setup time and job splitting: Hospital catering case study”, Applied Sciences-Basel, cilt 11, sayı 4, Şubat 2021, doi: 10.3390/app11041504.
11. [11] J. M. Novas, “Production scheduling and lot streaming at flexible job-shops environments using constraint programming”, Computers & Industrial Engineering, cilt 136, s. 252-264, Ekim 2019, doi: 10.1016/j.cie.2019.07.011.
12. [12] A. Bozek ve F. Werner, “Flexible job shop scheduling with lot streaming and sublot size optimisation”, International Journal of Production Research, cilt 56, sayı 19, s. 6391-6411, Ekim 2017, doi: 10.1080/00207543.2017.1346322.
13. [13] J. X. Fan, C. J. Zhang, W. M. Shen ve L. Gao, “A matheuristic for flexible job shop scheduling problem with lot-streaming and machine reconfigurations”, International Journal Of Production Research, cilt 61, sayı 19, s. 6565-6588, Ekim 2022, doi: 10.1080/00207543.2022.2135629.
14. [14] Y. B. Li, Z. P. Yang, L. Wang, H. T. Tang, L. B. Sun ve S. S. Guo, “A hybrid imperialist competitive algorithm for energy-efficient flexible job shop scheduling problem with variable-size sublots”, Computers & Industrial Engineering, cilt 172, Ekim 2022, doi: 10.1016/j.cie.2022.108641.
15. [15] B. Tutumlu ve T. Saraç, “A MIP model and a hybrid genetic algorithm for flexible job-shop scheduling problem with job-splitting”, Computers and Operations Research, cilt 155, Temmuz 2023, doi: 10.1016/j.cor.2023.106222.
16. [16] W. H. T. Meira vd., “Scheduling of a single-source multiproduct pipeline system by a matheuristic approach: Combining simulated annealing and MILP”, Computers & Chemical Engineering, cilt 136, Mayıs 2020, doi: 10.1016/j.compchemeng.2020.106784.
17. [17] N. Mladenovic ve P. Hansen, “Variable neighborhood search”, Pergamon, cilt 24, sayı 11, s. 1097-1100, Kasım 1997, doi: 10.1016/S0305-0548(97)00031-2.
18. [18] P. Hansen ve N. Mladenovic, “J-Means: a new local search heuristic for minimum sum of squares clustering”, Pattern Recognition, cilt 34, sayı 2, s. 405-413, Şubat 2001, doi: 10.1016/S0031-3203(99)00216-2.