Bin Packing with Queues

Devavrat Shah, John N. TsitsiklisJournal of Applied Probability 2008 · DOI

This paper, published in the Journal of Applied Probability, explores the fundamental limits of a dynamic and stochastic version of the classic bin-packing problem. While traditional bin packing focuses on fitting a static set of items into the fewest bins possible, this work investigates how a system behaves when items arrive over time and can be queued. The authors establish a near-optimal bound for average queue size and delay in the "heavy traffic" regime—where the system is pushed to its capacity limit.

TL;DR

The authors prove that by allowing items to wait in a queue, dynamic bin packing can achieve an average queue size that scales nearly linearly—specifically $O(h \log^{3/2} h)$—with the system's congestion factor $h$. This significantly outperforms simpler "batching" strategies and establishes a fundamental lower bound of $\Omega(h \log h)$ for any possible packing policy.

What Problem Does This Paper Address?

In many real-world systems—like network bandwidth allocation or logistics—items (packets or cargo) arrive stochastically and must be packed into fixed-capacity containers (time slots or trucks).

The authors identify a gap between two well-known models:

  1. Online Bin Packing: Items must be packed immediately upon arrival. This usually results in significant wasted space because you can't wait for a "perfect match" to arrive later.
  2. Queueing Theory (M/U/1): If items could be broken into pieces (fluid-like), the average queue size would scale linearly as $h = 1/(1-\rho)$, where $\rho$ is the load.

The "Bin Packing with Queues" model sits in the middle. Items cannot be broken, but they can wait in a queue. The central question is: What is the cost of "discreteness"? How much larger does the queue need to be because we have to pack whole items compared to a system where items are infinitely divisible?

Methods

The authors employ a mix of probabilistic analysis and combinatorial discrepancy theory:

  • Lower Bound Analysis: They relate the bin-packing process to a two-dimensional matching problem. By treating item arrivals and bin availability as points in a time-size coordinate system, they use results from "grid matching" (specifically the work of Ajtai, Komlós, and Tusnády) to prove that no policy can escape a logarithmic penalty.
  • The Proposed Policy: They introduce a randomized policy that simplifies the problem by splitting bins into "small" (size $\le 1/2$) and "large" (size $> 1/2$) slots. The policy essentially tries to pair a large item with a small item that "fits" the remaining space.
  • Discrepancy Theory: To analyze the performance of their policy, they use discrepancy bounds to show how the "randomness" of item sizes accumulates over time and how their policy effectively "cancels out" these fluctuations to keep the queue small.

Datasets

This is a theoretical paper and does not use empirical datasets. Instead, it evaluates the problem under a standard stochastic model:

  • Arrivals: Poisson process with rate $2\rho$.
  • Item Sizes: Independent and identically distributed (i.i.d.) with a uniform distribution on $[0, 1]$.
  • Bins: One unit-capacity bin becomes available at every integer time step.

Key Insights and Ideas

  • Queueing as Flexibility: The "aha moment" is that queueing isn't just a side effect of congestion; it's a tool. By allowing a small delay, the controller can wait for items that are near-perfect complements (e.g., a 0.3 and a 0.7), which drastically reduces waste compared to online packing.
  • The Logarithmic Penalty: The authors show that the "cost of discreteness" is polylogarithmic. While a fluid system scales as $h$, the bin-packing constraint adds a $\log h$ factor.
  • The Danger of "Restricted" Pairing: They demonstrate that if you are too rigid—for example, only allowing an item of size $x$ to be packed with an item of size exactly $1-x$ (within some small epsilon)—the performance collapses. Such "restricted-pair" policies force the queue to grow as $O(h^2)$, which is much worse than their proposed near-optimal policy.

Key Results

  • Universal Lower Bound: For any policy, the average queue size must be at least $\Omega(h \log h)$.
  • Upper Bound: The authors' proposed policy achieves an average queue size of $O(h \log^{3/2} h)$. This is "nearly optimal" as it is only a factor of $\sqrt{\log h}$ away from the lower bound.
  • Comparison to Batching: Standard batching policies (waiting for a group of items and then packing them) typically result in $O(h^2)$ scaling. This paper shows we can do much better.

Limitations and Future Work

  • Uniform Distribution Assumption: The results rely heavily on item sizes being uniformly distributed on $[0, 1]$. While the authors suggest the logic should hold for any distribution symmetric around $1/2$, non-symmetric distributions remain an open challenge.
  • Closing the Gap: There is still a small gap between the $\log h$ lower bound and the $\log^{3/2} h$ upper bound. Closing this gap would require even more sophisticated matching analysis.
  • Randomization: The primary policy presented is randomized. While the authors mention it can be made deterministic, the randomized version is more elegant for theoretical proof but might be less desirable in certain hardware implementations.

Summary updated

Abstract

We study the best achievable performance (in terms of the 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 independent and identically distributed (i.i.d.) with a uniform distribution 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 1. Coffman and Stolyar (1999) and Gamarnik (2004) 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 1. 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 of 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 log 3/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 ).
BibTeX
@article{shah2008bin,
  author = {Devavrat Shah and John N. Tsitsiklis},
  title = {{Bin Packing with Queues}},
  journal = {Journal of Applied Probability},
  year = {2008},
  doi = {10.1017/s0021900200004885},
}
Figure