Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/19707
Title: Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan
Authors: Ji, M
Cheng, TCE 
Keywords: Batch scheduling
Computational complexity
FPTAS
Makespan
Issue Date: 2010
Publisher: Elsevier
Source: European journal of operational research, 2010, v. 202, no. 1, p. 90-98 How to cite?
Journal: European journal of operational research 
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 ≤ U for a variable U ≥ 2 or B ≥ U for any constant U ≥ 2. For the case of B ≤ 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 ≥ 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.
URI: http://hdl.handle.net/10397/19707
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2009.05.021
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

26
Last Week
0
Last month
2
Citations as of Sep 8, 2017

WEB OF SCIENCETM
Citations

21
Last Week
0
Last month
1
Citations as of Sep 14, 2017

Page view(s)

55
Last Week
3
Last month
Checked on Sep 18, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.