Paper Robust Dynamic Staffing with Predictions
This study examines a dynamic staffing problem in which a decision-maker must sequentially hire workers over a finite planning horizon to meet a demand level that is unknown until the end of the period. Demand forecasts arrive progressively and grow more accurate over time, but worker availability simultaneously declines as the operating day approaches. This creates a fundamental tension between hiring early, when workers are plentiful but forecasts are unreliable, and hiring late, when forecasts are sharp but availability is limited. The problem is motivated by last-mile delivery operations, where platforms rely on gig-economy workers whose availability diminishes closer to the day of service. To avoid dependence on distributional assumptions and remain agnostic to the underlying forecasting method, the problem is studied under an adversarial predictions framework. Sequential forecasts take the form of uncertainty intervals that approximately contain true demand, chosen adversarially. The objective is to minimize worst-case staffing imbalance costs across all adversarial sequences. The main theoretical contribution is a simple, computationally efficient online algorithm that is proven minimax optimal. The minimax cost against a restricted adversary is characterized via a polynomial-size linear program, and the solution is shown to extend to the general adversarial setting. The framework is further extended to handle multiple simultaneous demands, costly reversals of hiring decisions, and inconsistent prediction intervals. A practical re-solving variant of the algorithm is also introduced and shown to retain minimax optimality. Numerical experiments conducted in collaboration with Amazon Last-Mile demonstrate that the proposed algorithms outperform Bayesian heuristics in both cost and computational speed.
- Authored by
- 2025
- CAAI - Operations