Heuristic methods for the capacitated stochastic lot-sizing problem under the static-dynamic uncertainty strategy

Abstract

We consider a lot-sizing problem in a single-item single-stage production system facing non-stationary stochastic demand in a finite planning horizon. Motivated by common practice, the set-up times need to be determined and frozen once and for all at the beginning of the horizon while decisions on the exact lot sizes can be deferred until the setup epochs. This operating scheme is referred to as the static-dynamic uncertainty strategy in the literature. It has been shown that a modified base stock policy is optimal for a capacitated system with minimum lot size restrictions under the static-dynamic uncertainty strategy. However, the optimal policy parameters require an exhaustive search, for which the computational time grows exponentially in the number of periods in the planning horizon. In order to alleviate the computational burden for real-life size problems, we developed and tested seven different heuristics for computational efficiency and solution quality. Our extensive numerical experiments showed that average optimality gaps less than 0.1% and maximum optimality gaps below 4% can be attained in reasonable running times by using a combination of these heuristics.