A primal bounding approach for multistage stochastic programs of resource-constrained planning and scheduling with stochastic task success

摘要

Resource-constrained planning and scheduling problems under stochastic task success, which are common in chemical industries, lend themselves well to being modelled using multistage stochastic programming (MSSP) because most projects involve a series of tasks that needs to be completed in stages and that may or may not be successful.However, these MSSP models rapidly grow and quickly become computationally intractable for real world problems.This paper presents three alternative ways to estimate objective function values in a general primal bounding framework for MSSP models of resource-constrained planning and scheduling with stochastic task success.The framework extends the concept of expected value solution.We apply the proposed framework with alternative objective function estimation approach to instances with varying project sizes (i.e., 3-, 4-, 5-, and 6- projects) with up to 4096 scenarios.The framework yields primal bounds within 1.01% of the true solutions for all tested cases with a reduction in solution times up to four orders of magnitude.