Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

Tools
- Tools
+ Tools

Chen, Bo, Coffman, Ed , Dereniowski, Dariusz and Kubiak, Wiesław (2016) Normal-form preemption sequences for an open problem in scheduling theory. Journal of Scheduling, 19 (6). pp. 701-728. doi:10.1007/s10951-015-0446-9

[img] PDF
WRAP_art%3A10.1007%2Fs10951-015-0446-9.pdf - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (1745Kb)
[img]
Preview
PDF
WRAP_art%3A10.1007%2Fs10951-015-0446-9.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (1764Kb) | Preview
[img] PDF
WRAP_9471193-wbs-180815-josh_preprint_2015-07-29.pdf - Accepted Version
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (826Kb)
Official URL: http://dx.doi.org/10.1007/s10951-015-0446-9

Request Changes to record.

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; that the number must be of order Ω(logn) for some instances; and that the minimum shift need not be less than 2−2n+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. We expect the new structural properties to play a prominent role in finally settling a vexing, still-open question of complexity.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
T Technology > TS Manufactures
Divisions: Faculty of Science, Engineering and Medicine > Science > Mathematics
Faculty of Social Sciences > Warwick Business School
Library of Congress Subject Headings (LCSH): Computer scheduling -- Mathematical models -- Research, Operating systems (Computers) -- Algorithms
Journal or Publication Title: Journal of Scheduling
Publisher: Springer New York LLC
ISSN: 1094-6136
Official Date: December 2016
Dates:
DateEvent
December 2016Published
28 August 2015Available
29 July 2015Accepted
Volume: 19
Number: 6
Number of Pages: 27
Page Range: pp. 701-728
DOI: 10.1007/s10951-015-0446-9
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
Funder: Natural Sciences and Engineering Research Council of Canada (NSERC), Polska. Ministerstwo Nauki i Szkolnictwa Wyższego [Ministry of Science and Higher Education], Narodowe Centrum Nauki [Polish National Science Center]
Grant number: OPG0105675 (NSERC), DEC-2011/02/A/ST6/00201

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us