A composite branch and cut algorithm for optimal shift scheduling with multiple breaks and break windows

This paper presents a new branch and cut algorithm for optimal shift scheduling with multiple breaks and break windows. The proposed algorithm is based on an implicit formulation of the problem requiring significantly smaller number of variables than the set covering formulation of Danzig. The new algorithm, adding cuts, developing upper bounds for the variables, and employing an efficient rounding heuristic, was tested successfully with 90 test problems involving between 2160 and 32 928 shift variations and five demand profiles. Our results show that large shift scheduling problems can be solved optimally with the proposed branch and cut algorithm and the implicit formulation.