Dynamic batching of online arrivals to leverage economies of scale
研究在在线到达场景下如何动态分批处理订单，以平衡等待成本和处理成本，提出多项式时间的最优离线算法和具有常数竞争比的在线算法，适用于网约车匹配、视频广告等场景。
Many settings, such as matching riders to drivers in ride-hailing platforms or in-stream video advertising, require handling arrivals over time. In such applications, it is often beneficial to group the arriving orders or requests into batches and process the larger batches rather than individual arrivals. However, waiting too long to create larger batches incurs a waiting cost for past arrivals. On the other hand, processing the arrivals too soon leads to higher processing costs by missing the economies of scale of grouping larger numbers of arrivals into larger batches. Moreover, the timing of the next arrival is often unknown, meaning fixed-size batches or fixed waiting times tend to be poor choices. In this work, we consider the problem of finding the optimal batching schedule to minimize the sum of waiting time and processing cost under both offline and online settings. In the offline problem in which all arrival times are known a priori, we show that the optimal batching schedule can be found in polynomial time by reducing it to a shortest path problem on a weighted acyclic graph. For the online problem with unknown arrival times, we develop algorithms that are provably competitive for a broad range of processing-cost functions. We also provide a lower bound on the competitive ratio that no online algorithm can beat. Finally, we run numerical experiments on simulated and real data to demonstrate the effectiveness of our algorithms against the offline benchmark. • Tradeoff waiting to accumulate more requests vs efficiency due to larger batches. • Online algorithm with a constant-factor competitive ratio guarantee. • Lower bound that no online algorithm can beat. • Arbitrary submodular processing cost makes it applicable to very general scenarios.