Journal
COMPUTERS & CHEMICAL ENGINEERING
Volume 28, Issue 6-7, Pages 1039-1058Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.compchemeng.2003.09.024
Keywords
stochastic dynamic programming; Markov chain; project scheduling; combinatorial optimization; heuristics
Ask authors/readers for more resources
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. (C) 2003 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available