### 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 a_{i} + α(d_{i} - a_{i}) where a_{i} 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 1116-1125 |

Number of pages | 10 |

State | Published - Sep 21 2009 |

Event | 20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States Duration: Jan 4 2009 → Jan 6 2009 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 20th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | New York, NY |

Period | 1/4/09 → 1/6/09 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Mathematics(all)

### Cite this

*Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 1116-1125). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).