An Exact approach to minimize total weighted tardiness problem with unequal release dates

Abstract

ÖZET TEK MAKİNADA FARKLI SİSTEM GİRİŞ ZAMANLARI İLE TOPLAM AĞIRLIKLI GECİKME PROBLEMİNE TAM SONUÇ BULMA YAKLAŞIMI Deniz Özdemir Endüstri Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Yard. Doç. Dr. M. Selim Aktürk Ağustos, 1998 Bu araştırmada, tek makinada, farklı sistem giriş zamanlarına sahip bir iş kümesinin toplam ağırlıklı gecikmeyi enaza indirgeyerek çizelgelenmesi problemi gözönüne alındı. Komşu her iş ikilisinin zamana bağlı sıralanması düşünülerek yeni bir baskınlık kuralı sunuldu. Önerilen kural yerel enaza indirgemeyi garanti etmekte yani komşu işlerin yerlerinin değiştirilmesi ile daha iyi bir amaç fonksiyonu değerinin bulunamayacağını göstermektedir. Bu baskınlık özelliklerini kullanan bir algoritma geliştirilerek, literatürdeki metotlarla karşılaştırıldı. Sonuçlar, önerilen algoritmanın test edilen bütün problemler için rakip algoritmalardan daha iyi sonuç verdiğini gösterdi. Bunun sonucu olarak, önerilen algoritmanın üst smır hesaplarında iyileştirme sağlayacağı ve kesin sonuca yönelik tekniklerde alternatif sayısını azaltacağı iddia edilebilir. Ayrıca önerilen baskınlık özellikleri bir alt smır projesi, dallandırma şartı ve araştırma stratejisi ile birleştirilerek bir dal & sınır algoritması geliştirildi. Tek makinada, farklı sistem giriş zamanları ile toplam ağırlıklı gecikmeyi enazlama problemi üzerine tam sonuç bulmaya yönelik çalışma, tarafımızca bilinmiyor. Araştırmanın bu problem üzerine yapılan tam sonuç bulmaya yönelik ilk çalışma olması literatüre katkısını arttırmaktadır. Anahtar sözcükler: Tek Makinada Çizelgeleme, Toplam Ağırlıklı Gecikmeyi Enazlama, Baskınlık Kuralları, Sezgisel Algoritmalar, Dal&Smır Algoritması. iv

ABSTRACT AN EXACT APPROACH TO MINIMIZE SINGLE MACHINE TOTAL WEIGHTED TARDINESS PROBLEM WITH UNEQUAL RELEASE DATES Deniz Ozdemir M.S. in Industrial Engineering Supervisor: Assist. Prof. M. Selim Aktürk August, 1998 In this research, the problem of scheduling a set of jobs on a single machine to minimize total weighted tardiness with unequal release dates is considered. We present a new dominance rule by considering the time depending orderings between each pair of jobs. The proposed rule provides a sufficient condition for local optimality. Therefore, if any sequence violates the dominance rule then switching the violating jobs either lowers the total weighted tardiness or leaves it unchanged. Based on the dominance rule, an algorithm is developed which is compared to a number of heuristics in the literature. Our computational results indicate that the proposed algorithm dominates the competing algorithms in all runs, therefore it can improve the upper bounding scheme and can be used in reducing the number of alternatives in any enumerative algorithm. Furthermore, the proposed dominance rule is incorporated in a branch and bound algorithm in conjunction with lower bounding scheme, branching condition and search strategy. To the best of our knowledge, author know of no other published exact approach for l/rj/ J2wjTj problem. This enhances contribution of our study in the literature. Key words: Dominance Rule, Single Machine, Scheduling, Total Weighted Tardiness, Release Dates, Heuristics, Branch h Bound Algorithms. iii