Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan

Min Ji and T.C.E. Cheng

European Journal of Operational Research, 2010, vol. 202, issue 1, 90-98

Abstract: We consider a scheduling problem in which n jobs are to be processed on a single machine. The jobs are processed in batches and the processing time of each job is a simple linear function of its waiting time, i.e., the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. The objective is to minimize the makespan, i.e., the completion time of the last job. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B[less-than-or-equals, slant]U for a variable U[greater-or-equal, slanted]2 or B[greater-or-equal, slanted]U for any constant U[greater-or-equal, slanted]2. For the case of B[less-than-or-equals, slant]U, we present a dynamic programming algorithm that runs in pseudo-polynomial time and a fully polynomial time approximation scheme (FPTAS) for any constant U[greater-or-equal, slanted]2. Furthermore, we provide an optimal linear time algorithm for the special case where the jobs are subject to a linear precedence constraint, which subsumes the case where all the job growth rates are equal.

Keywords: Batch; scheduling; Makespan; Computational; complexity; 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 (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00351-8
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:202:y:2010:i:1:p:90-98

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