##
Necessary and sufficient conditions for stability of a bin-packing system

###
C. Courcoubetis and R.R. Weber,
*J. Appl. Prob.* **23** 989-999, 1986.

Abstract

Objects of various integer sizes, $o_1,\ldots,o_n$, are to be packed together
into bins of size $N$ as they arrive at a service facility. The number of
objects of size $o_i$ which arrive by time $t$ is $A_i^t$, where the components
of $A^t=(A_1^t,\ldots,A_n^t)$ are independent renewal processes, with
$A^t/t\rightarrow\lambda$ as $t\rightarrow\infty$. The empty space in those
bins that are neither full nor empty at time $t$ is called the $\emph{wasted
space} and the system is declared \emph{stabilizable} if for some finite $B$
there exists a bin-packing algorithm whose use guarantees the expected waste is
less than $B$ for all $t$. We show that the system is stabilizable if the
arrival processes are Poisson and $\lambda$ lies in the interior of a certain
convex polyhedral cone $\Lambda$. In this case there exists a bin packing
algorithm which stabilizes the system without needing to know $\lambda$.
However, if $\lambda$ lies on the boundary pf $\Lambda$ the wasted space grows
as $O(\sqrt{t})$ and if $\lambda$ is exterior to $\Lambda$ it grows as $O(t)$;
these conclusions hold even if objects are repacked as often as desired.

**back to list of papers**