Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/15480
Title: The unbounded parallel-batch scheduling with rejection
Authors: Zhang, LQ
Lu, LF
Ng, CT 
Keywords: parallel-batch scheduling
polynomial-time algorithm
rejection penalty
Issue Date: 2012
Publisher: Palgrave Macmillan Ltd
Source: Journal of the operational research society, 2012, v. 63, no. 3, p. 293-298 How to cite?
Journal: Journal of the Operational Research Society 
Abstract: In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs; (2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs; (3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs; (4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them.
URI: http://hdl.handle.net/10397/15480
DOI: 10.1057/jors.2011.31
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
Citations as of Apr 3, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
0
Citations as of Apr 26, 2017

Page view(s)

31
Last Week
0
Last month
Checked on Apr 23, 2017

Google ScholarTM

Check

Altmetric



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