
Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem
Grosso, Andrea; Della Croce, Federico; Paschos, Vangelis (2004), Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem, Journal of Scheduling, 7, 1, p. 85-91. http://dx.doi.org/10.1023/B:JOSH.0000013056.09936.fd
View/ Open
Type
Article accepté pour publication ou publiéDate
2004Journal name
Journal of SchedulingVolume
7Number
1Publisher
Springer
Pages
85-91
Publication identifier
Metadata
Show full item recordAbstract (EN)
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(n 7/E)). 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.Subjects / Keywords
Approximation; Scheduling; Total tardinessRelated items
Showing items related by title and author.
-
Paschos, Vangelis; Demange, Marc (1997) Article accepté pour publication ou publié
-
Baburin, Aleksei; Della Croce, Federico; Gimadi, Edward; Glazkov, Yuri; Paschos, Vangelis (2009) Article accepté pour publication ou publié
-
Della Croce, Federico; Aloulou, Mohamed Ali (2008) Chapitre d'ouvrage
-
Paschos, Vangelis; Della Croce, Federico; Escoffier, Bruno (2007) Article accepté pour publication ou publié
-
Della Croce, Federico; Paschos, Vangelis (2012) Communication / Conférence