A comparative evaluation of modeling approaches to the labor shift scheduling problem

The labor shift scheduling problem has traditionally been formulated using the set covering approach proposed by Dantzig. The size of the resulting integer model with this approach, however, has been found to be very large to solve optimally in most practical applications. Recently, Bechtold and Jacobs proposed a new integer programming formulation requiring a significantly smaller number of variables and nonzeros in the A-matrix than the equivalent set covering formulation. However, due to its assumptions, this approach has remained limited to the special cases of the shift scheduling problem. Earlier, we presented another implicit modeling approach that is applicable to the general problem without any of the limitations of Bechtold and Jacobs. This approach also requires a substantially smaller number of variables and nonzeros in the A-matrix than the equivalent set covering formulation. In this paper, we relax the assumptions of Bechtold and Jacobs and present a generalized version of it. The extended formulation of Bechtold and Jacobs, although requiring a smaller number of variables, has more constraints, more nonzeros in the A-matrix, and significantly higher density than the formulation of Aykin. We compare these modeling approaches through solving (optimally) 220 problems involving as many as 32 928 shift variations. Our computational results show that the time needed to locate an optimal shift schedule and the percentage of the problems solved optimally with Aykin's formulation are substantially better than those with the formulation of Bechtold and Jacobs.