A bin-packing system for objects with sizes from a finite set: Necessary and sufficient conditions for stability and some applications

Publisher Website
Google Scholar
Abstract
Objects of various integer sizes, o1 .... on, on, are to be packed together into bins of size N as they arrive at a service facility. The number of objects of size oi which arrive by time t is Ai t, where the components of At = (A1 t, ....., An t) are independent renewal processes, with At/t → λ at t → ∞. The empty space in those bins which are neither empty nor full at time t is called the wasted space and the system is declared stabilizable if for some finite B there exists a bin-packing algorithm whose use guarantees the expected wasted space is less than B for all t. We show that the system is stabilizable if the arrival processes are Poisson and λ lies in the interior of a certain convex polyhedral cone Λ. In this case there exists a bin-packing algorithm which stabilizes the system without needing to know λ. However, if λ lies on the boundary of Λ the wasted space grows as O(√t) and if √ is exterior to Λ it grows as O(t); these conclusions hold even if objects may be repacked as often as desired. We give two interesting applications of the above results. In the first we consider the case in which the bins are of size N1, N2 ..... NK. In the second we allow the size of the arriving objects to be drawn from an arbitrary continuous distribution.

This publication has 0 references indexed in Scilit: