Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/60939
Title: Faster algorithms for single machine scheduling with release dates and rejection
Authors: Ou, J
Zhong, X
Li, CL 
Keywords: Algorithms
Rejection penalty
Release dates
Scheduling
Worst-case analysis
Issue Date: 2016
Publisher: Elsevier
Source: Information processing letters, 2016, v. 116, no. 8, p. 503-507 How to cite?
Journal: Information processing letters 
Abstract: We consider the single machine scheduling problem with release dates and job rejection with an objective of minimizing the makespan of the job schedule plus the total rejection penalty of the rejected jobs. Zhang et al. [6] have presented a 2-approximation algorithm with an O(n2) complexity for this problem and an exact algorithm with an O(n3) complexity for the special case with identical job processing times. In this note, we show that the 2-approximation algorithm developed by Zhang et al. [6] can be implemented in O(nlogn) time. We also develop a new exact algorithm with an improved complexity of O(n2logn) for the special case with identical job processing times. The second algorithm can be easily extended to solve the parallel-machine case with the same running time complexity, which answers an open question recently raised by Zhang and Lu [5].
URI: http://hdl.handle.net/10397/60939
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2016.02.008
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

1
Last Week
0
Last month
Citations as of Jul 29, 2017

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
Citations as of Aug 13, 2017

Page view(s)

22
Last Week
1
Last month
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



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