Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/21642
Title: Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan
Authors: Li, S
Ng, CT 
Cheng, TCE 
Yuan, J
Keywords: Batching
Deterioration
Dynamic programming
Release dates
Scheduling
Issue Date: 2011
Publisher: Elsevier
Source: European journal of operational research, 2011, v. 210, no. 3, p. 482-488 How to cite?
Journal: European journal of operational research 
Abstract: We consider the problem of scheduling n deteriorating jobs with release dates on a single batching machine. Each job's processing time is an increasing simple linear function of its starting time. The machine can process up to b jobs simultaneously as a batch. The objective is to minimize the maximum completion time, i.e., makespan. For the unbounded model, i.e., b = ∞, we obtain an O(n log n) dynamic programming algorithm. For the bounded model, i.e., b < n, we first show that the problem is binary NP-hard even if there are only two distinct release dates. Then we present O(nb) and O((nb/h)h) algorithms for the case where the job processing order is predetermined in advance and for the case where there are h, h ≥ 2, distinct deteriorating rates, respectively. Furthermore, we provide a fully polynomial-time approximation scheme for the case where the number of distinct release dates is a constant.
URI: http://hdl.handle.net/10397/21642
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2010.11.021
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

25
Last Week
0
Last month
1
Citations as of May 19, 2017

WEB OF SCIENCETM
Citations

19
Last Week
0
Last month
1
Citations as of May 21, 2017

Page view(s)

38
Last Week
2
Last month
Checked on May 21, 2017

Google ScholarTM

Check

Altmetric



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