The Library
The power of reordering for online minimum makespan scheduling
Tools
Englert, Matthias, Özmen, Deniz and Westermann, Matthias (2008) The power of reordering for online minimum makespan scheduling. In: 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, 25-28 Oct 2008. Published in: Symposium on Foundations of Computer Science. Annual Proceedings pp. 603-612. doi:10.1109/FOCS.2008.46 ISSN 1523-8288.
PDF
04690993.pdf Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (283Kb) |
Official URL: http://dx.doi.org/10.1109/FOCS.2008.46
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 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. Among others, we introduce, for every buffer size k isin [1, (m+ 1)/2], a (2 middot 1/(m middot k+ 1))-competitive algorithm, which nicely generalizes the well-known result of Graham. 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 knowncompetitive ratio for uniformly related machines without reordering is 5.828, this result emphasizes the power of online reordering further more.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Symposium on Foundations of Computer Science. Annual Proceedings | ||||
Publisher: | IEEE Computer Society | ||||
ISSN: | 1523-8288 | ||||
Book Title: | 2008 49th Annual IEEE Symposium on Foundations of Computer Science | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Page Range: | pp. 603-612 | ||||
DOI: | 10.1109/FOCS.2008.46 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 49th Annual IEEE Symposium on Foundations of Computer Science | ||||
Type of Event: | Other | ||||
Location of Event: | Philadelphia, PA | ||||
Date(s) of Event: | 25-28 Oct 2008 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |