Sıralı akış tipi çizelgeleme problemlerinde genetik algoritma uygulaması
A genetic algorithm application on ordered flow-shop problems
Yazar: MEHMET TUFAN KÖREZ
Danışman: Y.DOÇ.DR. SEMİH ÖNÜT
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2005
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Tez kapsamında, NP problemleri grubunda olan akış tipi çizelgeleme problemlerinin bir altgelişimi olan ?sıralı akış tipi çizelgeleme problemleri? ele alınmış, problem için geliştirilençözüm yöntemine alternatif olarak, Genetik Algoritma ile yeni bir çözüm yöntemigeliştirilmeye çalışılmıştır.Çalışmanın ilk bölümünde, akış tipi çizelgeleme problemlerinin yapısı ve çizelgelemeproblemlerinde kullanılan rassal arama metotlarından olan, tabu araştırmaları, tavlamabenzetimi, karınca kolonileri ve yapay bağışıklık sistemlerinden bahsedilmiştir.Genetik algoritmanın sıralı akış tipi çizelgeleme problemleri üzerindeki performansınıdeğerlendirmek için yapılan uygulama, sıralı akış tipi çizelgeleme problemlerinin doğasıgereği iki kısım olarak ele alınmıştır.İlk kısımda, genel durum olarak adlandırılan, işlem zamanları matrisinde en büyük işlemzamanlarının ara makinelerden birinde oluşması durum ele alınmıştır. 10 farklı iş-makinekombinasyonu üzerine yapılan uygulamada, genetik algoritmanın Smith Panwalkar Dudekalgoritmasına çok yakın sonuçlar verdiği, tavlama benzetimine kıyasla daha iyi olduğugözlenmiştir.İkinci kısım olan, en büyük işlem zamanlarının ilk yada son makinede oluşması durumu, özeldurum problemlerinde ise tekrar genel durum probleminde ele alınan 10 farklı iş-makinekombinasyonu ele alınmış, burada da genetik algoritma Smith Panwalkar Dudekalgoritmasına yakın sonuçlar vermiş, tavlama benzetimine göre daha iyi olduğu gözlenmiştir.İki uygulama ele alındığında, genel durum problemleri için iyi bir çözümü Smith PanwalkarDudek algoritmasına kıyasla çok daha kısa bir zamanda elde ettiğinden genetik algoritmayıkullanmak avantajlı olacak, ancak özel durum probleminde, optimum sonucu çok basit biryöntemle, kısa zamanda ve az eforla garanti ettiğinden Smith Panwalkar Dudek algoritmasınıtercih etmek daha doğru olacaktır.Anahtar Kelimeler: Sıralı Akış Tipi Çizelgeleme, Genetik Algoritma

Abstract:
In this thesis, the problem of scheduling jobs in a flow-shop environment, which is a NP-complete problem is considered. Genetic algorithm is applied in order to find a new approachto the problem.In the first part of the study, the structure of flow-shop problems and some related randomsearch methods such as tabu search, simulated annealing, ant colonies and artificial immunesystems are considered.The application, which is made to determine the performance of genetic algorithm, on orderedflow-shop problems are considered as two different parts as the nature of the ordered type offlow-shop problems.In the first part, the general case, which is the maximum processing time for every joboccurred in intermediate machines, are considered. The application is made on 10 differentjob-machine combinations and as an outcome, genetic algorithm had close results, whichwere better than the results of simulated annealing, to Smith Panwalkar Dudek algorithm wasobserved.In the second part, the maximum processing time for every job occurred on the first or lastmachine, which was the special case, are considered. Same job-machine combinations forgeneral case are considered and again genetic algorithm had better result than simulatedannealing where the results are close enough to Smith Panwalkar Dudek algorithm.After two application, it was observed that in general case, genetic algorithm provides areasonable and close optimal solution which less effort and time than Smith Panwalker andDudek algorithm. But in the special case, Smith Panwalkar Dudek algorithm is much moresimple and optimal solution guaranteed than genetic algorithm.Keywords: Ordered Flow-Shop Problems, Genetic Algorithm