Papers for

warehousing operations teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Online method for grouping requests with capacity and delay limits

Capacitated Line Aggregation with Maximum Delay

Abstract: We study capacitated line aggregation with per-batch maximum delay. Requests arrive over time at locations on a rooted half-line and are served in instantaneous batches of at most $k$ requests. Each batch pays the distance to its farthest request plus the waiting time of its oldest request. The objective is to minimize the total cost. We give a deterministic online algorithm with competitive ratio $36+12\sqrt3$. The algorithm uses a Next Fit idea along paths of nested time intervals: it assigns a new group to an existing batch when a path-load test permits, and opens a new batch otherwise. The path load controls both capacity and the cost of opening new batches. Randomizing the common scale improves the expected competitive ratio to $(18+6\sqrt3)/\ln2$ against an oblivious adversary. Both guarantees extend to arbitrary indivisible request sizes. We also study capacitated LAD in the learning-augmented model. Advice revealed at its service times allows $(1+ε)$-consistency against every complete feasible advice schedule and $O(ε^{-2})$-robustness. The analysis charges repeated switches to successive decreases in the remaining advice cost.

Mon 19 OctData Structures and Algorithms
The gist
Imagine you have a line of people who need to be served in groups, but each group can only hold a certain number of people, and you want to keep waiting times short. The paper studies how to group these requests arriving one by one in a way that balances travel distance and waiting time. The authors present an online method that decides when to add a new request to an existing group or start a new one, achieving a good balance between efficiency and delay. They also explore how extra information or advice about requests can improve this process even more.
Open → 2610.26497v1