2026-08-12T02:27:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12907 2024-03-06T10:51:03Z ddc:004 open_access

Optimally Handling Commitment Issues in Online Throughput Maximization Eberle, Franziska Megow, Nicole Schewior, Kevin Deadline scheduling throughput online algorithms competitive analysis We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on m machines that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis, it is commonly required that jobs contain some slack ε > 0, which means that the feasible time window for scheduling a job is at least 1+ε times its processing time. In this paper, we answer the question on how to handle commitment requirements which enforce that a scheduler has to guarantee at a certain point in time the completion of admitted jobs. This is very relevant, e.g., in providing cloud-computing services and disallows last-minute rejections of critical tasks. We present the first online algorithm for handling commitment on parallel machines for arbitrary slack ε. When the scheduler must commit upon starting a job, the algorithm is Θ(1/ε)-competitive. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment on a single machine. If commitment decisions must be made before a job’s slack becomes less than a δ-fraction of its size, we prove a competitive ratio of 𝒪(1/(ε - δ)) for 0 < δ < ε. This result nicely interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithms admits any bounded competitive ratio. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Franziska Eberle and Nicole Megow and Kevin Schewior 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.41 urn:nbn:de:0030-drops-129076 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.41 eng https://creativecommons.org/licenses/by/3.0/legalcode