Makine uygunluk kısıtlaması ve sıra bağımlı kurulum süresi ile özdeş olmayan paralel makine çizelgeleme problemi için tabu arama algoritması

Öz

Paralel makine çizelgeleme problemlerinin birçok pratik ve endüstriyel uygulaması olup özellikle son yıllarda birçok araştırmacı tarafından araştırma konusu olmuştur. Ancak, bazen makineler, bakım işlemleri veya makine arızası gibi nedenlerden dolayı belirli bir süre devre dışı kalabilmekteler. Literatürde bu tip kısıtlamaları dikkate alan çalışmaların eksik olduğu bu çalışmanın motivasyon kaynağını oluşturmuştur. Bu çalışmada, özdeş olmayan paralel makine çizelgeleme problemi; makinelerin her zaman hazır olmayacağı ve bazı görevlerin yerine getiremeyeceği varsayımı ile ele alınmıştır. Ayrıca sıra bağımlı hazırlık süreleri de dikkate alınmıştır. Çalışmanın amacı toplam gecikme ve erken teslim sürelerini minimize etmektir. Problem için sunulan karma tam sayılı matematiksel model, GUROBI 9.0 çözücü ile çözülmüştür. Ele alınan problemin Np-zor yapısından dolayı büyük boyutlu problemlerin çözümü için tabu arama algoritması önerilmiştir. Deneysel sonuçlar, önerilen tabu arama algoritmanın iyi bir performansa sahip olduğunu göstermektedir.

Anahtar Kelimeler

• Çizelgeleme
• Özdeş Olmayan Paralel Makineler
• Meta Sezgisel Algoritmalar
• Tabu Arama Algoritması

A tabu search algorithm for the unrelated parallel machine scheduling problem with machine availability constraint and sequence-dependent setup time

Öz

Parallel machine scheduling problems have many practical and industrial applications and have recently been the subject of research by many researchers. However, sometimes machines can often be out of reach for a period of time for reasons such as machine failure and maintenance operations. The lack of studies in the literature considering such restrictions has been the motivation for this study. In this study, the unrelated parallel machine scheduling problem is discussed with the assumption that the machines will not always be ready and that some tasks will not be able to perform. In addition, sequence-dependent setup times were also taken into account. The objective function is to minimize total delays and early delivery times. A mixed integer mathematical model is presented for the problem and solved with the GUROBI 9.0 solver. Due to the NP-hard nature of the addressed problem, a tabu search algorithm is proposed for large scale problems. Experimental results show that the proposed tabu search algorithm has a good performance and efficiency.

Anahtar Kelimeler

• Scheduling
• Unrelated Parallel Machines
• Meta-Heuristic Algorithms
• Tabu Search Algorithm

Kaynakça

1. Mokotoff, E., An exact algorithm for the identical parallel machine scheduling problem. European Journal of Operational Research, 2004. 152(3): p. 758-769.
2. Lin, Y.K., M.E. Pfund, and J.W. Fowler, Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems. Computers & Operations Research, 2011. 38(6): p. 901-916.
3. McNaughton, R., Scheduling with deadlines and loss functions. Management Science, 1959. 6(1): p. 1-12.
4. Türker, A.K. and Ç. Sel, Sıra Bağımlı Hazırlık Operasyonları İçin Tek Ekipli Paralel Makinalarda Çizelgeleme Problemine Karma Yaklaşım. Journal of the Faculty of Engineering & Architecture of Gazi University, 2011. 26(4).
5. Sun, K. and H. Li, Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines. International Journal of Production Economics, 2010. 124(1): p. 151-158.
6. Xu, D., et al., Makespan minimization for two parallel machines scheduling with a periodic availability constraint. Computers & Operations Research, 2009. 36(6): p. 1809-1812.
7. Zhao, C., M. Ji, and H. Tang, Parallel-machine scheduling with an availability constraint. Computers & Industrial Engineering, 2011. 61(3): p. 778-781.
8. Bektur, G. and T. Saraç, A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server. Computers & Operations Research, 2019. 103: p. 46-63.

9. Lee, C.Y. and Z.L. Chen, Scheduling jobs and maintenance activities on parallel machines. Naval Research Logistics (NRL), 2000. 47(2): p. 145-165.
10. Sheen, G.-J., L.-W. Liao, and C.-F. Lin, Optimal parallel machines scheduling with machine availability and eligibility constraints. The International Journal of Advanced Manufacturing Technology, 2008. 36(1-2): p. 132-139.
11. Huo, Y. and H. Zhao, Total completion time minimization on multiple machines subject to machine availability and makespan constraints. European Journal of Operational Research, 2015. 243(2): p. 547-554.
12. Ezugwu, A.E., Enhanced symbiotic organisms search algorithm for unrelated parallel machines manufacturing scheduling with setup times. Knowledge-Based Systems, 2019. 172: p. 15-32.
13. Yin, Y., et al., Parallel-machine scheduling of deteriorating jobs with potential machine disruptions. Omega, 2017. 69: p. 17-28.
14. Chen, C.-L. and C.-L. Chen, Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology, 2009. 43(1-2): p. 161.
15. Wang, M. and G. Pan, A Novel Imperialist Competitive Algorithm With Multi-Elite Individuals Guidance for Multi-Object Unrelated Parallel Machine Scheduling Problem. IEEE Access, 2019. 7: p. 121223-121235.
16. Glover, F., Tabu search—part I. ORSA Journal on computing, 1989. 1(3): p. 190-206.
17. Güner, E. and F. Altınparmak, İki Ölçütlü Tek Makinalı Çizelgeleme Problemi İçin Sezgisel Bir Yaklaşım. Journal of the Faculty of Engineering & Architecture of Gazi University. 18(3).
18. Radhakrishnan, S. and J.A. Ventura, Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times. International Journal of Production Research, 2000. 38(10): p. 2233-2252.