## 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.