A heuristic for bicriteria single machine scheduling problem with sequence dependent setup times

Sıra bağımlı hazırlık süreli iki ölçütlü tek makine çizelgeleme problemi için sezgisel bir çözüm yöntemi

Abstract

In this study, the bi-criteria scheduling problem of minimizing the makespan and total tardiness on a single machine with sequence dependent setup times is considered. This problem is known as NP-hard. To solve this problem, firstly we propose a new dispatching rule named as WSST that is the weighted form of the SST (Shortest Setup Time) rule. The proposed rule is compared with EDD (Earliest Due Date), SST and ATCS (Apparent Tardiness Cost with Setups) dispatching rules. And then, a new heuristic which improves the solutions of the WSST by a local search algorithm is proposed. The performance of the proposed heuristics is tested by using randomly generated test problems.

Özet

Bu çalışmada sıra bağımlı hazırlık süreli, son işin tamamlanma zamanını ve toplam gecikmeyi en aza indirmeyi amaçlayan tek makine çizelgeleme problemi ele alınmıştır. Bu problem NP-zor sınıfında yer almaktadır. Problemin çözümü için ilk olarak, SST (en kısa hazırlık süresi) sıralama kuralının ağırlıklandırılmış hali olan yeni bir sıralama kuralı (WSST) önerilmiştir. Bu sıralama kuralı, literatürde yer alan EDD (en küçük teslim zamanı), SST ve ATCS (Apparent Tardiness Cost with Setups) sıralama kurallarıyla karşılaştırılmıştır. Daha sonra, önerilen sıralama kuralının çözümlerini, bir yerel arama yöntemiyle iyileştirme amacını güden yeni bir sezgisel algoritma önerilmiştir. Önerilen yöntemlerin etkinliği rassal olarak türetilen test problemleri kullanılarak araştırılmıştır.