Metaheuristics for the Permutation Flow Shop Problems

Abstract

Bu tezde, sıra bağımlı hazırlık süreli permütasyon akış tipi çizelgeleme probleminin iki tane farklı varyasyonu ele alınmıştır. İlk olarak sıra bağımlı hazırlık süreli permütasyon akış tipi çizelgeleme probleminde tamamlanma süresinin en iyilenmesi çalışılmıştır. Bu problem için yeni bir yenilemeli açgözlü algoritma ve yeni yerel arama algoritması geliştirilmiştir. Yeni yerel arama algoritmasında araya sokma ve karşılıklı yer değiştirme komşulukları kullanılmaktadır. Karşılıklı yer değiştirme komşuluğunun hesaplama zamanını azaltabilmek için Taillard'ın araya sokma komşuluğu hesaplama yönteminden esinlenerek bir hızlandırma yöntemi geliştirilmiştir. Yeni geliştirilen bu hızlandırma yöntemi karşılıklı yer değiştirme komşuluğunun hesaplanma süresini ortalama olarak yüzde elli oranında azaltmaktadır. Geliştirilen hızlandırma yöntemini kullanan yenilemeli açgözlü algoritma literatürde kullanılan bir test kümesindeki problemler için çalıştırılmış ve sonuç olarak bilinen en iyi 480 sonuçtan 250 tanesi için yeni en iyi sonuç bulunmuştur. Tez kapsamında ikinci olarak sıra bağımlı hazırlık süreli permütasyon akış tipi çizelgeleme probleminde akış süresi en iyileme çalışılmıştır. Literatürde bu problem ilk defa çalışılmıştır. Sıra bağımlı hazırlık süresi olmayan NEH_DD ve LR sezgisel algoritmaları ve karşılıklı yer değiştirme ve araya sokma komşulukları için hızlandırma yöntemleri bu probleme uyarlanmıştır. Birden fazla sezgi ötesi algoritma geliştirilmiş ve test kümesindeki problemler için çalıştırılmıştır. Tüm algoritmaların başarım sonuçları karşılaştırılmış ve sonuçlar sunulmuştur.

In this study, two variants of permutation flow shop scheduling problem with sequence dependent setup times are considered. The first problem studied in this thesis is the permutation flow shop problem with sequence dependent setup times under makespan criterion. A new iterated greedy algorithm and a new local search algorithm is developed for this problem. The new local search includes insertion neighborhood and swap neighborhood. A new speed up technique is developed to reduce the cost of the swap neighborhood search, which is inspired from Taillard's well-known speed-up method for the insertion neighborhood. The developed speed up technique can save fifty percent CPU time in average. The developed iterated greedy algorithm utilizing the new swap speed-up method is tested on the benchmark instances from the literature and new best-known solutions are found for 250 out of 480 problem instances. The second problem considered is the permutation flow shop scheduling problem with sequence dependent setup times under total flow time criterion. This problem is studied for the first time in the literature to best of our knowledge. NEH_EDD and LR heuristics as well as speed-up methods for problems without the sequence dependent setup times for insertion and swap neighborhoods are adapted to this problem. Several metaheuristics are developed and executed on a benchmark set. The performances of the developed algorithms are compared and the results are presented.