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

The power of reordering for online minimum makespan scheduling

Tools
- Tools
+ Tools

Englert, Matthias, Özmen, Deniz and Westermann, Matthias (2014) The power of reordering for online minimum makespan scheduling. SIAM Journal on Computing, Volume 43 (Number 3). pp. 1220-1237. doi:10.1137/130919738 ISSN 1095-7111.

[img]
Preview
PDF
WRAP_Englert_paper.pdf - Accepted Version - Requires a PDF viewer.

Download (565Kb) | Preview
Official URL: http://dx.doi.org/10.1137/130919738

Request Changes to record.

Abstract

In the classic minimum makespan scheduling problem, we are given an input sequence of jobs with processing times. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we do not require that each arriving job has to be assigned immediately to one of the machines. A reordering buffer with limited storage capacity can be used to reorder the input sequence in a restricted fashion so as to schedule the jobs with a smaller makespan. This is a natural extension of lookahead. We present an extensive study of the power and limits of online reordering for minimum makespan scheduling. As a main result, we give, for $m$ identical machines, tight and, in comparison to the problem without reordering, much improved bounds on the competitive ratio for minimum makespan scheduling with reordering buffers. Depending on m, the achieved competitive ratio lies between 4/3 and 1.4659. This optimal ratio is achieved with a buffer of size Theta(m). We show that larger buffer sizes do not result in an additional advantage and that a buffer of size Omega(m) is necessary to achieve this competitive ratio. Further, we present several algorithms for different buffer sizes. For m uniformly related machines, we give a scheduling algorithm that achieves a competitive ratio of 2 with a reordering buffer of size m. Considering that the best known competitive ratio for uniformly related machines without reordering is 5.828, this result further emphasizes the power of online reordering.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Computer scheduling -- Mathematical models
Journal or Publication Title: SIAM Journal on Computing
Publisher: Society for Industrial and Applied Mathematics
ISSN: 1095-7111
Official Date: 27 May 2014
Dates:
DateEvent
27 May 2014Available
3 February 2014Accepted
3 May 2013Submitted
Volume: Volume 43
Number: Number 3
Number of Pages: 18
Page Range: pp. 1220-1237
DOI: 10.1137/130919738
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 27 December 2015
Date of first compliant Open Access: 27 December 2015
Funder: Deutsche Forschungsgemeinschaft (DFG), University of Warwick. Centre for Discrete Mathematics and Its Applications, Engineering and Physical Sciences Research Council (EPSRC)
Grant number: WE 2842/1 (DFG), EP/D063191/1 (EPSRC)
Embodied As: 1

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

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