2026-07-21T14:19:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21007 2024-09-16T06:02:38Z ddc:004 open_access

Scheduling on a Stochastic Number of Machines Buchem, Moritz Eberle, Franziska Kasuya Rosado, Hugo Kooki Schewior, Kevin Wiese, Andreas scheduling approximation algorithms stochastic machines makespan max-min fair allocation dynamic programming We consider a new scheduling problem on parallel identical machines in which the number of machines is initially not known, but it follows a given probability distribution. Only after all jobs are assigned to a given number of bags, the actual number of machines is revealed. Subsequently, the jobs need to be assigned to the machines without splitting the bags. This is the stochastic version of a related problem introduced by Stein and Zhong [SODA 2018, TALG 2020] and it is, for example, motivated by bundling jobs that need to be scheduled by data centers. We present two PTASs for the stochastic setting, computing job-to-bag assignments that (i) minimize the expected maximum machine load and (ii) maximize the expected minimum machine load (like in the Santa Claus problem), respectively. The former result follows by careful enumeration combined with known PTASs. For the latter result, we introduce an intricate dynamic program that we apply to a suitably rounded instance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moritz Buchem and Franziska Eberle and Hugo Kooki Kasuya Rosado and Kevin Schewior and Andreas Wiese 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.14 urn:nbn:de:0030-drops-210073 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.14 eng https://creativecommons.org/licenses/by/4.0/legalcode