2026-07-20T15:08:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15517 2024-03-06T10:55:29Z ddc:004 open_access

Scheduling in the Secretary Model Albers, Susanne Janke, Maximilian Scheduling makespan minimization online algorithm competitive analysis lower bound random-order secretary problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Susanne Albers and Maximilian Janke 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.6 urn:nbn:de:0030-drops-155172 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.6 eng https://creativecommons.org/licenses/by/4.0/legalcode