Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/1076
Title: Minimizing total completion time subject to job release dates and preemption penalties
Authors: Liu, Z
Cheng, TCE 
Keywords: Preemptive scheduling
Preemption penalty
Setup time
Issue Date: Jul-2004
Publisher: Kluwer Academic Publishers (Springer Netherlands)
Source: Journal of scheduling, July 2004, v. 7, no. 4, p. 313-327 How to cite?
Journal: Journal of scheduling 
Abstract: Extensive research has been devoted to preemptive scheduling. However, little attention has been paid to problems where a certain time penalty must be incurred if preemption is allowed. In this paper, we consider the single-machine scheduling problem of minimizing the total completion time subject to job release dates and preemption penalties, where each time a job is started, whether initially or after being preempted, a job-independent setup must take place. The problem is proved to be strongly NP-hard even if the setup time is one unit. We also study a natural extension of a greedy algorithm, which is optimal in the absence of preemption penalty. It is proved that the algorithm has a worst-case performance bound of 25/16, even when the maximum completion time, i.e., makespan, criterion is considered simultaneously.
URI: http://hdl.handle.net/10397/1076
ISSN: 1094-6136 (print)
1099-1425 (online)
DOI: 10.1023/B:JOSH.0000031424.35504.c4
Rights: Journal of Scheduling © 2004 Kluwer Academic Publishers (Springer). The original publication is available at www.springerlink.com.
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
preempt-penalty.pdfPre-published version158.2 kBAdobe PDFView/Open
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 Jun 4, 2016

WEB OF SCIENCETM
Citations

16
Last Week
0
Last month
0
Citations as of Jul 24, 2016

Page view(s)

324
Last Week
2
Last month
Checked on Jul 24, 2016

Download(s)

828
Checked on Jul 24, 2016

Google ScholarTM

Check

Altmetric



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