Online scheduling to minimize the maximum delay factor

Chandra Chekuri, Benjamin Moseley

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

Abstract

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
Pages1116-1125
Number of pages10
StatePublished - Sep 21 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

Other

Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew York, NY
Period1/4/091/6/09

    Fingerprint

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Chekuri, C., & Moseley, B. (2009). Online scheduling to minimize the maximum delay factor. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1116-1125). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).