A faster fully polynomial approximation scheme for the single-machine total tardiness problem

Christos Koulamas

European Journal of Operational Research, 2009, vol. 193, issue 2, 637-638

Abstract: Lawler [E.L. Lawler, A fully polynomial approximation scheme for the total tardiness problem, Operations Research Letters 1 (1982) 207-208] proposed a fully polynomial approximation scheme for the single-machine total tardiness problem which runs in time (where n is the number of jobs and [epsilon] is the desired level of approximation). A faster fully polynomial approximation scheme running in time is presented in this note by applying an alternative rounding scheme in conjunction with implementing Kovalyov's [M.Y. Kovalyov, Improving the complexities of approximation algorithms for optimization problems, Operations Research Letters 17 (1995) 85-87] bound improvement procedure.

Keywords: Single-machine; sequencing; Total; tardiness; Fully; polynomial; approximation (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00006-4
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:193:y:2009:i:2:p:637-638

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().