Stability of on-line bin packing with random arrivals and long-run average constraints

C. Courcoubetis and R.R. Weber. Probability in the Engineering and Informational Sciences, 4, 447-460, 1990.


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
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 prescribed 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 the goal to
be realized and describe an algorithm to achieve it.

back to list of papers