Kullanılamayan Zaman Dilimlerinin ve Sıra Bağımlı Hazırlık Sürelerinin Olduğu Paralel Makina Çizelgeleme Problemi

Öz

Makine çizelgeleme problemlerinde tüm makineler daima kullanılabilir durumda değildirler. Planlı bakım, öğle yemeği ve dinlenme molaları gibi nedenlerle periyodik olarak kesintilere uğrayabilmektedirler. Ancak literatürde genellikle bu durum göz ardı edilmektedir. Bu çalışmada kullanılamayan zaman dilimlerinin ve sıra bağımlı hazırlık sürelerinin olduğu ilişkisiz paralel makine çizelgeleme problemi ele alınmıştır. Ele alınan problem için bir matematiksel model geliştirilmiştir. Önerilen matematiksel modelin performansı rassal türetilen test problemleri kullanılarak gösterilmiştir. Kullanılamayan zaman dilimlerinin dikkate alınmasıyla son için tamamlanma zamanlarında ortalama %5,29’luk bir azalma sağlanmıştır.

Anahtar Kelimeler

• İlişkisiz paralel makine çizelgeleme problemi
• kullanılamayan zaman dilimleri
• sıra bağımlı hazırlık süreleri

Parallel Machine Scheduling Problem with Unavailable Time Periods and Sequence Dependent Setup Times

Abstract

In machine scheduling problems, not all machines are always available. They may be interrupted periodically for reasons such as planned maintenance, lunch and rest breaks. However, this situation is often overlooked in the literature. In this study, unrelated parallel machine scheduling problem with unavailable time periods and sequence dependent setup times is discussed. A mathematical model has been developed for the considered problem. The performance of the proposed mathematical model is demonstrated using randomly generated test problems. By taking into account the unavailable time periods, an average of 5.29% reduction was achieved in the makespan.

Keywords

• Unrelated parallel machine scheduling problem
• unavailable time periods
• sequence dependent setup times

References

1. [1] Low C., Ji M., Hsu C-J., Su C-T, Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance, Applied Mathematical Modelling, 34 (2010) 334–342.
2. [2] Perez-Gonzalez P., Framinan J.M., Single machine scheduling with periodic machine availability, Computers & Industrial Engineering, 123 (2018) 180–188.
3. [3] Ji M., Cheng TCE, Scheduling resumable simple linear deteriorating jobs on a single machine with an availability constraint to minimize makespan, Computers & Industrial Engineering, 59 (2010) 794–798.
4. [4] Rapine C., Brauner N., Finke G., Lebacque V., Single machine scheduling with small operator-non-availability periods, Journal of Scheduling, 15 (2012) 127–139.
5. [5] Shabtay D., Zofi, M., Single machine scheduling with controllable processing times and an unavailability period to minimize the makespan, International Journal of Production Economics, 198 (2018) 191–200.
6. [6] Shabtay D., Single-machine scheduling with machine unavailability periods and resource dependent processing times, European Journal of Operational Research, 296 (2022) 423–439.
7. [7] Mor B., Mosheiov G., Heuristics for scheduling problems with an unavailability constraint and position-dependent processing times, Computers & Industrial Engineering, 62 (2012) 908–916.
8. [8] Kacem I., Chu C., Souissi A., Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times, Computers & Operations Research, 35 (2008) 827 – 844.

9. [9] Khoudi A., Berrichi A., Minimize total tardiness and machine unavailability on single machine scheduling problem: bi-objective branch and bound algorithm, Operational Research, 20: (2020) 1763–1789.
10. [10] Laalaoui Y., M’Hallah R., A binary multiple knapsack model for single machine scheduling with machine unavailability, Computers & Operations Research, 72 (2016) 71–82.
11. [11] Low C., Li R-K, Wu G-H, Minimizing total earliness and tardiness for common due date single-machine scheduling with an unavailability interval, Mathematical Problems in Engineering, (2016) Article ID 6124734
12. [12] Mashkani O., Moslehi G., Minimising the total completion time in a single machine scheduling problem under bimodal flexible periodic availability constraints, International Journal of Computer Integrated Manufacturing, 29:3 (2016) 323-341.
13. [13] Mor B., Shapira D., Single machine scheduling with non-availability interval and optional job rejection, Journal of Combinatorial Optimization, (2022) In press
14. [14] Mosheiov G., Oron D. Shabtay D., Minimizing total late work on a single machine with generalized due-dates, European Journal of Operational Research, 293 (2021) 837–846.
15. [15] Su L-H, Wang H-M, Minimizing total absolute deviation of job completion times on a single machine with cleaning activities, Computers & Industrial Engineering, 103 (2017) 242–249.
16. [16] Yazdani M., Khalili S.M., Babagolzadeh M., Jolai F., A single-machine scheduling problem with multiple unavailability constraints: A mathematical model and an enhanced variable neighborhood search approach, Journal of Computational Design and Engineering, 4 (2017) 46–59.
17. [17] Yin Y., Xu J., Cheng T. C. E., Wu C-C, Wang D-J., Approximation schemes for single-machine scheduling with a fixed maintenance activity to minimize the total amount of late work, Naval Research Logistics, 63 (2016) 172–183.
18. [18] Bülbül K., Kedad-Sidhoum S., Sen H., Single-machine common due date total earliness/tardiness scheduling with machine unavailability, Journal of Scheduling, 22 (2019) 543–565.
19. [19] Al-Shayea A.M., Saleh M. , Alatefi M., Ghaleb M., Scheduling two identical parallel machines subjected to release times, Delivery Times and Unavailability Constraints, Processes, 8 (2020) 1025.
20. [20] Berrichi A., Yalaoui F., Efficient bi-objective ant colony approach to minimize total tardiness and system unavailability for a parallel machine scheduling problem, International Journal of Advanced Manufacturing Technology, 68 (2013) 2295–2310.
21. [21] Dong M., Parallel machine scheduling with limited controllable machine availability, International Journal of Production Research, 51:8 (2013) 2240-2252.
22. [22] Fu B., Huo Y., Zhao H. 2011, Approximation schemes for parallel machine scheduling with availability constraints, Discrete Applied Mathematics, 159 (2011) 1555–1565.
23. [23] Huo Y., Parallel machine makespan minimization subject to machine availability and total completion time constraints, Journal of Scheduling, 22 (2019) 433–447.
24. [24] Moradi E., Zandieh M, Minimizing the makespan and the system unavailability in parallel machine scheduling problem: a similarity-based genetic algorithm, International Journal of Advanced Manufacturing Technology, 51 (2010) 829–840.
25. [25] Nessah R., Chu C., Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods, Annals of Operations Research, 181 (2010) 359–375.
26. [26] Kaabi J., Harrath Y. Scheduling on uniform parallel machines with periodic unavailability constraints, International Journal of Production Research, 57:1 (2019) 216-227.
27. [27] Wang S., Liu M., Multi-objective optimization of parallel machine scheduling integrated with multi-resources preventive maintenance planning, Journal of Manufacturing Systems, 37 (2015) 182–192.