Analysis of Stochastic Online Bin Packing Processes

A stochastic online version of the classical bin packing problem, where a bin corresponds to the capacity of a resource allocated among streams of requests at discrete time units, is a fundamental problem that arises in a wide variety of application areas including bandwidth allocation in networks, memory management in computers, and message transmission in slotted network channels. We derive a mathematical analysis of the corresponding multi-dimensional stochastic process, potentially infinite in each dimension, under the Best Fit scheduling policy based on a combination of a Lyapunov function technique and matrix-analytic methods, although our results can also support other scheduling policies. Our analysis yields stability conditions and stationary distributions for this stochastic bin packing process under general model parameter distributions. We further provide some numerical methods for the computation of these measures.