Job shop scheduling under nonrenewable resource constraint

Abstract

ÖZET YENÎLENEMEZ KAYNAK KISITLI, ATELYE TİPİ SİSTEMLERDE ÇİZELGELEME PROBLEMİ TOKER, Ayşegül 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, 101 sayfa Bu çalışma, kesikli ve yenilenemez kaynak kısıtlı atelye tipi sistemlerde işlerin çizelgelemesini ele almaktadır. Sisteme her zaman periyodunda bir birim kaynak geldiği varsayılmıştır. Seçilen performans kriteri işlerin tamamlanma süresini enazlamaktır. Kaynak kısıtlı bir makine probleminin iki makine içeren seri iş akışlı probleme denk olduğunun gösterilmesi, optimal çözüm veren Johnson algoritmasının kullanımını mümkün kılmaktadır. Daha sonra, bu. sonucun bazı uzantıları tartışılmaktadır. Genelde, kaynak kısıtlı m makine içeren atelye tipi çizelgeleme probleminin kaynak kısıtsız m+1 makine içeren atelye tipi çizelgeleme problemine denk olduğu gösterilmiştir. Kaynak kısıtsız problem bir dal-budak algoritması ile çözülmüştür. Bu problemler için yaklaşık çözüm bulan iki algoritma önerilmiş ve performansları sulanmıştır. Anahtar kelimeler: Çizelgeleme, atelye tipi sistem, yenilenemez kaynak. iv

ABSTRACT JOB SHOP SCHEDULING UNDER NONRENEWABLE RESOURCE CONSTRAINT TOKER, Ayşegül M.S. in Industrial Engineering Supervisor: Assist. Prof. Suna KONDAKCI Supervisor: Assoc. Prof. Dr. Nesim ERKİP February 1988, 101 pages This study deals with the job shop scheduling problem under a discrete nonrenewable resource constraint where jobs have arbitrary processing times and resource requirements. Unit supply of a resource is assumed at each time period. Performance criterion is makespan It is proved that a single machine resource constrained problem is identical to two-machine flow shop problem, enabling the use of Johnson's algorithm. Immediate extensions of this result are presented. In general, the equivalence of an m-machine scheduling problem under resource constraint to (mH-l)-machine job shop problem is shown. The latter problem is solved by means of a branch-and-bound algorithm. Two heuristic procedures are proposed for the nonrenewable resource constrained job shop scheduling problem. Performance of these heuristic procedures are tested through generated problems. Key words: Scheduling, job shop, nonrenewable resource iii