Esnek akış tipi çizelgeleme problemine sezgisel bir yaklaşım ve bir uygulama
A heuristic approach and an application to flexible flowshop scheduling problem
Yazar: EMRE ASLAN
Danışman: PROF. DR. OSMAN UNUTULMAZ
Erciyes Üniversitesi / Sosyal Bilimler Enstitüsü / İşletme Ana Bilim Dalı / Üretim Yönetimi ve Pazarlama Bilim Dalı
Derece: Doktora, 2014
Konu: İşletme = Business Administration
Dizin: Karma tamsayılı programlama = Mixed integer programming ; Sezgisel yöntemler = Heuristic methods ; Çizelgeleme = Scheduling

Özet:
Esnek akış tipi çizelgeleme problemi birbirine seri aşamaları olan, bu aşamalardan en az birinde paralel makineler bulunan ve işlerin aynı rotayı takip ettiği çizelgeleme problemi tipidir. Akış tipi çizelgeleme probleminin paralel makineli hali veya paralel makine çizelgeleme probleminin çok aşamalı hali olarak da düşünülebilir.

Bu tezde, esnek akış tipi çizelgeleme probleminde aşama atlama, partilere ayırma, sıra bağımlı hazırlık zamanları, makine uygunluk ve iş öncelik kısıtları birlikte ele alınmıştır. Ofis mobilyaları üreten bir tesiste uygulaması olan bu çalışmada 6 aşama ve 66 iş vardır. 

Problem için öncelikle karma tamsayılı programlama modeli geliştirilmiş, model GAMS dilinde yazılmış ve CPLEX çözücü ile çözüm aranmıştır. 2 saat, 1 gün ve 3 gün boyunca maksimum tamamlanma zamanı ve toplam gecikmeyi minimize etmeye çalışan iki ayrı amaç fonksiyonu için çalıştırılmış fakat optimum çözüm bulunamamıştır. Bu nedenle söz konusu problem için çok daha kısa sürelerde kabul edilebilir sonuçlar vermesi beklenen sıralama kurallarına dayalı bazı sezgisel modeller geliştirilerek kullanılmıştır. Uyarlanmış Johnson Kuralı (UJK), En Az Boşluk Kuralı (EABK) ve bu kurallarla karşılaştırma yapılabilmesi için En Kısa İşlem Zamanı (EKİZ) ve En Uzun İşlem Zamanı (EUİZ) kuralları tezin uygulama problemine ve oluşturulan farklı büyüklükteki test problemlerine uygulanmış ve gerekli karşılaştırmalar yapılmıştır.

UJK sezgiselinin Cmax performans kriterinde en iyi sonuçları verdiği tespit edilmiştir. UJK sezgiseli uygulama probleminde matematiksel modelin 3 gün çalışarak ulaştığı Cmax değerinden %34 daha düşük bir değeri 1 saniyeden daha kısa sürede elde edebilmektedir. Bununla beraber EABK sezgiselinin büyük boyutlu problemlerde gecikme ile ilgili kriterler dikkate alındığında öne çıktığı görülmüştür. Problemlerde ilk aşama sonrası partilere ayırma alternatifi denenmiş ve bu duruma özel Partilere Ayrılmış En Az Boşluk Kuralı (PEABK) geliştirilmiştir. PEABK gecikme ile ilgili kriterlerde hem küçük hem de büyük boyutlu problemlerde EABK sezgiselinden daha iyi sonuçlar vermiştir.

Abstract:
The flexible flow shop scheduling problem is such a flow shop scheduling problem that has serial stages, at least one of the serial stages has parallel machines and the jobs follow the same path. The flexible flow shop scheduling problem may be considered as a flow shop scheduling problem with parallel machines or a multi-stage parallel machine scheduling problem.

In this thesis; stage skipping, lot splitting, sequence-dependent setup times, machine eligibility and the precedence constraints are taken into account all together at the same time while developing the methods for solving the flexible flow shop scheduling problem. The identified model is being employed to solve the existing problem of an office furniture producing facility that is composed of 6 stages and 66 jobs.

At the beginning a mixed integer programing model is developed. This model is coded in GAMS programming language and the solution is searched employing CPLEX solver. It is run for 2 hours, 1 day and 3 days  for two different objective functions minimizing makespan and total tardiness. However, the optimum solution is not reached. Then with the expectation of reaching reasonable solutions within a short time period heuristic methods based on priority rules are developed and employed. Modified Johnson Rule, Minimum Slack Rule and to be able to compare the results Shortest Processing Time and Longest Processing Time rules are also employed while solving the office furniture producing facility problem and the similar problems of different size. Finally such obtained results are compared.

It is observed that the Modified Johnson Heuristic gives the best result on the Cmax performance criteria. In fact, the Modified Johnson heuristic finds a Cmax value, within a second, which is 34% smaller than the Cmax value obtained by the mathematical model in 3 days. However, under the tardiness criterion, Minimum Slack Rule heuristic is prominent for large size problems. An alternative of lot splitting after the first step was experimented and Lot-Splitted Minimum Slack Rule was developed special to this situation. Lot-Splitted Minimum Slack Rule obatined better values than Minimum Slack Rule according to tardiness-related criteria on both small and large size problems.