NeFut Logo NeFut
中 Admin Login

[CS.DS] Online Bin Packing with Dispatch Deadlines

Published at: 2026-11-09 22:00 Last updated: 2026-11-12 00:51
#algorithm #optimization #Data Structure

We study a generalization of online bin packing that incorporates dispatch deadlines. Items arrive over time; each item reveals its arrival time, size (in $(0,1]$), and deadline only upon arrival. The algorithm must immediately and irrevocably place the item into a unit‑capacity bin that has not yet been dispatched. Every bin must be dispatched no later than the earliest deadline among its assigned items, and once dispatched it cannot be used again. The objective is to minimize the number of bins used. This setting naturally arises in logistics, and the offline version has appeared as the clique partition problem in weighted interval graphs or the BinSchedule problem. It is also a special case of online bin packing with conflicts and is closely related to models with delay costs. We examine the competitive ratios of several classic online bin packing algorithms and find that the hierarchy of ratios largely persists. The main technical contributions are that First‑Fit achieves a competitive ratio exactly $\frac{16}{7}\approx2.28571$, while any deterministic online algorithm has a lower bound of $\frac{11}{5}=2.2$, indicating First‑Fit is near optimal. Next‑Fit and Worst‑Fit both have ratio $3$, and every Any‑Fit algorithm lies between $\frac{16}{7}$ and $3$.\n\nReview: The paper provides a thorough analysis of online bin packing with deadlines, establishing tight bounds that are valuable for both theory and practical scheduling applications.

Original Source: https://arxiv.org/abs/2611.08792

[h] Back to Home