Show simple item record

dc.contributor.authorGrosso, Andrea
dc.contributor.authorDella Croce, Federico
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-01-15T15:14:55Z
dc.date.available2010-01-15T15:14:55Z
dc.date.issued2004
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2975
dc.language.isoenen
dc.subjectApproximationen
dc.subjectSchedulingen
dc.subjectTotal tardinessen
dc.subject.ddc003en
dc.titleLower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problemen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherPolitecnico di Torino;Italie
dc.contributor.editoruniversityotherUniversita` di Torino;Italie
dc.description.abstractenThe 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.en
dc.relation.isversionofjnlnameJournal of Scheduling
dc.relation.isversionofjnlvol7en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2004-01
dc.relation.isversionofjnlpages85-91en
dc.relation.isversionofdoihttp://dx.doi.org/10.1023/B:JOSH.0000013056.09936.fden
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record