Value of Sparse Structures in Dynamic Reusable Resource Allocation with Waiting

We study the dynamic resource allocation problem in online service platforms featuring reusable resources, waiting space, and heterogeneous demands and resources. The service provider aims to balance the trade-off between maximizing revenue and minimizing waiting times across various demand types. For this problem, we propose a comprehensive framework to minimize the long-run average revenue loss and waiting cost by simultaneously designing the 1) flexibility structure, 2) admission control, and 3) scheduling policy. The flexibility structures are tailored to systems with varying levels of workload intensity, and the number of arcs in the network is linear in the number of resource and demand types. In these sparse networks, we show that simple static priority rules and threshold-based admission controls are asymptotically optimal in the many-server regimes. Furthermore, our proposed algorithm for designing system flexibility, along with the scheduling and admission control policies, is both easy to interpret and straightforward to implement. Numerical experiments demonstrate the effectiveness of our approach, particularly for smaller systems, in non-asymptotic environments.

(This is joint work with Shixin Wang (CUHK) and Jing Dong (Columbia).)