A genetic algorithm for a flexible job shop scheduling problem with sequence dependent set up times

Abstract

Bu tezde, sıra bağımlı hazırlık zamanlı esnek atölye çizelgeleme problemlerinden, tamamlanma zamanı minimizasyonu Genetik Algoritma ile çözülmüştür. Esnek atölye çizelgeleme problemlerinde iş akışı paralel ve paralel olmayan iş istasyonları arasında olmaktadır. Esnek atölye çizelgeleme problemi iki alt problemden oluşmaktadır. İlk problem; her bir operasyonun makinalara atamaların yapılması, ikinci problem ise ataması yapılan makina önündeki iş sıralamaların yapılmasıdır. Bu tezde, ilk problemde, üç makine atama yöntemi kullanılmıştır. İlk yöntem her bir operasyonu makinalara atarken makina yüklerini ve iş sürelerini göz önünde bulundurarak atama yapan ?Approach by Localization? yöntemidir. Bu yöntem makine hazırlık zamanlarını göz önünde bulundurmamaktadır. İkinci yöntem ?Approach by Localization? yönteminin sıra bağımlı hazırlık zamanlarını da makina yükleri ve iş süreleri ile birlikte göz önünde bulundurdurarak modife edildiği yöntemdir. Üçüncü yöntem ise karşılaştırma amaçlı kullanılan, makine atamalarının rastgele yapıldığı yöntemdir. İkinci problemde operasyon ataması yapılmış her bir makina önündeki sıralamalar, En Kısa Hazırlık Zamanı, En Kısa İşlem Zamanı, En Uzun İşlem Zamanı, En Uzun Kalan Süre ve Rasgele, öncelik dağıtım kuralları ile oluşturulmaktadır._x000B_Bu tezde, makine atamaları ve makine önündeki sıralamalar yapılırken sıra bağımlı hazırlık zamanları iş süreleri ve makine yükleri ile birlikte ele alınmıştır. Farklı problem büyüklüklerinde başlangıç popülasyonu yaratma, sistemde kalma süresi hesaplama, seçme ve mutasyon yöntemlerinin genetik algoritma performansı üstünde etkileri araştırılmıştır. This thesis addresses the problem of scheduling flexible job shops with sequence dependent setup times, and aims at minimizing makespan as an objective by using genetic algorithms. The flexible job shop is characterized by job flow through a number of work centers that contain identical or nonidentical parallel machines. Flexible Job Shop Problems divided into two subproblems. In the first subproblem, assignments of operations to machines are made. In the second subproblem, sequencing problem is solved. For the first subproblem, three assignment methods were used in this thesis. The first method is ?Approach by Localization? which assigns each operation to the suitable machine by taking into accounts the processing times and workloads of machines. This assignment procedure assumes that there are no setup times. The second method is modified version of the first method. In this method, we modified the assignment procedure by using sequence dependent setup times in addition to processing times and workloads of machines. In the third method, assignments were made randomly just for the comparison purposes. For the second subproblem, dispatching rules such as shortest processing time (SPT), most work remaining (MWR), longest processing time (LPT), shortest setup time first rule (SSTFR), random rule and neighborhood search were applied to sequence the machines._x000B_The main feature of this thesis is to combine the sequence dependent setup times with the processing times and the workloads on both assignment and sequencing procedures. The performance of genetic algorithm was also analyzed by taking into account the issues such as, initial population generation, sequencing, selection and mutation methods.