General perfectly periodic scheduling

ABSTRACT

In a perfectly-periodic schedule, time is divided into time-slots, and each client is scheduled precisely every some predefined number of slots, called the period of that client. Periodic schedules are useful in wireless communication and other settings. The quality of a schedule is measured by the proportion between the requested and the granted periods: either the maximum over all jobs, or the average. There exist good scheduling algorithms for the average measure in the unit-length single-server model in which all jobs are one slot long, and at most one job is served in each time unit. In this paper we study the general model, where each job may have a different length, and m jobs can be served in parallel for some given m. We give a lower bound for this model which demonstrates the inherent difficulty of multiple lengths, and present a sequence of algorithms, culminating in an algorithm for the general case which is asymptotically optimal under the maximum ratio measure (and hence also the average ratio measure). The new algorithms utilize new techniques which are rather different from the known algorithms used for the unit-length model. Some of the algorithms improve on the best known bounds for the unit-length model.

REFERENCES

• 1: Bluetooth technical specifications, version 1.1. Available from http://www.bluetooth.com/, Feb. 2001.
• 2: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 3: M. H. Ammar and J. W. Wong. The design of teletext broadcast cycles. Performance Evaluation, 5(4):235-242, Dec 1985.
• 4: S. Anily, C. A. Glass, and R. Hassin. Scheduling of maintenance services to three machines. Annals of Operations Research, 86:375-391, 1999.
• 5: Amotz Bar-Noy , Randeep Bhatia , Joseph Naor , Baruch Schieber, Minimizing service and operation costs of periodic scheduling, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.11-20, January 25-27, 1998, San Francisco, California, United States
• 6: S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. A. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15:600-625, 1996.
• 7: A. Bar-Noy, V. Dreizin, and B. Patt-Shamir. Efficient Periodic Scheduling by Trees. To appear in INFOCOM 2002, June 2002.
• 8: Z. Brakeski, V. Dreizin, and B. Patt-Shamir. Dispatching in Perfectly-Periodic Schedules. Unpublished manuscript, 2001.
• 9: Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237984]
• 10: Amotz Bar-Noy , Aviv Nisgav , Boaz Patt-Shamir, Nearly optimal perfectly-periodic schedules, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.107-116, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383998]
• 11: Yon Dohn Chung , Myoung-Ho Kim, QEM: A Scheduling Method for Wireless Broadcast Data, Proceedings of the Sixth International Conference on Database Systems for Advanced Applications, p.135-142, April 19-21, 1999
• 12: Tomasz Imielinski , S. Viswanathan , B. R. Badrinath, Energy efficient indexing on air, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.25-36, May 24-27, 1994, Minneapolis, Minnesota, United States
• 13: Claire Kenyon , Nicolas Schabanel , Neal Young, Polynomial-time approximation scheme for data broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.659-666, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335398]
• 14: Sanjeev Khanna , Shiyu Zhou, On indexed data broadcast, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.463-472, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276859]
• 15: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 16: R. Tijdeman. The chairman assignment problem. Discrete Mathematics, 32:323-330, 1980.
• 17: Carl A. Waldspurger and William E. Weihl. Lottery scheduling: Flexible proportional-share resource management. In Proc. First Symposium on Operating Systems Design and Implementation, November 1994.
• 18: W. Wei and C. Liu. On a periodic maintenance problem. Operations Research Letters, 2:90-93, 1983.