Tez No İndirme Tez Künye Durumu
341129
A genetic algorithm for the resource constrained project scheduling problem having a single machine with sequence dependent setup times / Sıra bağımlı kurulum zamanlı tek bir makineye sahip kaynak kısıtlı proje çizelgeleme problemi için bir genetik algoritma
Yazar:SÜLEYMAN KAYA
Danışman: DOÇ. DR. SEDEF MERAL
Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Konu:Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin:
Onaylandı
Yüksek Lisans
İngilizce
2013
79 s.
Bu çalışmada ele alınan çizelgeleme problemi çizelgeleme alanındaki iki farklı tipteki çizelgeleme probleminin birleşiminden oluşmaktadır. Bu problemlerden biri kaynak (yenilenebilir) kısıtlı proje çizelgeleme problemi, diğeri ise sıra bağımlı kurulum zamanlarına sahip tek makineli çizelgeleme problemidir. Gerçek hayatta proje çizelgeleme problemleri genellikle karmaşıktır ve çeşitli çizelgeleme problem karakteristiklerini içermektedir. Ele alınan problemdeki amaç projenin bitiş zamanını en aza indirmektir. Bu problem için bir genetik algoritma ve karışık tamsayılı doğrusal programlama modeli geliştirilmiştir. Küçük boyutlu problem örneklerinde genetik algoritmanın sonuçları IBM ILOG CPLEX kütüphanesi kullanılarak kodlanan karışık tamsayılı doğrusal programlama modelinin sonuçlarıyla karşılaştırılmıştır. Geliştirilen karışık tamsayılı programlama modeli, kaynak kısıtlı proje çizelgeleme probleminin karışık tamsayılı programlama modeli ile sıra bağımlı kurulum zamanlarına sahip tek makineli çizelgeleme probleminin karışık tamsayılı programlama modelinin birleşiminden oluşmaktadır. Büyük boyutlu problem örnekleri için genetik algoritmanın sonuçları, bir tepe-tırmanma benzeri arama algoritmasının sonuçlarıyla karşılaştırılmıştır. Genetik algoritma, karışık tamsayılı programlama modeli ve bir tepe-tırmanma benzeri arama algoritmasının bilgisayar programları Microsoft Visual C# .Net platform kullanılarak kodlanmıştır. Önerilen genetik algoritmanın verdiği sonuçların tepe-tırmanma benzeri algoritmanın verdiği sonuçlardan daima daha iyi olduğu gözlemlenir.Anahtar Kelimeler: Sıra bağımlı kurulum zamanlarına sahip tek makineli çizelgeleme, Kaynak kısıtlı proje çizelgeleme, Genetik algoritmalar, Arama algoritmaları
The scheduling problem considered in this study is the integration of two different problems in the scheduling area. One of the problems is the resource constrained project scheduling problem with renewable resources, while the other one is the single machine scheduling problem with sequence dependent setup times. In real life, project scheduling problems are usually complicated and include various scheduling problems characteristics. The objective of the problem addressed is the minimization of the completion time of the project. A genetic algorithm and a MIP model are developed for the problem. The results of the genetic algorithm for small problem instances are compared with the results of the MIP model coded using the library of IBM ILOG CPLEX. The MIP model developed is the integration of the MIP model of the resource constrained project scheduling problem and the MIP model of the single machine scheduling with sequence dependent setup times. For big problem instances, results are compared with the results of hill-climbing-like search algorithm. Computer programs for the genetic algorithm, MIP model and the hill-climbing-like search algorithm are coded by Microsoft Visual C# .Net platform. The results obtained by the proposed genetic algorithm are always superior to the hill-climbing-like search algorithm?s results.Keywords: Single machine scheduling with sequence dependent setup times, Resource constrained project scheduling, Genetic algorithms, Search algorithms