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

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

0.00 Avg rating0 Votes
Article ID: iaor200677
Country: Netherlands
Volume: 28
Issue: 6/7
Start Page Number: 1039
End Page Number: 1058
Publication Date: Jun 2004
Journal: Computers and Chemical Engineering
Authors: , ,
Keywords: heuristics, programming: dynamic
Abstract:

The resource-constrained project scheduling problem (RCPSP) is a significant challenge in highly regulated industries, such as pharmaceuticals 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.

Reviews

Required fields are marked *. Your email address will not be published.