A simple, fast, and effective heuristic for the single-machine total weighted tardiness problem

Abstract

Bu tezde, kesintisiz tek-makinalı toplam ağırlıklı gecikme problemi genel gecikme ağırlıkları, işlem zamanları ve teslim tarihleri ile birlikte incelenmiştir. İlk olarak bu problem için bir grup kesintili gevşetilmiş alt sınır geliştirilmiş ve bunların yapısal özellikleri araştırılmıştır. Sonrasında, göz önüne alınanlar arasında en gevşek alt sınıra karşılık gelen kesintili çözümün, çok kısa hesaplama süreleri içerisinde asıl kesintisiz problem için çok kaliteli olurlu çözümler oluşturmak üzere kullanılabilecek bazı özellikler sağladığı gösterilmiştir. Literatürdeki standart denektaşı problem örnekleri çözülmüş ve bulunan sonuçlar takdim edilmiştir.

We consider the non-preemptive single-machine total weighted tardiness (TWT) problem with general weights, processing times, and due dates. We ? rst develop a family of preemptive lower bounds for this problem and explore their structural properties. Then, we show that the solution corresponding to the least tight lower-bound among those investigated features some desirable properties that can be exploitedto build excellent feasible solutions to the original non-preemptive problem in short computational times. We present results on standard benchmark instances from the literature.