Stochastic programming can yield significant savings over deterministic approaches. For example, the stochastic approach for the shift scheduling problem solved in Pacqueau and Soumis (2011) yields more than 15% savings on some instances. However, stochastic approaches always lead to very large problems (around 10 million IP variables in Pacqueau and Soumis (2011)), since a recourse must be computed for every scenario. There is no fast and exact method for solving such problems. In this article, the algorithm presented in Pacqueau and Soumis (2011) is improved in two ways: a Benders cuts dynamic management algorithm for the master problem and a multithreaded implementation to solve the subproblems. Those two improvements yield a heuristic able to solve a 10 million variables IP problem in less than 5 minutes, with a very good accuracy, and enables the resolution of larger instances. This algorithm uses general ideas that can easily be adapted to every problem that, in order to be solved, is split into a master problem and several subproblems: L-shaped method, column generation...