Stochastic Knapsack Revisited: The Service Level Perspective

Guodong Lyu (), Mabel C. Chou (), Chung-Piaw Teo (), Zhichao Zheng () and Yuanguang Zhong ()
Additional contact information
Guodong Lyu: Institute of Operations Research and Analytics, National University of Singapore, Singapore, Singapore 117602; Department of Analytics & Operations, NUS Business School, National University of Singapore, Singapore, Singapore 119245
Mabel C. Chou: Institute of Operations Research and Analytics, National University of Singapore, Singapore, Singapore 117602; Department of Analytics & Operations, NUS Business School, National University of Singapore, Singapore, Singapore 119245
Chung-Piaw Teo: Institute of Operations Research and Analytics, National University of Singapore, Singapore, Singapore 117602; Department of Analytics & Operations, NUS Business School, National University of Singapore, Singapore, Singapore 119245
Zhichao Zheng: Lee Kong Chian School of Business, Singapore Management University, Singapore, Singapore 178899
Yuanguang Zhong: School of Business Administration, South China University of Technology, Guangzhou, Guangdong 510640, China

Operations Research, 2022, vol. 70, issue 2, 729-747

Abstract: 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.

Keywords: Operations and Supply Chains; stochastic knapsack; resource allocation; capacity pooling; service level; persistency value (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2173 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:2:p:729-747

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().