Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-28T17:33:44.629Z Has data issue: false hasContentIssue false
  • English
  • Français

Stability of On-Line Bin Packing with Random Arrivals and Long-Run-Average Constraints

Published online by Cambridge University Press:  27 July 2009

Coastas Courcobetis  and
Richard Weber
Coastas Courcobetis
Affiliation:
AT&T Bell Laboratories Murray Hill, NJ 07974
Richard Weber
Affiliation:
Engineering DepartmentCambridge University, Cambridge CB3 9ET, England
Get access Rights & Permissions [Opens in a new window]

Abstract

Items of various types arrive at a bin-packing facility according to random processes and are to be combined with other readily available items of different types and packed into bins using one of a number of possible packings. One might think of a manufacturing context in which randomly arriving subassemblies are to be combined with subassemblies from an existing inventory to assemble a variety of finished products. Packing must be done on-line; that is, as each item arrives, it must be allocated to a bin whose configuration of packing is fixed. Moreover, it is required that the packing be managed in such a way that the readily available items are consumed at predescribed rates, corresponding perhaps to optimal rates for manufacturing these items. At any moment, some number of bins will be partially full. In practice, it is important that the packing be managed so that the expected number of partially full bins remains uniformly bounded in time. We present a necessary and sufficient condition for this goal to be realized and describe an algorithm to achieve it.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 4 , Issue 4 , October 1990 , pp. 447 - 460
Copyright
Copyright © Cambridge University Press 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Coffman, E.G. JrLueker, G. S. & Rinnooy, Kan A.H. (1988). Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics. Management Science 34(3): 266–290.CrossRefGoogle Scholar
Courcoubetis, C. & Weber, R.R. (1986). Necessary and sufficient conditions for stability of a bin-packing system. Journal of Applied Probability, 23: 989–999.CrossRefGoogle Scholar
Courcoubetis, C. & Weber, R.R. (1986). A bin-packing system for objects from a finite set: necessary and sufficient conditions for stability and some applications. Proceedings of 25th IEEE Conference on Decision and Control, Athens, Greece.CrossRefGoogle Scholar
Courcoubetis, C., Konstantopoulos, P., Walrand, J., & Weber, R.R. (1989). Stabilizing an uncertain production system. Queueing Systems: Theory and Applications 5(1–3): 37–54.CrossRefGoogle Scholar
Courcoubetis, C. & Rothblum, U.G. (1990). On optimal packing of randomly arriving objects. Mathematical Operations Research (to appear).Google Scholar
Eaves, B.C. & Rothblum, U.G. (1988). A discrete time average cost flexible manufacturing and operator scheduling model solved by deconvexification over time. Operations Research 36: 242–257.CrossRefGoogle Scholar
Hajek, B. (1982). Hitting-time and occupation-time bounds implied by drift analysis with applications. Advanced Applied Probability 14: 502–525.CrossRefGoogle Scholar
Lueker, G.S. (1983). Bin-packing with items uniformly distributed over intervals [a, b]. Proceedings of 24th Symposium on Foundation of Computer Science. New York: IEEE Computer Society Press, pp. 289–297.Google Scholar
Rhee, W.T. & Talagrand, M. (1988). Some distributions that allow perfect packing. Journal of the Association for Computing Machinery 35(3): 564–578.CrossRefGoogle Scholar