Single machine total tardiness problem: Exact and heuristic algorithms based on Beta-sequence and decamposition theorems

ÖZET TEK MAKİNEDE TOPLAM GECİKMEYİ EN AZLAMA PROBLEMİ : /3-SIRALAMASI VE AYRIŞTIRMAYA DAYANAN KESİN ÇÖZÜMLÜ VE SEZGİSEL ALGORİTMALAR Bahar Kara Endüstri Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Doç. Dr. Barbaros Ç. Tansel Eylül, 1994 Bu tez çalışmasında tek makinede toplam gecikmeyi enazlama problemi için kesin çözümlü ve sezgisel algoritmalar önerilmiştir. Literatür incelemesinde, bilinen kesin çözümlü algoritmaların 100 iş sayısı ile sınırlı olduğu görülmektedir. Bu çalışmada yakın zamanda geliştirilmiş olan /^-sıralaması ve ayrıştırma yöntemleri kullanılarak oluşturulan kesin çözümlü algoritmalar ile 200 iş sayılı problemler hızlı çözüme ulaştırılırken 500 iş sayısı içeren 160 test probleminin de 120 si çözüme ulaştırılmıştır. Ayrıca, bu çalışmada kesin çözümlü algoritmaya dayanan bir de sezgisel yöntem geliştirilmiştir. Sezgisel yöntem eniyi çözüme oldukça yakın sonuçlar vermektedir ve test problemlerinin %30 unda eniyi çözümü vermiş, bütün test problemlerinde ise optimalden sapması %9 un içinde kalmıştır. Anahtar sözcükler: Tek makinede çizelgeîeme, Toplam Gecikmeyi Enazlama, Kesin Çözümlü Algoritmalar, Sezgisel Algoritmalar. iv