Online scheduling to minimize the maximum delay factor

Chandra Chekuri, Benjamin Moseley

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Number of pages10
ISBN (Print)9780898716801
StatePublished - 2009
Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
Duration: Jan 4 2009Jan 6 2009

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityNew York, NY

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Online scheduling to minimize the maximum delay factor'. Together they form a unique fingerprint.

Cite this