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