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ı
Yıl: 2021 Cilt: 36 Sayı: 3 Sayfa Aralığı: 1539 - 1549 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.806641 İndeks Tarihi: 10-11-2022
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. Bununla birlikte, 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 olması 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örevlerini yerine getiremeyeceği varsayımı altında ele alınmıştır. Ayrıca işler arası sıra bağımlı kurulum 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 çözümünde Np-zor yapısından dolayı tabu arama (TA) algoritması önerilmiştir. Deneysel sonuçlar, önerilen TA algoritmanın iyi bir performansa sahip olduğunu göstermektedir.
Anahtar Kelime: 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 be unavailable 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 available and they will not be able to perform some tasks. In addition, sequence-dependent setup times between tasks were also taken into account. The objective function is to minimize total tardiness and earliness. 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 (TS) algorithm is proposed. Experimental results show that the proposed TS algorithm has a good performance.
Anahtar Kelime: Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
- 1. Mokotoff E., An exact algorithm for the identical parallel machine scheduling problem, European Journal of Operational Research, 152 (3), 758-769, 2004.
- 2. Lin Y.K., Pfund M.E., Fowler J.W., Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems, Computers & Operations Research, 38 (6), 901-916, 2011.
- 3. Mcnaughton R., Scheduling with deadlines and loss functions, Management Science, 6 (1), 1-12, 1959.
- 4. Türker A.K., Sel Ç., A hybrid approach on single server parallel machines scheduling problem with sequence dependent setup times, Journal of the Faculty of Engineering & Architecture of Gazi University, 26 (4), 731-740, 2011.
- 5. Sun K., Li H., Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines, International Journal of Production Economics, 124 (1), 151-158, 2010.
- 6. Xu D., Cheng Z., Yin Y., Li H., Makespan minimization for two parallel machines scheduling with a periodic availability constraint, Computers & Operations Research, 36 (6), 1809-1812, 2009.
- 7. Zhao C., Ji M., Tang H., Parallel-machine scheduling with an availability constraint, Computers & Industrial Engineering, 61 (3), 778-781, 2011.
- 8. Bektur G., Saraç T., 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, 103, 46-63, 2019.
- 9. Lee C.Y.,Chen Z.L., Scheduling jobs and maintenance activities on parallel machines, Naval Research Logistics (NRL), 47(2), 145-165, 2000.
- 10. Sheen G.-J.,Liao L.-W.,Lin C.-F., Optimal parallel machines scheduling with machine availability and eligibility constraints, The International Journal of Advanced Manufacturing Technology, 36 (1-2), 132- 139, 2008
- 11. Huo Y., Zhao H., Total completion time minimization on multiple machines subject to machine availability and makespan constraints, European Journal of Operational Research, 243 (2), 547-554, 2015.
- 12. Ezugwu A.E., Enhanced symbiotic organisms search algorithm for unrelated parallel machines manufacturing scheduling with setup times, Knowledge-Based Systems, 172, 15-32, 2019.
- 13. Yin Y., Wang Y., Cheng T.C.E., Liu W., Li J., Parallel- machine scheduling of deteriorating jobs with potential machine disruptions, Omega, 69, 17-28, 2017.
- 14. Chen C.-L., Chen C.-L., Hybrid metaheuristics for unrelated parallel machine scheduling with sequence- dependent setup times, The International Journal of Advanced Manufacturing Technology, 43 (1-2), 161, 2009.
- 15. Wang M., Pan G., A Novel Imperialist Competitive Algorithm With Multi-Elite Individuals Guidance for Multi-Object Unrelated Parallel Machine Scheduling Problem, IEEE Access, 7, 121223-121235, 2019.
- 16. Glover F., Tabu search—part I, ORSA Journal on computing, 1(3), 190-206, 1989
- 17. Solimanpur M., Elmi A., A tabu search approach for cell scheduling problem with makespan criterion, International Journal of Production Economics, 141 (2), 639-645, 2013.
- 18. Solimanpur M., Elmi A., A tabu search approach for group scheduling in buffer-constrained flow shop cells, International Journal of Computer Integrated Manufacturing, 24 (3), 257-268, 2011.
- 19. Güner E., Altınparmak F., A heuristic approach for the secondary criterion scheduling problem on a single machine, Journal of the Faculty of Engineering & Architecture of Gazi University, 18 (3), 27-42, 2003.
- 20. Radhakrishnan S.,Ventura J.A., Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times, International Journal of Production Research, 38 (10), 2233-2252, 2000.
| APA | Furugi A (2021). 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ı. , 1539 - 1549. 10.17341/gazimmfd.806641 |
| Chicago | Furugi Ahad 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ı. (2021): 1539 - 1549. 10.17341/gazimmfd.806641 |
| MLA | Furugi Ahad 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ı. , 2021, ss.1539 - 1549. 10.17341/gazimmfd.806641 |
| AMA | Furugi A 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ı. . 2021; 1539 - 1549. 10.17341/gazimmfd.806641 |
| Vancouver | Furugi A 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ı. . 2021; 1539 - 1549. 10.17341/gazimmfd.806641 |
| IEEE | Furugi A "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ı." , ss.1539 - 1549, 2021. 10.17341/gazimmfd.806641 |
| ISNAD | Furugi, Ahad. "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ı". (2021), 1539-1549. https://doi.org/10.17341/gazimmfd.806641 |
| APA | Furugi A (2021). 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ı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36(3), 1539 - 1549. 10.17341/gazimmfd.806641 |
| Chicago | Furugi Ahad 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ı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 36, no.3 (2021): 1539 - 1549. 10.17341/gazimmfd.806641 |
| MLA | Furugi Ahad 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ı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.36, no.3, 2021, ss.1539 - 1549. 10.17341/gazimmfd.806641 |
| AMA | Furugi A 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ı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2021; 36(3): 1539 - 1549. 10.17341/gazimmfd.806641 |
| Vancouver | Furugi A 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ı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2021; 36(3): 1539 - 1549. 10.17341/gazimmfd.806641 |
| IEEE | Furugi A "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ı." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 36, ss.1539 - 1549, 2021. 10.17341/gazimmfd.806641 |
| ISNAD | Furugi, Ahad. "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ı". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 36/3 (2021), 1539-1549. https://doi.org/10.17341/gazimmfd.806641 |
