Shift scheduling when the demand for employees is stochastic is usually done in two steps. Since employees need to know their shifts before the demand is known (e.g. two weeks in advance), the shifts are scheduled using a forecast demand. Once the demand is known, a recourse - depending on the company and legislation - may be possible. For example, overtime can be added for some employees, part-time employees can be hired, or the breaks schedule can be changed. This is a deterministic approach. We propose an alternative method for scheduling work shifts, and we thoroughly study and quantify the savings. Stochastic programming is used for both steps (full-time shifts and recourse) using the stochastic distribution of the demand. The resulting problem is hard to solve: 10 million IP variables for a 96-period problem with 500 scenarios. We develop a heuristic that is fast (sometimes less than 15 minutes) and yields significant savings over deterministic solutions (from 0.5% to 15%, depending on the instance). The stochastic approach is worthwhile, since the computational time is low, the solution is nearly always better, and the deterministic approach turns out to be unstable. The stochastic approach presented here is worthwhile since the computational time is low and it provides better solutions in general (savings of up to 15%) than those of the deterministic approach, which can be unstable under stochastic demand.