Metaheuristics for the no-idle permutation flowshop scheduling problem

Abstract

Bu çalışmada, permütasyon akış tipi çizelgeleme probleminin, bekleme zamanlarına izin verilmeyen hali ele alınmıştır. Güçlü bir metasezgisel algoritma olan Genel Değişken Komşu Arama algoritması, dış döngüde ekle ve değiştir operasyonları, iç döngüde ise iteratif açgözlü algoritma ve iteratif bölgesel arama algoritması kullanılmıştır. Sunulan algoritmanın performansı, teknik yazında sunulan 4 farklı algoritmayla sonuçlarının karşılaştırılması ile ölçülmüştür. Karşılaştırma yapılan diğer algoritmalar şunlardır; (1) iteratif açgözlü, (2) değişken iteratif açgözlü, (3) hibrit ayrık farksal evrim algoritması, (4) farksal evrim ile değişken iteratif açgözlü algoritması. Bu algoritmaların performanslarını test etmek için http://soa.iti.es/rruiz sayfasında, Prof. Ruben Ruiz tarafından sunulan örnek problem yapısı kullanılmıştır. Yapılan karşılaştırmalar sonucunda Genel Değişken Komşu Arama algoritmasının, mevcut bilinen en iyi 250 sonucun 85 tanesini iyileştirdiği gözlenmiştir.

In this thesis, a variant of permutation flowshop scheduling problem, where no-idle times are allowed on machines, is considered and a metaheuristic algorithm; a General Variable Neighborhood Search algorithm with insert and swap operations in outer loop and in the inner loop (Variable Neighborhood Descent phase), Iterated Greedy algorithm and Iterated Local Search algorithm is represented. The results of the algorithm are compared to the results with some other algorithms to measure the performance. These algorithms are; (1) an iterated greedy, (2) variable iterated greedy, (3) the hybrid discrete differential evolution and (4) variable iterated greedy algorithm with differential evolution algorithm. The performances of the proposed algorithms are tested on the Prof. Ruben Ruiz? benchmark suite that is presented in http://soa.iti.es/rruiz. Computational results are proposed and concluded as the GVNS algorithm further improved 85 out of 250 current best known solutions. In addition, these conclusions are supported by the paired T-tests and the interval plot.