TY - GEN

T1 - Online scheduling to minimize the maximum delay factor

AU - Chekuri, Chandra

AU - Moseley, Benjamin

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - In this paper two scheduling models are addressed. First is the standard model (unicast) where requests (or jobs) are independent. The other is the broadcast model where broadcasting a page can satisfy multiple outstanding requests for that page. We consider online scheduling of requests when they have deadlines. Unlike previous models, which mainly consider the objective of maximizing throughput while respecting deadlines, here we focus on scheduling all the given requests with the goal of minimizing the maximum delay factor. The delay factor of a schedule is defined to be the minimum α ≥ 1 such that each request i is completed by time ai + α(di - ai) where ai is the arrival time of request i and di is its deadline. Delay factor generalizes the previously defined measure of maximum stretch which is based only the processing times of requests [9, 11]. We prove strong lower bounds on the achievable competitive ratios for delay factor scheduling even with unit-time requests. Motivated by this, we consider resource augmentation analysis [24] and prove the following positive results. For the unicast model we give algorithms that are (1 + ∈)-speed O(1/∈)-competitive in both the single machine and multiple machine settings. In the broadcast model we give an algorithm for same-sized pages that is (2 + ∈)-speed O(1/∈2)-competitive. For arbitrary page sizes we give an algorithm that is (4 + ∈)-speed O(1/∈2)- competitive.

AB - In this paper two scheduling models are addressed. First is the standard model (unicast) where requests (or jobs) are independent. The other is the broadcast model where broadcasting a page can satisfy multiple outstanding requests for that page. We consider online scheduling of requests when they have deadlines. Unlike previous models, which mainly consider the objective of maximizing throughput while respecting deadlines, here we focus on scheduling all the given requests with the goal of minimizing the maximum delay factor. The delay factor of a schedule is defined to be the minimum α ≥ 1 such that each request i is completed by time ai + α(di - ai) where ai is the arrival time of request i and di is its deadline. Delay factor generalizes the previously defined measure of maximum stretch which is based only the processing times of requests [9, 11]. We prove strong lower bounds on the achievable competitive ratios for delay factor scheduling even with unit-time requests. Motivated by this, we consider resource augmentation analysis [24] and prove the following positive results. For the unicast model we give algorithms that are (1 + ∈)-speed O(1/∈)-competitive in both the single machine and multiple machine settings. In the broadcast model we give an algorithm for same-sized pages that is (2 + ∈)-speed O(1/∈2)-competitive. For arbitrary page sizes we give an algorithm that is (4 + ∈)-speed O(1/∈2)- competitive.

UR - http://www.scopus.com/inward/record.url?scp=70349117291&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349117291&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973068.121

DO - 10.1137/1.9781611973068.121

M3 - Conference contribution

AN - SCOPUS:70349117291

SN - 9780898716801

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1116

EP - 1125

BT - Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery (ACM)

T2 - 20th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 4 January 2009 through 6 January 2009

ER -