文章基本信息

标题：Optimally Handling Commitment Issues in Online Throughput Maximization
本地全文：下载
作者：Franziska Eberle ; Nicole Megow ; Kevin Schewior 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：41:1-41:15
DOI：10.4230/LIPIcs.ESA.2020.41
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Deadline scheduling; throughput; online algorithms; competitive analysis