How small are shifts required in optimal preemptive schedules?

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),...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2015-04, Vol.18 (2), p.155-163
Main Authors: Coffman, E. G., Ng, C. T., Timkovsky, V. G.
Format: Article
Language:English
Subjects:
Artificial Intelligence
Business and Management
Calculus of Variations and Optimal Control
Optimization
Completion time
Criteria
Intervals
Job shops
Operations Research/Decision Theory
Optimization
Precedence constraints
Preempting
Release dates
Schedules
Scheduling
Studies
Supply Chain Management
Texts
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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  m - n are not required in shortest preemptive schedules of  n unit-length jobs with precedence constraints on m identical parallel machines. They showed, on the other hand, that there are instances for infinitely many n such that shifts of length less than  ( m - 1 ) - n / ( 3 m ) ( m - 2 ) / m can be required if  m ≥ 3 . In this paper, we continue research in the same direction and strengthen their results, finding the respective tighter bounds,  m - ( n + 1 ) / 2 and   ( m - 1 ) - n / ( m + 3 ) . 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  1 / m .
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-013-0355-8