TY - GEN
T1 - A General Framework for Handling Commitment in Online Throughput Maximization
AU - Chen, Lin
AU - Eberle, Franziska
AU - Megow, Nicole
AU - Schewior, Kevin
AU - Stein, Cliff
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - 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 times its processing time, for some 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 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 fraction of its size, we prove a competitive ratio of for When a scheduler must commit upon starting a job, our bound is Finally, we observe that for scheduling with commitment the restriction to the “unweighted” throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms.
AB - 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 times its processing time, for some 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 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 fraction of its size, we prove a competitive ratio of for When a scheduler must commit upon starting a job, our bound is Finally, we observe that for scheduling with commitment the restriction to the “unweighted” throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms.
UR - http://www.scopus.com/inward/record.url?scp=85065888472&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-17953-3_11
DO - 10.1007/978-3-030-17953-3_11
M3 - Conference contribution
AN - SCOPUS:85065888472
SN - 9783030179526
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 141
EP - 154
BT - Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
A2 - Lodi, Andrea
A2 - Nagarajan, Viswanath
PB - Springer-Verlag
T2 - 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
Y2 - 22 May 2019 through 24 May 2019
ER -