Atölye tipi çizelgeleme problemleri için genetik algoritma tabanlı hipersezgisel yaklaşım
A genetic algorithm-based hyperheuristic approach for job shop scheduling problems
Yazar: CANAN HAZAL AKARSU
Danışman: DOÇ. DR. TARIK KÜÇÜKDENİZ
İstanbul Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2018
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Atölye tipi çizelgeleme problemleri hem literatürde hem de endüstriyel uygulamalarıyla bir gerçek hayat problemi olarak geniş biçimde incelenen yaygın ve zor problemlerdir. Bu nedenle verimliliği arttırıp maliyetleri düşürerek karlılığı arttırmak amacıyla etkili üretim çizelgeleme yöntemlerinin geliştirilmesi oldukça önemlidir. Fazla adaptasyon süresi gerektirmeden farklı problemlerde kullanılabilecek, yeterince iyi, yeterince hızlı, yeterince ucuz çözüme ihtiyaç duyulduğu durumda hipersezgiseller tercih edilir. Hipersezgiseller çözüm uzayı yerine alt seviyeli sezgisellerin arama uzayında çalışan, dolayısıyla bir dizi alt seviye sezgiseli yöneterek probleme direk çözüm aramak yerine çözüm için iyi bir yöntem arayan, sınırlı miktarda probleme özel bilgiye ihtiyaç duyan sezgisel seçen sezgisellerdir. Bu çalışmada atölye tipi çizelgeleme problemlerinin çözümü için genetik algoritma tabanlı hipersezgisel (GAHS) yaklaşımı önerilmiştir. Alt seviyeli sezgiseller olarak 26 adet dağıtım kuralı kullanılmıştır. Dağıtım kuralları çizelgeleme problemlerindeki başarısı, uygulama kolaylığı ve esnekliği sebebiyle tercih edilmiştir. Geliştirilen GA tabanlı hipersezgisel yaklaşımın yazılımı Matlab kullanılarak yapılmıştır. Önerilen GA tabanlı hipersezgisel yaklaşımın performansı, tek başına GA, TB ve PSO metasezgiselleri ve literatürde atölye tipi çizelgeleme problemlerinde maksimum tamamlanma zamanının enküçüklenmesi için başarılı bulunan SPT, MTWR, SIO, FIFO, PT+WINQ dağıtım kuralları ile karşılaştırılarak değerlendirilmiştir. Kıyaslama problemleri olarak OR-Library' den temin edilmiş farklı veri setlerinden farklı boyutlardaki problemler seçilmiştir. Genetik algoritma tabanlı hipersezgisel, kıyaslama problemlerine optimum ya da kıyaslanan yöntemlere göre daha iyi sonuç vermiştir.

Abstract:
Job shop scheduling problems are common and hard problems that are widely studied both in the literature and in industrial applications as a real life problem. Therefore it is very important to develop effective production scheduling methods in order to increase profitability by increasing efficiency and reducing costs. Hyperheuristics are preffered when we are looking for a technique which can be easily applied to different problems without requiring too much adaptation time and when we require solutions which are good enough, fast enough and cheap enough. Hyperheuristics are heuristics to choose heuristics that require a limited amount of problem specific information and work in low level heuristics' search space instead of solution space. Thus hyperheuristics search for a good method for solution by managing low level heuristics rather than looking for a direct solution. In this thesis, a genetic algorithm based hyperheuristic (GAHH) approach is proposed for job shop scheduling problems. As low level heuristics 26 dispatching rules were used. Dispatching rules were prefered because of their success in scheduling problems, ease of implementation and flexibility. The code of developed genetic algorithm based hyperheuristic approach was written in Matlab. The performance of the proposed approach was compared with metaheuristics as GA, SA, PSO,  and with dispatching rules as SPT, MTWR, SIO, FIFO, PT+WINQ which were found to be successful in minimizing the makespan in job shop scheduling problems in the literature. Benchmark problems in different sizes were selected from datasets supplied by OR-Library. Computational experiments show that the proposed genetic algorithm based hyperheuristic find optimum or else better results than compared methods.