A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem

Krzysztof M. Ocetkiewicz

European Journal of Operational Research, 2010, vol. 203, issue 2, 316-320

Abstract: In this paper a single machine time-dependent scheduling problem with total completion time criterion is considered. There are given n jobs J1,...,Jn and the processing time pi of the ith job is given by pi=a+bisi, where si is the starting time of the ith job (i=1,...,n),bi is its deterioration rate and a is the common base processing time. If all jobs have deterioration rates different and not smaller than a certain constant u>0, then for each [epsilon]>0 a solution with the value of the goal function that is at most 1+[epsilon] times greater than the optimal one can be found. We give a FPTAS that finds such a solution in time. Consequently, the problem cannot be NP-hard in the strong sense.

Keywords: Scheduling; Single; machine; Deteriorating; jobs; Total; completion; time; FPTAS (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00537-2
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:203:y:2010:i:2:p:316-320

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 ().