Dynamic Allocation of Reusable Resources: Logarithmic Regret in Overloaded Networks

• 成果类型: Article
• 署名作者: Xie, Xinchang; Gurvich, Itai; Kucukyavuz, Simge
• 署名单位: Northwestern University; Northwestern University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0429
• 发表日期: 2025
• 页码: 2097-2124
• 关键词: revenue management; loss systems; policies; optimization; reservation; bottlenecks

摘要

We study the problem of dynamically allocating reusable resources to customers of n types. There are d pools of resources and a finite number of units from each resource. If a customer request is accepted, the decision maker collects a type-dependent reward, and the customer occupies, for a random service time, one unit from each resource in a set of these. Upon service completion, these resource units become available for future allocation. This is a loss network: requests that are not accepted leave immediately. The decision maker's objective is to maximize the long-run average reward subject to the resource capacity constraint. A natural linear programming (LP) relaxation of the problem serves as an upper bound on the performance of any policy. We identify a condition that generalizes the notion of overload in single-resource networks (i.e., when d(-1)). The LP guides our construction of a threshold policy. In this policy, the number of thresholds equals the number of resource types (hence, does not depend on the number of customer types). These thresholds are applied to a corrected headcount process. In the case of a single resource, the corrected head count is the number of resource units that are occupied. We prove that, in overloaded networks, the additive loss (or regret) of this policy benchmarked against the LP upper bound is logarithmic in the total arrival volume in the high-customer-volume, manyresource-units, asymptotic regime. No policy can achieve sublogarithmic regret. Simulations showcase the performance of the proposed policy.