Windows scheduling of arbitrary length jobs on parallel machines

ABSTRACT

The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I =\ang(w₁, l₁),(w₂, l ₂),...,(w_n, l_n) of n pairs of positive integers that are associated with the jobs 1,2,...,n, respectively. The processing length of job i is l_i slots (a slot is the processing time of one length unit). The goal is to repeatedly and non-preemptively schedule all the jobs on the fewest possible parallel machines such that the gap (window) between two consecutive executions of the first slot of job i is at most w_i slots. This problem arises in push broadcast systems in which data is transmitted on parallel channels.

The problem is NP-hard even for unit-length jobs and a (1+Σ)-approximation algorithm is known for this case by approximating the natural lower bound W(I)=Σ₌₁ⁿ (1/W_i). The techniques used for approximating unit-length jobs cannot be applied for arbitrary-length jobs mainly because the optimal number of machines might be arbitrarily larger than the generalized lower bound W(I)=Σ₌₁ⁿ (l_i/w_i).

Our main result is an 8-approximation algorithm for the generalized problem using new methods, different from those used for the unit-length case. We also present an algorithm that uses 2(1+Σ)W(I)+ log w_max machines and a greedy algorithm that is based on a new tree representation of schedules. The greedy algorithm is optimal for some special and simulations show that it performs very well in practice.

REFERENCES

• 1: S. Acharya, M. J. Franklin, and S. Zdonik. Dissemination-based data delivery using broadcast disks. IEEE Personal Comm., 2(6):50--60, 1995.
• 2: H. Ammar and J. W. Wong. The design of teletext broadcast cycles. Performance Evaluation, 5(4):235--242, 1985.
• 3: Amotz Bar-Noy , Randeep Bhatia , Joseph (Seffi) Naor , Baruch Schieber, Minimizing Service and Operation Costs of Periodic Scheduling, Mathematics of Operations Research, v.27 n.3, p.518-544, August 2002 [doi>10.1287/moor.27.3.518.314]
• 4: Amotz Bar-Noy , Richard E. Ladner, Windows Scheduling Problems for Broadcast Systems, SIAM Journal on Computing, v.32 n.4, p.1091-1113, 2003 [doi>10.1137/S009753970240447X]
• 5: Amotz Bar-Noy , Richard E. Ladner , Tami Tamir, Scheduling techniques for media-on-demand, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 6: Amotz Bar-Noy , Richard E. Ladner , Tami Tamir, Windows scheduling as a restricted version of Bin Packing, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 7: Amotz Bar-Noy , Joseph Naor , Baruch Schieber, Pushing dependent data in clients-providers-servers systems, Wireless Networks, v.9 n.5, p.421-430, September 2003 [doi>10.1023/A:1024632031440]
• 8: Amotz Bar-Noy , Aviv Nisgav , Boaz Patt-Shamir, Nearly optimal perfectly periodic schedules, Distributed Computing, v.15 n.4, p.207-220, December 2002 [doi>10.1007/s00446-002-0085-1]
• 9: 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.
• 10: Sanjoy K. Baruah , Shun-Shii Lin, Pfair Scheduling of Generalized Pinwheel Task Systems, IEEE Transactions on Computers, v.47 n.7, p.812-816, July 1998 [doi>10.1109/12.709381 ]
• 11: Zvika Brakerski , Aviv Nisgav , Boaz Patt-Shamir, General perfectly periodic scheduling, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571854]
• 12: Y. Chan and F. Chin. Schedulers for larger classes of pinwheel instances. Algorithmica, 9:425--462, 1993.
• 13: E. G. Coffman, Jr. , M. R. Garey , D. S. Johnson, Approximation algorithms for bin packing: a survey, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 14: Lars Engebretsen , Madhu Sudan, Harmonic broadcasting is optimal, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.431-432, January 06-08, 2002, San Francisco, California
• 15: William Evans , David Kirkpatrick, Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 16: E. A. Feinberg, M. Bender, M. Curry, D. Huang, T. Koutsoudis, and J. Bernstein. Sensor resource management for an airborne early warning radar. In Proceedings of SPIE - The International Society of Optical Engineering, 145--156, 2002.
• 17: E. A. Feinberg and M. Curry. Online scheduling: generalized pinwheel problem. In Proceedings of the 42-nd IEEE Conference on Decision and Control (CDC), 4333--4338, 2003.
• 18: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 19: V. Gondhalekar, R. Jain, and J. Werth. Scheduling on airdisks: efficient access to personalized information services via periodic wireless data broadcast. IEEE International Conference on Communications (ICC), 3:1276--1280, 1997.
• 20: Lixin Gao , Jim Kurose , Don Towsley, Efficient schemes for broadcasting popular videos, Multimedia Systems, v.8 n.4, p.284-294, July 2002 [doi>10.1007/s005300100049]
• 21: R. Holte, A. Mok, L. Rosier, I. Tulchinsky, and D. Varvel. The pinwheel: A real-time scheduling problem. In Proc. of the 22-nd Hawaii International Conference on System Sciences, 693--702, 1989.
• 22: Robert Holte , Louis Rosier , Igor Tulchinsky , Donald Varvel, Pinwheel scheduling with two distinct numbers, Theoretical Computer Science, v.100 n.1, p.105-135, June 22, 1992 [doi>10.1016/0304-3975(92)90365-M ]
• 23: Kien A. Hua , Simon Sheu, An Efficient Periodic Broadcast Technique for Digital VideoLibraries, Multimedia Tools and Applications, v.10 n.2-3, p.157-177, April 2000
• 24: L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Transactions on Broadcasting, 43(3):268--271, 1997.
• 25: C. Kenyon and N. Schabanel. The data broadcast problem with non-uniform transmission times. Algorithmica, 35(2):146--175, 2003.
• 26: 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]
• 27: 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]
• 28: R. Tijdeman. The chairman assignment problem. Discrete Mathematics, 32:323--330, 1980.
• 29: W. F. Vega and G.S. Leuker. Bin packing can be solved within 1+ε in linear time. Combinatorica, 1:349--355, 1981.
• 30: S. Viswanathan , T. Imielinski, Metropolitan area video-on-demand service using pyramid broadcasting, Multimedia Systems, v.4 n.4, p.197-208, Aug. 1996 [doi>10.1007/s005300050023 ]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms

Keywords:
approximation algorithms, experimental algorithms, parallel machines, periodic scheduling, window scheduling