License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.68
URN: urn:nbn:de:0030-drops-124750
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12475/
Albers, Susanne ;
Janke, Maximilian
Scheduling in the Random-Order Model
Abstract
Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to m identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that Greedy is (2-1/m)-competitive [Graham, 1966]. The best deterministic online algorithm currently known achieves a competitive ratio of 1.9201 [Fleischer and Wahl, 2000]. No deterministic online strategy can obtain a competitiveness smaller than 1.88 [Rudin III, 2001].
In this paper, we study online makespan minimization in the popular random-order model, where the jobs of a given input arrive as a random permutation. It is known that Greedy does not attain a competitive factor asymptotically smaller than 2 in this setting [Osborn and Torng, 2008]. We present the first improved performance guarantees. Specifically, we develop a deterministic online algorithm that achieves a competitive ratio of 1.8478. The result relies on a new analysis approach. We identify a set of properties that a random permutation of the input jobs satisfies with high probability. Then we conduct a worst-case analysis of our algorithm, for the respective class of permutations. The analysis implies that the stated competitiveness holds not only in expectation but with high probability. Moreover, it provides mathematical evidence that job sequences leading to higher performance ratios are extremely rare, pathological inputs. We complement the results by lower bounds for the random-order model. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 4/3. Moreover, no deterministic online algorithm can attain a competitiveness smaller than 3/2 with high probability.
BibTeX - Entry
@InProceedings{albers_et_al:LIPIcs:2020:12475,
author = {Susanne Albers and Maximilian Janke},
title = {{Scheduling in the Random-Order Model}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {68:1--68:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12475},
URN = {urn:nbn:de:0030-drops-124750},
doi = {10.4230/LIPIcs.ICALP.2020.68},
annote = {Keywords: Scheduling, makespan minimization, online algorithm, competitive analysis, lower bound, random-order}
}
|
Keywords: |
|
Scheduling, makespan minimization, online algorithm, competitive analysis, lower bound, random-order |
|
Collection: |
|
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
29.06.2020 |
