Flow shop scheduling subject to renewable resource constraint: unitprocessing time problems

Abstract

ÖZET YENİLENEBİLİR KAYNAK KISITLI, BİRİM OPERASYON ZAMANLI VE SERİ İŞ AKIŞLI SİSTEMLERDE ÇİZELGELEME PROBLEMİ SURAL, Haldun Yüksek Lisans Tezi, End. Müh. Bölümü Tez Yöneticisi: Y. Doç. Dr. Suna KONDAKCI Tez Yöneticisi: Doç. Dr. Nesim ERKİP Şubat 1988, 113 sayfa Bu çalışma, kesikli ve yenilenebilir kaynak kısıtlı seri iş akışlı sistemlerde birim zamanlı işlerin çizelgelemesini ele almaktadır. İki makine ve birim operasyon zamanlı işler içeren kaynak kısıtlı ve seri- iş akışlı problemlerde beklemesiz çizelgelerin işlerin tamamlanma süresini her zaman en aza indirdiği ve bu problemin gezgin satıcı problemine denk olduğu gösteril mektedir. Aynı problemin özel bir durumu için polinom zamanlı bir algoritma verilmektedir. Ele alınan problem sınıfı için işlerin tamamlandığı en az süreyi bulan genel bir dal-budak algoritması geliştirilmiştir. Ayrıca, bazı yük paketleme algoritmalarının alt sınır olarak kullanılabilirliği incelenmiştir. Yaklaşık sonuç bulan dört algoritma önerilmiş ve üç makine problemleri için bu algoritmaların işlerin tamamlandığı en az süreyi bulmadaki etkinliği sınanmıştır. Anahtar kelimeler: Çizelgeleme, deterministik, seri akışlı sistem, yenilenebilir kaynak. iv

ABSTRACT FLOW-SHOP SCHEDULING SUBJECT TO RENEWABLE RESOURCE CONSTRAINT: UNIT-PROCESSING TIME PROBLEMS SURAL, Haldun M.S. in Industrial Engineering Supervisor: Assist. Prof. Suna KONDAKCI Supervisor: Assoc.Prof.Dr. Nesim ERKIP February 1988, 113 pages The study deals with the scheduling of unit-time jobs in flow-shop under discrete renewable resource constraint. It is shown that `no-wait` schedules for two- machine, unit-processing time, resource constrained flow- shop problems always minimize makespan and the problem is equivalent to traveling salesperson problem. A polynomial time algorithm is constructed for a special case of this problem. A general branch-and-bound algorithm to find a minimum makespan schedule for the above class of problems is designed. Implementation of some bin packing algorithms as lower bounds are investigated. Four approximation algorithms are proposed and their efficiencies in finding minimum makespan are tested for three-machine problems. Key words: Scheduling, deterministic, flow-shop, renewable resource. iii