Normal-form preemption sequences for an open problem in scheduling theory

Bo Chen (), Ed Coffman (), Dariusz Dereniowski () and Wiesław Kubiak ()
Additional contact information
Bo Chen: University of Warwick
Ed Coffman: Columbia University
Dariusz Dereniowski: Gdańsk University of Technology
Wiesław Kubiak: Memorial University

Journal of Scheduling, 2016, vol. 19, issue 6, No 7, 728 pages

Abstract: Abstract Structural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on shifts, i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. These two parameters have been investigated for a large class of preemptive scheduling problems, but so far only rough bounds for these parameters have been derived for specific problems. This paper sharpens the bounds on these structural parameters for a well-known open problem in the theory of preemptive scheduling: Instances consist of in-trees of n unit-execution-time jobs with release dates, and the objective is to minimize the total completion time on two processors. This is among the current, tantalizing “threshold” problems of scheduling theory: Our literature survey reveals that any significant generalization leads to an NP-hard problem, but that any significant, but slight simplification leads to tractable problem with a polynomial-time solution. For the above problem, we show that the number of preemptions necessary for optimality need not exceed $$2n-1$$ 2 n - 1 ; that the number must be of order $${\varOmega }(\log n)$$ Ω ( log n ) for some instances; and that the minimum shift need not be less than $$2^{-2n+1}.$$ 2 - 2 n + 1 . These bounds are obtained by combinatorial analysis of optimal preemptive schedules rather than by the analysis of polytope corners for linear-program formulations of the problem, an approach to be found in earlier papers. The bounds immediately follow from a fundamental structural property called normality, by which minimal shifts of a job are exponentially decreasing functions. In particular, the first interval between a preempted job’s start and its preemption must be a multiple of 1 / 2, the second such interval must be a multiple of 1 / 4, and in general, the i-th preemption must occur at a multiple of $$2^{-i}$$ 2 - i . We expect the new structural properties to play a prominent role in finally settling a vexing, still-open question of complexity.

Keywords: Preemption; Parallel machines; In-tree; Release date; Scheduling algorithm; Total completion time (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-015-0446-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:19:y:2016:i:6:d:10.1007_s10951-015-0446-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-015-0446-9

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().