Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/1076
DC Field | Value | Language |
---|---|---|
dc.contributor | Department of Logistics and Maritime Studies | - |
dc.creator | Liu, Z | - |
dc.creator | Cheng, TCE | - |
dc.date.accessioned | 2014-12-11T08:24:05Z | - |
dc.date.available | 2014-12-11T08:24:05Z | - |
dc.identifier.issn | 1094-6136 | - |
dc.identifier.uri | http://hdl.handle.net/10397/1076 | - |
dc.language.iso | en | en_US |
dc.publisher | Springer | en_US |
dc.rights | Journal of Scheduling © 2004 Kluwer Academic Publishers (Springer). The original publication is available at www.springerlink.com. | en_US |
dc.subject | Preemptive scheduling | en_US |
dc.subject | Preemption penalty | en_US |
dc.subject | Setup time | en_US |
dc.title | Minimizing total completion time subject to job release dates and preemption penalties | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.spage | 313 | - |
dc.identifier.epage | 327 | - |
dc.identifier.volume | 7 | - |
dc.identifier.issue | 4 | - |
dc.identifier.doi | 10.1023/B:JOSH.0000031424.35504.c4 | - |
dcterms.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. | - |
dcterms.accessRights | open access | en_US |
dcterms.bibliographicCitation | Journal of scheduling, July 2004, v. 7, no. 4, p. 313-327 | - |
dcterms.isPartOf | Journal of scheduling | - |
dcterms.issued | 2004-07 | - |
dc.identifier.isi | WOS:000223473700004 | - |
dc.identifier.scopus | 2-s2.0-3042755389 | - |
dc.identifier.eissn | 1099-1425 | - |
dc.identifier.rosgroupid | r22766 | - |
dc.description.ros | 2004-2005 > Academic research: refereed > Publication in refereed journal | - |
dc.description.oa | Accepted Manuscript | en_US |
dc.identifier.FolderNumber | OA_IR/PIRA | en_US |
dc.description.pubStatus | Published | en_US |
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
134
Last Week
0
0
Last month
Citations as of Apr 21, 2024
Downloads
224
Citations as of Apr 21, 2024
SCOPUSTM
Citations
24
Last Week
0
0
Last month
0
0
Citations as of Apr 19, 2024
WEB OF SCIENCETM
Citations
22
Last Week
1
1
Last month
0
0
Citations as of Apr 25, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.