License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.41
URN: urn:nbn:de:0030-drops-129076
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12907/
Eberle, Franziska ;
Megow, Nicole ;
Schewior, Kevin
Optimally Handling Commitment Issues in Online Throughput Maximization
Abstract
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.
BibTeX - Entry
@InProceedings{eberle_et_al:LIPIcs:2020:12907,
author = {Franziska Eberle and Nicole Megow and Kevin Schewior},
title = {{Optimally Handling Commitment Issues in Online Throughput Maximization}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {41:1--41:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12907},
URN = {urn:nbn:de:0030-drops-129076},
doi = {10.4230/LIPIcs.ESA.2020.41},
annote = {Keywords: Deadline scheduling, throughput, online algorithms, competitive analysis}
}
|
Keywords: |
|
Deadline scheduling, throughput, online algorithms, competitive analysis |
|
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
