A scenario generation-based lower bounding approach for stochastic scheduling problems

Abstract

In this paper, we investigate scenario generation methods to establish lower bounds on the optimal objective value for stochastic scheduling problems that contain random parameters with continuous distributions. In contrast to the Sample Average Approximation (SAA) approach, which yields probabilistic bound values, we use an alternative bounding method that relies on the ideas of discrete bounding and recursive stratified sampling. Theoretical support is provided for deriving exact lower bounds for both expectation and conditional value-at-risk objectives. We illustrate the use of our method on the single machine total weighted tardiness problem. The results of our numerical investigation demonstrate good properties of our bounding method, compared with the SAA method and an earlier discrete bounding method.

Keywords:

• scheduling
• stochastic programming
• scenario generation
• discrete bounding
• total weighted tardiness

Acknowledgements

This work has been supported by the National Science Foundation under Grant CMMI-0856270.

Notes

1 Such a solution can be obtained from a deterministic problem using expected values for the random parameters.