2026-07-21T20:02:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24495 2025-12-16T13:59:57Z ddc:004 open_access

Online Makespan Scheduling Under Scenarios Ergen, Ekin online scheduling scenario-based model online algorithms We consider a natural extension of online makespan scheduling on identical parallel machines by introducing scenarios. A scenario is a subset of jobs, and the task of our problem is to find a global assignment of the jobs to machines so that the maximum makespan under a scenario, i.e., the maximum makespan of any schedule restricted to a scenario, is minimized. For varying values of the number of scenarios and machines, we explore the competitiveness of online algorithms. We prove tight and near-tight bounds, several of which are achieved through novel constructions. In particular, we leverage the interplay between the unit processing time case of our problem and the hypergraph coloring problem both ways: We use hypergraph coloring techniques to steer an adversarial family of instances proving lower bounds for our problem, which in turn leads to lower bounds for several variants of online hypergraph coloring. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ekin Ergen 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.27 urn:nbn:de:0030-drops-244950 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.27 eng https://creativecommons.org/licenses/by/4.0/legalcode