A general framework for handling commitment in online throughput maximization

• 成果类型: Article
• 署名作者: Chen, Lin; Eberle, Franziska; Megow, Nicole; Schewior, Kevin; Stein, Cliff
• 署名单位: Texas Tech University System; Texas Tech University; University of Bremen; University of Cologne; Columbia University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01469-2
• 发表日期: 2020
• 页码: 215-247
• 关键词: Admission control; algorithm; delay

摘要

We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least 1+epsilon times its processing time, for some epsilon>0. We quantify the impact that different provider commitment requirements have on the performance of online algorithms. Our main contribution is one universal algorithmic framework for online job admission both with and without commitments. Without commitment, our algorithm with a competitive ratio of O(1/epsilon) is the best possible (deterministic) for this problem. For commitment models, we give the first non-trivial performance bounds. If the commitment decisions must be made before a job's slack becomes less than a delta-fraction of its size, we prove a competitive ratio of O(epsilon/((epsilon-delta)delta(2))), for 0