Stochastic Resource Allocation with Time Windows

The stochastic resource allocation problem with time windows (SRAPTW) refers to a class of combinatorial optimization problems which are aimed at finding the optimal scheme of assigning resources to given tasks within their time windows. In SRAPTW, the capability of resources to accomplish tasks is quantitatively characterized by probability. The expected allocation scheme should include not only the task-resource pairings but also their allocation time. This paper formulates SRAPTW as a nonlinear mixed 0–1 programming problem with the objective of maximizing the reward of completing specified tasks. Then, a general encoding/decoding method is proposed for the representation of solutions, and several different problem-solving methodologies are presented and compared. Results of computational experiments show that the utilization of SRAPTW-specific knowledge can bring in excellent performance, and a constructive heuristic combining maximal marginal return strategy and maximal probability strategy has remarkable advantages, especially in larger-scale cases.