Windows scheduling as a restricted version of Bin Packing

ABSTRACT

Given is a sequence of n positive integers w1;w2....,wn that are associated with the items 1, 2....n respectively. In the windows scheduling problem, the goal is to schedule all the items (equal length information pages) on broadcasting channels such that the gap between two consecutive appearances of page i on any of the channels is at most wi slots (a slot is the transmission time of one page). In the unit fractions bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item i is 1/wi. The optimization objective is to minimize the number of channels or bins. In the off-line setting the sequence is known in advance whereas in the on-line setting the items arrive in order and assignment decisions are irrevocable. Since a page requires at least 1=wi of the channel's bandwidth, it follows that windows scheduling without migration (all broadcasts of a page must be from the same channel) is a restricted version of unit fractions bin packing.Let H = [Σⁿi = 1 (1/wi)] be the obvious bandwidth lower bound on the required number of bins (channels). Previously an H + O(ln H) off-line algorithm for the windows scheduling problem was known. This paper presents an H + 1 off-line algorithm to the unit fractions bin packing problem. In the on-line setting, this paper presents an H + O(√H) algorithm to both problems where the one for the unit fractions bin packing problem is simpler. On the other hand, this paper shows that already for the unit fractions bin packing problem, any on-line algorithm must use at least H + Ω (ln H) bins.

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: M. 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, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.433-442, January 06-08, 2002, San Francisco, California
• 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 , 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]
• 7: E. G. Coffman, Jr. , C. Courcoubetis , M. R. Garey , D. S. Johnson , P. W. Shor , R. R. Weber , M. Yannakakis, Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings, SIAM Journal on Discrete Mathematics, v.13 n.3, p.384-402, May—June 2000 [doi>10.1137/S0895480197325936]
• 8: E. G. Coffman, Jr. , M. R. Garey , D. S. Johnson, Bin packing with divisible item sizes, Journal of Complexity, v.3 n.4, p.406-428, December 1, 1987 [doi>10.1016/0885-064X(87)90009-4]
• 9: 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
• 10: 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
• 11: 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
• 12: V. Gondhalekar, R. Jain, and J. Werth. Scheduling on airdisks: effcient access to personalized information services via periodic wireless data broadcast. IEEE International Conference on Communications (ICC), 3:1276--1280, 1997.
• 13: 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 [doi>10.1023/A:1009610701409]
• 14: D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithm. SIAM J. of Comput., 3:256--278, 1974.
• 15: L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Transactions on Broadcasting, 43(3):268--271, 1997.
• 16: Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, v.37 n.1, p.27-35, Jan. 10, 1991 [doi>10.1016/0020-0190(91)90246-E]
• 17: 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]
• 18: Steven S. Seiden, On the online bin packing problem, Journal of the ACM (JACM), v.49 n.5, p.640-671, September 2002 [doi>10.1145/585265.585269]
• 19: R. Tijdeman. The chairman assignment problem. Discrete Mathematics, 32:323--330, 1980.
• 20: André van Vliet, On the asymptotic worst case behavior of harmonic fit, Journal of Algorithms, v.20 n.1, p.113-136, Jan. 1996 [doi>10.1006/jagm.1996.0005]
• 21: W. F. Vega and G. S. Leuker. Bin packing can be solved within 1 + ε in linear time. Combinatorica, 1:349--355, 1981.
• 22: 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]