Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/11962
Title: Optimal algorithms for single-machine scheduling with rejection to minimize the makespan
Authors: Lu, L
Ng, CT 
Zhang, L
Keywords: Competitive ratio
On-line algorithm
Rejection penalty
Scheduling
Issue Date: 2011
Publisher: Elsevier
Source: International journal of production economics, 2011, v. 130, no. 2, p. 153-158 How to cite?
Journal: International journal of production economics 
Abstract: In this paper we consider the single-machine scheduling problem with rejection. Each job has an arrival time, a processing time and a rejection penalty. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. First, we present a polynomial-time algorithm for the off-line problem when split is allowed. Second, for the on-line problem with arbitrary arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio 2. Finally, for the on-line problem with at most two distinct arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio (51)/2?1.618.
URI: http://hdl.handle.net/10397/11962
ISSN: 0925-5273
DOI: 10.1016/j.ijpe.2010.12.003
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

17
Last Week
0
Last month
0
Citations as of May 26, 2018

WEB OF SCIENCETM
Citations

16
Last Week
0
Last month
0
Citations as of May 11, 2018

Page view(s)

56
Last Week
0
Last month
Citations as of May 21, 2018

Google ScholarTM

Check

Altmetric


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