Single machine scheduling problemsi early-tardy penalties

Abstract

Özet TEK MAKİNA ÇİZELGELEME PROBLEMLERİ: ERKEN-GEÇ PENALTILARI Ceyda Oğuz Endüstri Mühendisliği Doktora Tez Yöneticisi: Doç. Dr. Cemal Dinçer Mart 1993 Tek makinalı farklı teslim tarihli toplam erken-geç çizelgeleme problemlerini analiz etmek ve problemin hem kesin çözümü için bir dinamik programlama formülasyonu hem de yaklaşık çözümü için kabul edilebilir sınırlar içinde sezgisel yordamlar geliştirmek bu çalışmanın ana içeriğini oluşturmaktadır. Tek makinalı erken-geç çizelgeleme problemleri üzerine daha önce yapılmış çalışmaların incelenmesi, araştırmaların başlıca, çizelgede boş zaman ilave edilmesine izin verilmeyen, kısıtlı bir problem üzerine yoğunlaştığını göstermektedir. Bu çalışma, gerekli olduğu zamanlarda boş zaman ilavesine izin veren genel modelle ilgilenmektedir. Tek makinalı erken-geç çizelgeleme problemleri için, ftfV-zox olmalarına rağmen, dinamik programlama formülasyonu yoluyla eniyi çözüm veren algoritmalara ihtiyaç vardır. Böyle bir algoritma, problem için bir yaklaşık yöntem tanımlayabilmek için gereklidir ki bu erken-geç çizelgeleme kuramında hemen hiç dokunulmamış bir alandır. Bundan başka, geliştirilen dinamik pro gramlama formülasyonu, önerilen sezgisel yöntemlerden birinin özünü oluşturan kısıtlandırılmış durum uzaylı bir dinamik programlama şekline dönüştürülmüştür. iiiBu çalışmanın ikinci bir safhası farklı teslim tarihleri için iki özel yapının, Eşit-Boşluk ve Toplam-İş-İçeriği kurallarının, incelenmesi ve bu özel yapılarla problemin hesap karmaşıklığının tartışılmasıdır. Bu problemler için, özel teslim tarih yapılarının özelliklerine dayanan çözüm yöntemleri önerilmiştir. Eşit-Boşluk kurallı toplam erken-geç çizelgeleme probleminin J V-zoı olduğu ispatlanırken, problemin belirli durumlarda polinom zamanda çözülebildiği de gösterilmiştir. Bundan başka, ikinci teslim tarihi yapısı ile problem için çok etkin bir sezgisel yordam önerilmiş ve bu problemden elde edilen sonuçlar, genel teslim tarihli problem için bir başka sezgisel yordamın geliştirilmesine öncülük etmiştir. Son olarak, problemin eniyi çözümünün yapısından kaynaklanan bir alt sınır yöntemi sunulmuştur. Bu alt sınır, literatürden bir başka alt sınır ile kıyaslanmış ve geliştirilen bu alt sınırın rassal yaratılan problemler üzerinde iyi performans gösterdiği gözlemlenmiştir. Anahtar Sözcükler: Deterministik Tek Makina Çizelgelemesi, Toplam Erken-Geç Enazlanması, Hesap Karmaşıklığı Teorisi, Kesin Çözüm Al goritmaları, Dinamik Programlama, Sezgisel Yordamlar, Alt Sınırlar. iv

Abstract SINGLE MACHINE SCHEDULING PROBLEMS: EARLY-TARDY PENALTIES Ceyda Oğuz Ph. D. in Industrial Engineering Supervisor: Assoc. Prof. Dr. Cemal Dinger March 1993 The primary concern of this dissertation is to analyze single machine total earli- ness and tardiness scheduling problems with different due dates and to develop both a dynamic programming formulation for its exact solution and heuristic algorithms for its approximate solution within acceptable limits. The analyses of previous works on the single machine earliness and tardiness scheduling problems reveal that the research mainly focused on a restricted problem type in which no idle time insertion is allowed in the schedule. This study deals with the general case where idle time insertion is allowed whenever necessary. Even though this problem is known to be jV`P-hard in the ordinary sense, there is still a need to develop an optimizing algorithm through dynamic programming formulation. Development of such an algorithm is necessary for further identifying an approximation scheme for the problem which is an untouched issue in the earliness and tardiness scheduling theory. Furthermore, the developed dynamic programming formulation is extended to an incomplete dynamic programming which forms the core of one of the heuristic procedure proposed.A second aspect of this study is to investigate two special structures for the different due dates, namely Equal-Slack and Total- Work-Content rules, and to discuss computational complexity of the problem with these special structures. Consequently, solution procedures which bear on the characteristics of the special due date structures are proposed. This research shows that the total earliness and tardiness scheduling problem with Equal-Slack rule is MV-haxa. but can be solvable in polynomial time in certain cases. Moreover, a very efficient heuristic algorithm is proposed for the problem with the other due date structure and the results of this part leads to another heuristic algorithm for the general due date structure. Finally, a lower bound procedure is presented which is motivated from the structure of the optimal solution of the problem. This lower bound is compared with another lower bound from the literature and it is shown that it performs well on randomly generated problems. Keywords: Deterministic Single Machine Scheduling, Minimizing Total Earliness and Tardiness, Computational Complexity Theory, Dynamic Programming, Heuristic Algorithms, Lower Bounds. 11