Dynamic batching of online arrivals to leverage economies of scale

Akhil Bhimaraju, S. Rasoul Etesami, Lav R. Varshney

Introduction

In modern distributed systems, requests often arrive asynchronously and unpredictably. Whether it is a ride-hailing platform matching passengers, an ad-server grouping video requests, or an IoT gateway aggregating sensor data, system designers face a fundamental tension: immediate processing incurs high overhead, while delayed processing to form larger batches increases latency. This paper presents a principled framework for dynamic batching, optimizing the balance between the cost of delay and the "economies of scale" inherent in bulk processing.

Problem Formulation

The core challenge of dynamic batching lies in the online nature of arrivals. A system cannot know when the next request will appear. Traditional strategies—such as waiting for a fixed number of requests or a fixed duration—often fail under variable arrival rates. If a system waits for a fixed size of 10, the 10th request might not arrive for hours; if it waits for a fixed time, it might process inefficiently small batches during low-traffic periods.

The authors model the processing cost using a submodular set function. This mathematical choice captures the diminishing marginal cost of adding requests to a batch: as a batch grows, the incremental cost of adding one more request decreases. The objective is to minimize the total cost, defined as the sum of all processing costs and the cumulative waiting time of all requests.

Methodology

The Offline Optimal (OSP)

To establish a benchmark, the authors first solve the offline version of the problem where all arrival times are known in advance. They demonstrate that the Optimal Scheduling Problem (OSP) can be reduced to finding the shortest path in a weighted Directed Acyclic Graph (DAG). In this graph, nodes represent individual arrivals, and edges represent the cost of batching a specific sequence of arrivals. This reduction allows for an exact solution in $O(n^2)$ time, providing a baseline for evaluating online strategies.

The Online Algorithm: WaitTillAlpha (WTA)

For real-world scenarios where the future is unknown, the authors introduce WaitTillAlpha (WTA). This algorithm is simple yet robust: it tracks the total waiting time accumulated by all requests currently in the queue. Once this "waiting pain" reaches a specific threshold—defined as a multiple ($\alpha$) of the cost to process the current batch—the system triggers processing. This approach essentially treats waiting time as a budget used to "buy" more efficient processing costs.

Theoretical Analysis

Using a potential function argument, the researchers prove that WTA is 3-competitive against an omniscient adversary for a wide range of submodular cost functions when $\alpha = 1/2$. This means that regardless of the arrival pattern, the online algorithm's total cost is guaranteed to be no more than three times the cost of the optimal offline schedule. The performance is further influenced by the "curvature" ($\Gamma$) of the cost function, which measures the strength of the economies of scale. The authors established a lower bound of $1/\Gamma$ for the competitive ratio.

Empirical Evaluation

The framework was tested using both synthetic simulations (Poisson processes) and real-world data. The real-world dataset comprised customer arrival patterns at three different banks over a four-week period, capturing the natural "burstiness" of human activity.

Key findings include:

  • Practical Efficiency: While the theoretical upper bound is 3, WTA typically performed within 1.3x of the offline optimum on real-world data, suggesting the worst-case scenarios are rare in practice.
  • Robustness: The algorithm maintained high performance even during inhomogeneous arrival rates (e.g., peak hours vs. quiet periods), proving it does not rely on steady-state assumptions or prior knowledge of arrival distributions.

Conclusion and Future Directions

WaitTillAlpha provides a generalized, provably efficient solution for dynamic batching across various domains, from cloud computing to logistics. However, some avenues remain for future exploration. The current model treats waiting as a linear cost rather than a hard deadline; extending the framework to accommodate strict latency constraints would benefit real-time communication systems. Additionally, while the current study focuses on batch size, future work could explore multi-dimensional features where processing costs depend on the specific attributes of the requests within a batch.

Summary updated

Abstract

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.
BibTeX
@article{bhimaraju2023dynamic,
  author = {Akhil Bhimaraju and S. Rasoul Etesami and Lav R. Varshney},
  title = {{Dynamic batching of online arrivals to leverage economies of scale}},
  journal = {Eur. J. Oper. Res.},
  year = {2023},
}
Figure