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 |
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 | Size | Format | |
---|---|---|---|---|
preempt-penalty.pdf | Pre-published version | 158.2 kB | Adobe PDF | View/Open |
Page views
129
Last Week
0
0
Last month
Citations as of Mar 24, 2024
Downloads
224
Citations as of Mar 24, 2024
SCOPUSTM
Citations
24
Last Week
0
0
Last month
0
0
Citations as of Mar 28, 2024
WEB OF SCIENCETM
Citations
22
Last Week
1
1
Last month
0
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.