Bi-objective no-wait permutation flowshop scheduling problems

Abstract

Permütasyon akış tipi çizelgeleme problemlerinin literatür incelenmesinde matematiksel modellerin ve sezgisel yaklaşımların yaygın olarak kullanılmakta olduğu görülmüştür. Ancak, makineler arasındaki işler için bekleme süresine izin verilmeyen bir permütasyon akış tipi çizelgeleme problemi çeşidi olan beklemesiz permütasyon akış tipi çizelgeleme problemleri alanında daha az çalışma yapılmıştır. Bu tez, beklemesiz permütasyon akış tipi çizelgeleme problemi için hem karma-tamsayılı doğrusal programlama hem de kısıt programlama model formülasyonunu, (i) iş üretim süresi, (ii) toplam akış süresi ve (iii) toplam gecikme gibi çeşitli amaçlar altında önermektedir. Ek olarak, enerji verimli çizelgeleme son zamanlarda oldukça popüler hale gelmiştir, çünkü yüksek hacimli imalattan kaynaklanan enerji tüketimi çoğu sektörde karşılaşılan en başta gelen problemdir. Bu nedenle, hem karma-tamsayılı programlama hem de kısıt programlama model formülasyonları, iki-amaçlı beklemesiz permütasyon akış tipi çizelgeleme problemleri üzerinde, yine (i) iş üretim süresini, (ii) toplam akış süresini ve (iii) toplam gecikmeyi ayrı ayrı en aza indirmek amacıyla çalışılmıştır. Bu tezde, iki-amaçlı beklemesiz permütasyon akış tipi çizelgeleme problemlerinin toplam enerji tüketimini ikinci bir amaç olarak kullandığı kabul edilmiştir. Ayrıca, ilk amaç fonksiyonunda bile NP-Hard sınıfında olan bu problem kapsamında, iki-amaçlı beklemesiz permütasyon akış tipi çizelgeleme problemleri için yeni bir çok-amaçlı ayrık yapay arı kolonisi algoritması (MO-DABC), bir geleneksel çok-amaçlı genetik algoritma (MO-GA) ve bir çok-amaçlı genetik algoritma çeşidi (MO-GALS) önerilmiştir. Sonuç olarak, iki amaçlı beklemesiz permütasyon akış tipi çizelgeleme problemleri için kapsamlı bir karşılaştırmalı metasezgisel analiz yapılmıştır. Bu nedenle, bu tez, beklemesiz permütasyon akış tipi çizelgeleme problemi literatürüne sadece tek-hedefli problemler için değil aynı zamanda iki-hedefli enerji verimli çizelgeleme problemleri için çeşitli yeni matematiksel modeller ve metasezgisel yöntemler sağlayarak katkıda bulunmaktadır.

In the field of permutation flowshop scheduling problems, there is a vast literature covering mathematical models and heuristics approaches. However, less work has been reported in the field of no-wait permutation flowshop scheduling problems, a variant of permutation flow shop scheduling problem where the waiting time for the jobs between the machines is not allowed. This thesis proposes both mixed-integer linear programming and constraint programming model formulations for no-wait permutation flowshop scheduling problem under various objectives such as (i) makespan, (ii) total flow time and (iii) total tardiness. Moreover, energy-efficient scheduling has become very popular recently since energy consumption in high volume manufacturing is the leading essential difficulty in most industries. Both mixed-integer programming and constraint programming model formulations are developed in this thesis on the energy-efficient (bi-objective) no-wait permutation flowshop scheduling problems with the objective of minimizing (i) makespan, (ii) total flow time and (iii) total tardiness, separately. The bi-objective no-wait permutation flowshop scheduling problems treat the total energy consumption as a second objective in this study. Furthermore, due to the NP-hardness nature of the first objective of the problem, a novel multi-objective discrete artificial bee colony algorithm (MO-DABC), a traditional multi-objective genetic algorithm (MO-GA) and a variant of multi-objective genetic algorithm (MO-GALS) are proposed for the bi-objective no-wait permutation flowshop scheduling problems. Consequently, a comprehensive comparative metaheuristic analysis is carried out. Hence, this thesis contributes to the literature of no-wait permutation flowshop scheduling problem for not only single-objective problems but also the bi-objective problems which consider energy efficient scheduling by ensuring various new mathematical models and metaheuristics.