A Stochastic Programming Approach for Cyclic Personnel Scheduling with Double Shift Requirement

摘要

We study cyclic personnel scheduling with double shift requirement under demand uncertainty. The problem is formulated as a two-stage stochastic integer program with integer recourse. Solving it with commercial software CPLEX takes extended period of time. We explore an exact approach based on Benders decomposition technique and compare its performance to a heuristics approach based on genetic algorithm and a mip approach, solving the original problem by a commercial mip solver. A special solution method allow us to obtain optimal solutions to subproblems efficiently. This method are applicable to both exact and heuristic approaches which significantly accelerate overall solution process. Numerical results illustrate that the proposed approach, exact approach based on Benders decomposition technique, outperform the heuristics approach based on genetic algorithm and the CPLEX mip solver in all 16 instances.