Esnek Atölye Tipi Çizelgeleme Problemi İçin Geliştirilen Sütun Üretme Ve Metasezgisellere Dayalı Algoritmalar

Abstract

Esnek Atölye Tipi Çizelgeleme Problemi (EATP), çözümü zor ve çizelgeleme teorisinde en sık araştırılan konulardan biri olan Atölye Tipi Çizelgeleme Probleminin (ATP) daha genel ve çok daha karmaşık halidir. Genel ATP de operasyonların hangi makinada işleneceği bellidir. Oysa EATP hem operasyonların hangi makinaya atanacağı kararını, hem de makinalardaki iş sırası kararını içerir. Tezde EATP için, en düşük yayılma süresini veren çizelgeyi bulmayı hedefleyen iki yeni yöntem geliştirilmiştir. İlk yöntem çalışma kapsamında araştırılan EATP literatüründe kullanılmamış olan sütun üretme (SÜ) algoritmasına dayanır. SÜ algoritması çok sayıda değişkenin olduğu problemlerde gevşetilmiş doğrusal programlamanın en iyi sonucunu bulmak için kullanılır. Bu çalışmada SÜ algoritması uygulandıktan sonra, yaratılan tüm sütunları içeren bir karışık tamsayılı programlama probleminin tam çözümü bulunur. Literatürden alınan çeşitli EATP verileri üzerinde elde edilen sonuçlara göre, SÜ gelecek çalışmalarda yapılacak metasezgisel bir arama için yeterince iyi bir sınırlandırılmış arama uzayı elde etmiştir. Tez kapsamında geliştirilen ikinci yöntem ise önceliğe dayalı kodlama kullanılarak geliştirilen Genetik Algoritmadır (GA). Önerilen GA’da her kromozom olası tüm operasyonlar için bir gen içerir ve her bir gen tez kapsamında geliştirilen yapıcı sezgisel algoritmada ilgili operasyonun öncelik değerini verir. Geliştirilen yapıcı algoritma FSJP için aktif çizelge oluşturmak için kullanılır. Literatürden alınan problemlere önerilen GA uygulanmıştır. Sonuç olarak esnekliği en az olan ve zayıf alt sınıra sahip solduğu için diğerlerinden daha zor olan problemlerde, önerilen GA literatürdeki algoritmalardan daha iyi sonuçlar bulmuştur.

One of the most researched topics in scheduling theory is job shop scheduling problem (JSP) which is known as difficult to solve. Flexible Job Shop Scheduling Problem (FJSP) is more complex and general than classical JSP. Unlike JSP; each operation can be processed by one of the machines in a given machine set. The aim of FJSP is finding both an assignment and a corresponding scheduling that minimize production time. In this thesis, two novel algorithms are developed for FJSP. The first algorithm is based on Column Generation (CG) approach which guarantees to find optimum solution of linear programming (LP) relaxation. CG is an exact algorithm to solve the LP models with an enormous number of variables. At the end of CG, a mixed integer programming problem with all generated columns is solved to find an integer solution. According to the computational results, the restricted search space is good enough to use metaheuristic search in further studies. The second approach developed in this study is Genetic Algorithms (GA) with priority based representation. Each gene of a chromosome represents the priority of corresponding operation which is used during constructive algorithm developed for decoding. The constructive algorithm can generate all active schedules which constitute a subset of feasible schedules including optimal one. The computational results showed that the proposed GA performs at the same level or better with respect to the makespan for the problems with low flexibility.