Heterogeneous Multi-resource Planning and Allocation Under Stochastic Demand.

This article focuses on the stochastic heterogeneous multiresource planning and allocation problem (smRmD), which involves deciding the quantity and allocation of multiple resource types to meet uncertain demands that require subsets of these resources simultaneously at specific times and locations. The authors formulate smRmD as a two-stage stochastic integer program with two objective variants: (i) maximizing expected reward under a resource budget constraint, and (ii) maximizing expected profit (reward minus resource cost). They establish that smRmD and its profit-maximizing variant (smRmD-P) are generally NP-hard, but identify special cases solvable in polynomial time, including single resource type scenarios and cases with laminar set families and conflicting demands. The paper develops approximation algorithms, including a bicriteria approximation for smRmD-P, and analyzes sample average approximation methods to handle large or probabilistic scenario sets, providing theoretical bounds on sample sizes needed for solution quality guarantees. Computational experiments demonstrate the impact of problem parameters such as budget and demand conflicts on solution quality and run times, highlighting the practical challenges and tractability aspects of smRmD.