Journal
OPERATIONS RESEARCH
Volume 70, Issue 2, Pages 729-747Publisher
INFORMS
DOI: 10.1287/opre.2021.2173
Keywords
stochastic knapsack; resource allocation; capacity pooling; service level; persistency value
Funding
- Ministry of Education, Singapore [MOE-2019-T3-1-010]
- National Natural Science Foundation of China [71871097, 71731006, 71520107001]
- Major Program of the National Natural Science Foundation of China [71690233]
- Singapore Ministry of Education Social Science Research [MOE2016-SSRTG-059]
- Guangdong Natural Science Foundation [2020A1515011270]
Ask authors/readers for more resources
This paper studies three classes of allocation policies and unifies the analysis of these policies through the concept of persistency values. It is found that the performance gaps between optimal anticipative policies and adaptive policies are bounded in certain models, while the gaps between optimal adaptive policies and responsive policies can be arbitrarily large. The techniques and persistency values obtained from optimal responsive policies can be used to design good adaptive and anticipative policies for other resource allocation problems, providing a unified approach to algorithm design and analysis for these problems.
A key challenge in the resource allocation problem is to find near-optimal policies to serve different customers with random demands/revenues, using a fixed pool of capacity (properly configured). In this paper, we study the properties of three classes of allocation policies-responsive (with perfect hindsight), adaptive (with information updates), and anticipative (with forecast information) policies. These policies differ in how the information on actual demand and revenue of each customer is being revealed and integrated into the allocation decisions. We show that the analysis of these policies can be unified through the notion of persistency (or service level) values-the probability that a customer is being (completely) served in the optimal responsive policy. We analyze and compare the performances of these policies for both capacity minimization (with given persistency targets) and revenue maximization (with given capacity) models. In both models, the performance gaps between optimal anticipative policies and adaptive policies are shown to be bounded when the demand and revenue of each item are independently generated. In contrast, the gaps between the optimal adaptive policies and responsive policies can be arbitrarily large. More importantly, we show that the techniques developed, and the persistency values obtained from the optimal responsive policies can be used to design good adaptive and anticipative policies for the other two variants of resource allocation problems. This provides a unified approach to the design and analysis of algorithms for these problems.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available