Solution approaches for multı objective parallel machine scheduling problems

Abstract

Bu çalışmada çok amaçlı paralel makine çizelgeleme problemi ele alınmıştır. Bağımsız paralel makineler ve özdeş olmayan iş dizileri için Ardışık İş Enküçük Tamamlanma Zaman (SJMCT) isimli yeni bir algoritma önerilerek iki amaç eniyilenmiştir. Bu amaçlar; her bir işin sadece tek bir zaman ve makineye atandığı durumdaki enbüyük tamamlanma zamanı ve toplam gecikmenin en küçüklenmesidir. Geliştirilen algoritmanın performansı, küçük boyutlu bir problem (dört makine ve dokuz iş) üzerinden çok kullanılan genel sevk etme kuralları ile karşılaştırılmıştır. Büyük boyutlu problemler için çok amaçlı makine çizelgeleme problemlerindeki karmaşıklıklardan dolayı, Baskın Olmayan Sıralama Genetik Algoritma (NSGA-II) tabanlı ile Güçlü Pareto Evrimsel Algoritma (SPEA-II) tabanlı SJMCT-NSGA-II ve SJMCT-SPEA-II isimli iki yeni melez metasezgisel algoritma Pareto optimal çözümleri elde etmek için önerilmiştir. 272 simülasyon sonucu, geliştirilen algoritmaların etkinliğini göstermektedir. Değişik parametrelerin etkilerini göstermek için iki farklı problem üzerinden simülasyonlar yapılmıştır. Simülasyonlarda iterasyon sayısı ve iş sayısı etkileri araştırılmıştır. Sonuçlar, önerilen SJMCT-SPEA-II algortimasının SJMCT-NSGA-II’den daha iyi performansa sahip olduğunu göstermektedir. Uygun performans ölçülerini seçmeden önce, elde edilen Pareto çözümlerin etkiliğini göstermek için Yayılma ve Mesafe metrikleri de kullanılmıştır. Son olarak, sonuçlar ve gelecek çalışmalar için bazı öneriler de sunulmuştur.