Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/1076
PIRA download icon_1.1View/Download Full Text
Title: Minimizing total completion time subject to job release dates and preemption penalties
Authors: Liu, Z
Cheng, TCE 
Issue Date: Jul-2004
Source: Journal of scheduling, July 2004, v. 7, no. 4, p. 313-327
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.
Keywords: Preemptive scheduling
Preemption penalty
Setup time
Publisher: Springer
Journal: Journal of scheduling 
ISSN: 1094-6136
EISSN: 1099-1425
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
Open Access Information
Status open access
File Version Final Accepted Manuscript
Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page views

129
Last Week
0
Last month
Citations as of Mar 24, 2024

Downloads

224
Citations as of Mar 24, 2024

SCOPUSTM   
Citations

24
Last Week
0
Last month
0
Citations as of Mar 28, 2024

WEB OF SCIENCETM
Citations

22
Last Week
1
Last month
0
Citations as of Mar 28, 2024

Google ScholarTM

Check

Altmetric


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