Stochastic Knapsack Revisited: The Service Level Perspective

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). Three classes of allocation policies, responsive (with perfect hindsight), adaptive (with information updates), and anticipative (with forecast information) policies, are widely used in practice. We analyze and compare the performances of these policies for both capacity minimization and revenue maximization 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.