ABSTRACT SHIFTING BOTTLENECK HEURISTICS FOR JOB-SHOP SCHEDULING İnan, Mustafa M.S., Department of Industrial Engineering Supervisor: Assoc. Prof. Dr. Meral Azizoğlu January 1999, 71 pages In this thesis, job shop scheduling problem of minimizing makespan is studied. The problem consists of n-jobs to be processed on m-machines according to predetermined routes. The problem of minimizing makespan on job shops is known to be NP-Hard and optimization algorithms require extensive computational efforts. We propose heuristic algorithms, which are based on modifications of well known shifting bottleneck algorithms. Performance of the algorithms are analyzed on a number of problem instances taken from literature. The computational results have revealed that the algorithms are capable producing high quality solutions for large size problems, in reasonable CPU-times. Keywords: Scheduling, Job Shop, Heuristic, Shifting Bottleneck. iii

oz ATELYE TIPI İMALAT SİSTEMLERİ İÇİN KAYAN DARBOĞAZ MAKİNE SEZGİSEL YAKLAŞIMI İnan, Mustafa Yüksek Lisans, Endüstri Mühendisliği Bölümü Tez Yöneticisi: Doç. Dr. Meral Azizoğlu Ocak 1999, 71 sayfa Bu çalışmada, atelye tipi imalat sistemlerinde, tüm işlerin bitirilmesi için geçen sürenin enküçüklenmesi problemi incelenmiştir. Atelye tipi imalat sistemi, m makinede önceden belirlenmiş sırada işlenmesi gereken, n işten oluşur. Problemin zorluğundan ve en iyi sonucu veren yöntemlerin uzun sürede çözüm üretmesinden dolayı sezgisel yöntemler önerilmiştir. Bu algoritmalar literatürde bilinen kayan darboğaz makine yaklaşımına dayanmaktadır. Algoritmaların etkinliği literatürde yer alan problemler üzerinde denenmiştir. Büyük problemlerde dahi iyi sonuç verdiği gösterilmiştir. Anahtar Kelimeler: Atelye Tipi İmalat Sistemi, Çizelgeleme, Sezgisel Yöntemler, Kayan Darboğaz Makine. iv

71