Optimal Shift Scheduling with Multiple Break Windows

This paper presents a new integer programming model for optimal shift scheduling with multiple rest and lunch breaks, and break windows. A set-covering approach for this problem was originally developed by Dantzig (1954). Since then, a number of set-covering-based formulations have been proposed in the literature. These formulations require an integer variable for every shift type, shift start time, and rest/lunch break placement combination. Unfortunately, the number of integer variables required is rather large, making them impractical to solve for an optimal solution in most applications. We present a new approach in which a set of break variables is introduced for every shift-break type combination to determine the break placements. This approach leads to a significantly improved integer programming model requiring substantially smaller number of variables and computer memory. We tested the proposed approach with 40 test problems involving between 1,728 and 8,640 shift variations, and five demand patterns. Our results showed that the proposed formulation is very useful in solving large shift scheduling problems optimally.