Solution of bicteria open shop scheduling problem with genetic algorithm and tabu search and detailed analysis of results


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara Üniversitesi, Turkey

Approval Date: 2010

Thesis Language: English

Student: Bikem Türkeli

Supervisor: SEROL BULKAN

Abstract:

İKİ KRİTERLİ AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMİNİN GENETİK ALGORİTMA VE TABU ARAMA ALGORİTMASI İLE ÇÖZÜMÜ VE SONUÇLARIN DETAYLI ANALİZİ İşlerin makine kısıtı olmadığı Açık Atölye tipi çizelgeleme problemlerinde işlerin tamamının en az zamanda bittiği ve aynı zamanda maksimum gecikme süresinin en az olduğu çizelgeyi oluşturmak çok zordur. Literatürde, Açık Atölye tipi çizelgeleme problemleri, akış tipi çizelgeleme ve atölye çizelgeleme problemlerinden daha az çalışılmıştır. Literatürde, çizelgeleme alanında yapılan çalışmaların pek çoğunda sadece bir kriter ele alınmıştır ve kriter olarak yoğunlukla üretim tamamlanma zamanı kullanılmıştır. Bir ve iki makine sayılı problemlerde birkaç tane birden çok kriterli çalışmalar yapılmıştır. Ancak ikiden fazla makine sayılı problemlerde genellikle tek amaçlı çalışmalar yapılmıştır. Bilgimiz dahilinde, bu tez iki kriterli Açık Atölye tipi çizelgele problemi çözümüne Genetik Algoritma ve Tabu Arama Algoritması ile çözüm öneren ilk uygulamadır. Bu tezde, üretim tamamlanma zamanı ve maksimum gecikme kriterleri, 4 iş – 4 makine ve 15 iş – 15 makine problem boyutları arasında, aynı zamanda kullanılmıştır. Bu amaçla, Genetik Algoritma ve Tabu Arama Algoritması geliştirilmiş ve analiz problemlerine uygulanmıştır. Genetik Algoritma ve Tabu Arama Algoritması analiz edilmiş, iki algoritmanın performansları karşılaştırılmış ve elde edilen sonuçların detaylı analizi yapılmıştır ABSTRACT SOLUTION OF BICRITERIA OPEN SHOP SCHEDULING PROBLEM WITH GENETIC ALGORITHM AND TABU SEARCH AND DETAILED ANALYSIS OF RESULTS It is very difficult to find the minimum makespan and minimum maximum tardiness values concurrently, in the open shop scheduling problems that do not have any precedence constraint of machines of each job. In literature, studies in OSSP are less than flow shop and job shop problem studies. In literature, generally, solutions regarding single criteria are developed; and makespan is the most common objective used. There are some multi objective solutions for one or two machines; but only one criterion is generally used for more than two machines. To the best of our knowledge, this thesis is the first application of Genetic Algorithm and Tabu Search Algorithm to bicriteria Open Shop Scheduling. In this thesis, makespan and maximum tardiness criteria are used concurrently, for problem sizes between 4 jobs – 4 machines and 15 jobs - 15 machines. For this purpose, a Genetic Algorithm and a Tabu Search Algorithm is developed and applied to test problems. GA and TS are tested, the relative performances of the two algorithms are compared and detailed analysis of results is given.