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: https://drops.dagstuhl.de/opus/volltexte/2021/15517/
Go to the corresponding LIPIcs Volume Portal


Albers, Susanne ; Janke, Maximilian

Scheduling in the Secretary Model

pdf-format:
LIPIcs-FSTTCS-2021-6.pdf (0.9 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI