We consider a lot-sizing problem in a single-item single-stage production system facing non-stationary stochastic demand in a nite planning horizon. Motivated by practice, the set-up times need to be deter- mined 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 modi ed base stock policy is optimal for a capacitated system with minimum lot size restrictions under the static-dynamic uncertainty strategy. However, the opti- mal 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 develop and test seven di erent heuristics for computational eciency and solution qual- ity. Our extensive numerical experiments show 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.