Robust genetic algorithm for minimizing makespan in ordered flow shop scheduling

Abstract

Bu çalışma, NP-zor bir optimizasyon problemi olan sıralı (ordered) flow shop çizelgeleme problemini ele almaktadır. Bu özel alt problem üzerine literatürde sınırlı sayıda çalışma bulunmakta olup, yalnızca Khatami ve arkadaşlarının çalışması dikkat çekmektedir. Çalışmada, piramit yapılarını koruyarak çözüm üretebilen yeni bir evrimsel algoritma önerilmiştir. Geliştirilen yöntem, farklı boyutlardaki veri kümeleri üzerinde test edilmiş ve literatürde sıkça kullanılan NEH, Pair-insert ve ILS algoritmaları ile karşılaştırılmıştır. Sonuçların güvenilirliğini artırmak amacıyla, ekleme (insert) ve yer değiştirme (swap) operatörlerini içeren piramit yapısına uyarlanmış bir Tabu Arama algoritması da geliştirilmiştir. Wilcoxon Sıralı İşaret Testi ve Friedman Testi ile yapılan istatistiksel analizler, önerilen genetik algoritmanın piramit yapı ve dışbükeyliği koruma açısından üstün performans sergilediğini göstermiştir. Araştırma sonuçları, sıralı flow shop probleminin çözümünde mevcut yöntemlere kıyasla daha başarılı bir yaklaşım sunulduğunu ortaya koymuştur.

This study addresses the ordered flow shop scheduling problem, a recognized NP-hard optimization challenge with limited dedicated research, notably only by Khatami et al. A novel evolutionary algorithm is proposed to preserve pyramid structures during scheduling, overcoming existing limitations. The method was tested on datasets of various sizes and compared with established algorithms like Pair-insert, NEH, and ILS. To further validate the outcomes, a customized Tabu Search was developed using insert and swap operators. Statistical evaluation with the Friedman Test and Wilcoxon Signed Rank Test confirmed the superiority of the proposed genetic algorithm in maintaining convexity and the pyramidal structure. The outcomes show that the ordered flow shop scheduling problem can be solved more effectively than using current methods.