Dynamic programming in a heuristically confined state space: a stochastic resource-constrained project scheduling application

摘要

The resource-constrained project scheduling problem (RCPSP) is a significant challenge in highly regulated industries, such as pharma-ceuticals and agrochemicals, where a large number of candidate new products must undergo a set of tests for certification. We propose a novel way of addressing the uncertainties in the RCPSP including the uncertainties in task durations and costs, as well as uncertainties in the results of tasks (success or failure) by using a discrete time Markov chain, which enables us to model probabilistic correlation of the uncertain parameters. The resulting stochastic optimization problem can be solved by using dynamic programming, but the computational load renders this impractical. Instead, we develop a new way to combine heuristic solutions through dynamic programming in the state space that the heuristics generate. The proposed approach is tested on a simplified version of RCPSP that has a fairly complicated stochastic nature, with 1,214,693,756 possible parameter realizations (scenarios), and involves five projects and 17 tasks. As a result, an on-line policy is obtained, which can use the information states in on-line decision making and improve the heuristics rather than a fixed solution obtained by the previous mathematical programming (MILP) problem formulations.