Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/16037
Title: How small are shifts required in optimal preemptive schedules?
Authors: Coffman, EG
Ng, CT 
Timkovsky, VG
Keywords: Due dates
Identical parallel machines
Preemptive scheduling
Release dates
Issue Date: 2015
Publisher: Springer
Source: Journal of scheduling, 2015, v. 18, no. 2, p. 155-163 How to cite?
Journal: Journal of scheduling 
Abstract: An event in a schedule is a job start, interruption, resumption or completion time. A shift in a schedule is an non-idling interval between two events that does not contain other events. If a scheduling problem with a regular criterion has only integer data (and we consider here only such problems), then the length of smallest shifts required in optimal nonpreemptive schedules is obviously 1. The length of smallest shifts required in optimal preemptive schedules, however, can be infinitely small. As Sauer and Stone (Order 4:195–206, 1987) showed more than 25 years ago, shifts of length less than (Formula presented.) are not required in shortest preemptive schedules of (Formula presented.) unit-length jobs with precedence constraints on (Formula presented.) identical parallel machines. They showed, on the other hand, that there are instances for infinitely many (Formula presented.) such that shifts of length less than (Formula presented.) can be required if (Formula presented.). In this paper, we continue research in the same direction and strengthen their results, finding the respective tighter bounds, (Formula presented.) and  (Formula presented.). We also obtain similar results for other preemptive scheduling problems on identical parallel machines. A useful consequence of certain of these results is that preemptive scheduling problems with unequal release dates and/or unequal due dates can require even smaller shifts for optimality. We also identify problems whose optimal preemptive schedules do not require shifts of length less than (Formula presented.).
URI: http://hdl.handle.net/10397/16037
ISSN: 1094-6136
EISSN: 1099-1425
DOI: 10.1007/s10951-013-0355-8
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
0
Citations as of Nov 8, 2017

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
0
Citations as of Nov 17, 2017

Page view(s)

75
Last Week
1
Last month
Checked on Nov 12, 2017

Google ScholarTM

Check

Altmetric



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