Bin packing with queues

We study the best achievable performance (in terms of average queue size and delay) in a stochastic and dynamic version of the bin-packing problem. Items arrive to a queue according to a Poisson process with rate 2ρ, where ρ ∈ (0, 1). The item sizes are i.i.d., uniformly distributed in [0, 1]. At each time unit, a single unit-size bin is available and can receive any of the queued items, as long as their total size does not exceed one. Coffman & Stolyar (1999) and Gamarnik (2001) have established that there exist packing policies under which the average queue size is finite, for every ρ ∈ (0, 1). In this paper, we study the precise scaling of the average queue size, as a function of ρ, with emphasis on the critical regime where ρ approaches one. Standard results on the probabilistic (but static) bin-packing problem can be readily applied to produce policies under which the queue size scales as O(h 2 ), where h = 1/(1 − ρ), which raises the question whether this is the best possible. We establish that the average queue-size scales as Ω(h log h), under any policy. Furthermore, we provide an easily implementable policy, which packs at most two items per bin. Under that policy, the average queue size scales as O(h log3/2 h), which is nearly optimal. On the other hand, if we impose the additional requirement that any two items packed together must have near-complementary sizes (in a sense to be made precise), we show that the average queue size must scale as Θ(h 2 ).