Windows scheduling as a restricted version of bin packing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Windows scheduling as a restricted version of bin packing

Full text

Pdf (232 KB)

Source

ACM Transactions on Algorithms (TALG) archive
Volume 3 , Issue 3 (August 2007) table of contents

Article No. 28

Year of Publication: 2007

ISSN:1549-6325

Authors

Amotz Bar-Noy	Brooklyn College, Brooklyn, NY
Richard E. Ladner	University of Washington, Seattle, WA
Tami Tamir	The Interdisciplinary Center, Herzliya, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 162, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1273340.1273344 What is a DOI?

ABSTRACT

Given is a sequence of n positive integers w₁,w₂,…,w_n 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 w_i 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/w_i. The optimization objective is to minimize the number of channels or bins. In the offline setting, the sequence is known in advance, whereas in the online setting, the items arrive in order and assignment decisions are irrevocable. Since a page requires at least 1/w_i of a channel's bandwidth, it follows that windows scheduling without migration (i.e., all broadcasts of a page must be from the same channel) is a restricted version of unit-fractions bin packing.

Let H = ⌈&sum_i=1ⁿ(1/w_i) be the bandwidth lower bound on the required number of bins (channels). The best-known offline algorithm for the windows scheduling problem used H + O(ln H) channels. This article presents an offline algorithm for the unit-fractions bin packing problem with at most H + 1 bins. In the online setting, this article presents algorithms for both problems with H + O(&sqrt;H) channels or bins, where the one for the unit-fractions bin packing problem is simpler. On the other hand, this article shows that already for the unit-fractions bin packing problem, any online algorithm must use at least H+&Omega(ln H) bins. For instances in which the window sizes form a divisible sequence, an optimal online algorithm is presented. Finally, this article includes a new NP-hardness proof for the windows scheduling problem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Acharya, S., Franklin, M. J., and Zdonik, S. 1995. Dissemination-Based data delivery using broadcast disks. IEEE Personal Commun. 2, 6, 50--60.
	2	Ammar, M. H., and Wong, J. W. 1985. The design of teletext broadcast cycles. Perform. Eval. 5, 4, 235--242.
	3	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]
	4	Amotz Bar-Noy , Joseph (Seffi) 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]
	5	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]
	6	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
	7	Mee Yee Chan , Francis Y. L. Chin, General Schedulers for the Pinwheel Problem Based on Double-Integer Reduction, IEEE Transactions on Computers, v.41 n.6, p.755-768, June 1992 [doi>10.1109/12.144627 ]
	8	Chan, W. T., and Wong, P. W. H. 2004. On-Line windows scheduling of temporary items. In Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC). 259--270.
	9	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]
	10	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
	11	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]
	12	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
	13	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
	14	Gondhalekar, V., Jain, R., and Werth, J. 1997. Scheduling on airdisks: Efficient access to personalized information services via periodic wireless data broadcast. In Proceedings of the IEEE International Conference on Communications (ICC), vol. 3. 1276--1280.
	15	Holte, R., Mok, A., Rosier, L., Tulchinsky, I., and Varvel, D. 1989. The pinwheel: A real-time scheduling problem. In Proceedings of the 22nd Hawaii International Conference on System Science. 693--702.
	16	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
	17	Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., and Graham, R. L. 1974. Worst-Case performance bounds for simple one-dimensional packing algorithm. SIAM J. Comput. 3, 4, 299--325.
	18	Juhn, L., and Tseng, L. 1997. Harmonic broadcasting for video-on-demand service. IEEE Trans. Broadcast. 43, 3, 268--271.
	19	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 ]
	20	C. C. Lee , D. T. Lee, A simple on-line bin-packing algorithm, Journal of the ACM (JACM), v.32 n.3, p.562-572, July 1985 [doi>10.1145/3828.3833]
	21	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]
	22	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]
	23	Tijdeman, R. 1980. The chairman assignment problem. Discrete Math. 32, 3, 323--330.
	24	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 ]
	25	Vega, W. F., and Leuker, G. S. 1981. Bin packing can be solved within 1 + in linear time. Combinatorica 1, 4, 349--355.
	26	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 ]
	27	Wong, P. W. H., Chan, W. T., and Lam, T. W. 2005. Dynamic bin packing of unit-fractions items. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP).