In an important new study, HKUST’s Guodong Lyu and colleagues show how to optimize resource allocation under stochastic demand. Improving on previous frameworks, they demonstrate that the analysis of three different classes of allocation policy can be unified from the customer perspective, through the concept of the service level. This gives rise to a flexible framework for solving allocation problems in real-world managerial situations.

The researchers analyzed the general problem of a “planner” who designs an allocation policy to supply products to customers. Demand information can be revealed in three ways: at the start of allocation, as on a ride-sharing platform; after the decision to serve a customer, as in aid provision, where the situation can only be appraised by visiting the relief area; or after allocation, which is common in supply-chain management. In the last case, say the authors, “the realized demand information is not used in the construction of the allocation priorities,” but this is still an allocation problem.

The planner can optimize either revenue or customer satisfaction. More specifically, the aim can be to maximize the total revenue of customers served using a fixed amount of capacity, or to minimize the capacity required to satisfy the service target given a fixed expected revenue. “All the problems above,” say the authors, “are variants of the stochastic knapsack problem.” That is, by analogy with packing items into a knapsack one by one, customers in stochastic knapsack allocation problems are served in a sequential manner, and “packing” must be optimized.

The study provides key insights into solving such problems. When both demand and revenue are random, the probability of successfully serving a customer—known as persistency—provides a powerful and general conceptual framework. The stochastic knapsack problem is also related to the capacity pooling problem, a well-studied scenario in operational research. The two problems frequently co-occur in real-life situations, such as TV advertisement scheduling during live sports (with breaks of unknown number and duration) and obsolete inventory management.

Returning to the three ways of revealing demand information, these also correspond to three types of allocation policy. The “responsive” policy is adopted when demand is known at the start of allocation. The “anticipative” and “adaptive” policies apply when the demand information becomes known at successively later stages. Lyu and colleagues found that their persistency-inspired model could improve performance relative to the benchmark “greedy” algorithm for the anticipative and adaptive cases.

“When the capacity is limited,” the researchers note, “only a few customers can be successfully served. In this case, our adaptive and anticipative policies perform well in selecting the ‘right’ customers to serve.” Given the ubiquity of stochastic knapsack problems in business research, the authors’ development of a unified framework that gives rise to easily solvable models will be invaluable to management practitioners.

“The techniques developed, and the persistency values obtained from the optimal responsive policy,” conclude the authors, “can be used to design good adaptive and anticipative policies for the two variants of stochastic knapsack problems.” Allocation decision-makers with known service-level targets can leverage this research to appraise the “achievable regions” of service for a given capacity level and hence design optimal strategies.