Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem

Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem

0.00 Avg rating0 Votes
Article ID: iaor2008177
Country: United Kingdom
Volume: 7
Issue: 1
Start Page Number: 85
End Page Number: 91
Publication Date: Jan 2004
Journal: Journal of Scheduling
Authors: , ,
Keywords: heuristics
Abstract:

The weakly NP-hard single-machine total tardiness scheduling problem has been extensively studied in the last decades. Various heuristics have been proposed to efficiently solve in practice a problem for which a fully polynomial time approximation scheme exists (though with complexity O(n7/ϵ)). In this note, we show that all known constructive heuristics for the problem, namely AU, MDD, PSK, WI, COVERT, NBR, present arbitrarily bad approximation ratios. The same behavior is shown by the decomposition heuristics DEC/EDD, DEC/MDD, DEC/PSK, and DEC/WI.

Reviews

Required fields are marked *. Your email address will not be published.