Nearly optimal perfectly periodic schedules |
| |
Authors: | Amotz Bar-Noy Aviv Nisgav Boaz Patt-Shamir |
| |
Affiliation: | (1) Department of Computer and Information Science, CUNY, Brooklyn, NY 11210, USA (e-mail: amotz@sci.brooklyn.cuny.edu) , US;(2) Department of Electrical Engineering, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: {aviv,boaz}@eng.tau.ac.il) , IL |
| |
Abstract: | We consider the problem of scheduling a set of pages on a single broadcast channel using time-multiplexing. In a perfectly periodic schedule, time is divided into equal size slots, and each page is transmitted in a time slot precisely every fixed interval of time (the period of the page). We study the case in which each page i has a given demand probability , and the goal is to design a perfectly periodic schedule that minimizes the average time a random client waits until its
page is transmitted. We seek approximate polynomial solutions. Approximation bounds are obtained by comparing the costs of
a solution provided by an algorithm and a solution to a relaxed (non-integral) version of the problem. A key quantity in our
methodology is a fraction we denote by , that depends on the maximum demand probability: . The best known polynomial algorithm to date guarantees an approximation of . In this paper, we develop a tree-based methodology for perfectly periodic scheduling, and using new techniques, we derive
algorithms with better bounds. For small values, our best algorithm guarantees approximation of . On the other hand, we show that the integrality gap between the cost of any perfectly periodic schedule and the cost of
the fractional problem is at least . We also provide algorithms with good performance guarantees for large values of .
Received: December 2001 / Accepted: September 2002 |
| |
Keywords: | : Perfectly periodic scheduling – Broadcast disk – Asymmetric communication – Maintenance scheduling |
本文献已被 SpringerLink 等数据库收录! |
|