License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.6
URN: urn:nbn:de:0030-drops-155172
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15517/
Albers, Susanne ;
Janke, Maximilian
Scheduling in the Secretary Model
Abstract
This paper studies online makespan minimization in the secretary model. Jobs, specified by their processing times, are presented in a uniformly random order. The input size n is known in advance. An online algorithm has to non-preemptively assign each job permanently and irrevocably to one of m parallel and identical machines such that the expected time it takes to process them all, the makespan, is minimized.
We give two deterministic algorithms. First, a straightforward adaptation of the semi-online strategy Light Load [Albers and Hellwig, 2012] provides a very simple approach retaining its competitive ratio of 1.75. A new and sophisticated algorithm is 1.535-competitive. These competitive ratios are not only obtained in expectation but, in fact, for all but a very tiny fraction of job orders.
Classically, online makespan minimization only considers the worst-case order. Here, no competitive ratio below 1.885 for deterministic algorithms and 1.581 using randomization is possible. The best randomized algorithm so far is 1.916-competitive. Our results show that classical worst-case orders are quite rare and pessimistic for many applications.
We complement our results by providing first lower bounds. A competitive ratio obtained on nearly all possible job orders must be at least 1.257. This implies a lower bound of 1.043 for both deterministic and randomized algorithms in the general model.
BibTeX - Entry
@InProceedings{albers_et_al:LIPIcs.FSTTCS.2021.6,
author = {Albers, Susanne and Janke, Maximilian},
title = {{Scheduling in the Secretary Model}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {6:1--6:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-215-0},
ISSN = {1868-8969},
year = {2021},
volume = {213},
editor = {Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15517},
URN = {urn:nbn:de:0030-drops-155172},
doi = {10.4230/LIPIcs.FSTTCS.2021.6},
annote = {Keywords: Scheduling, makespan minimization, online algorithm, competitive analysis, lower bound, random-order, secretary problem}
}
|
Keywords: |
|
Scheduling, makespan minimization, online algorithm, competitive analysis, lower bound, random-order, secretary problem |
|
Collection: |
|
41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
29.11.2021 |
