Block-based state-expanded network models for multi-activity shift scheduling

This paper presents new mixed-integer linear programming formulations for multi-activity shift scheduling problems (MASSP). In these formulations, the rules governing shift feasibility are encoded in block-based state-expanded networks in which nodes are associated with states and arcs represent assignments of blocks of work or break periods inducing state transitions. A key advantage of these formulations is that for the anonymous MASSP in which all employees are considered as equal only a single network with integer flow variables is needed as long as the network encodes all shift composition rules. A challenging aspect is that the networks can become very large, yielding huge models that are hard to solve for large problem instances. To address this challenge, this paper proposes two exact modeling techniques that substantially reduce the size of the model instances: First, it introduces a set of aggregate side constraints enforcing that an integer flow solution can be decomposed into paths representing feasible shifts. Second, it proposes to decouple the shift composition from the assignment of concrete activities to blocks of work periods, thereby removing a large amount of symmetry from the original model. In a computational study with two MASSP instance sets from the literature dealing with shift scheduling problems, we demonstrate the effectiveness of these techniques for reducing the both size of the model instances and the solution time: We are able to solve all instances, including more than 70 previously open instances, to optimality-the vast majority of them in less than 30 min on a notebook computer.

Automated summary

This paper presents new mixed-integer linear programming formulations for solving multi-activity shift scheduling problems (MASSP). These formulations encode shift feasibility rules in block-based state-expanded networks. The paper proposes two exact modeling techniques to address the challenge of large network sizes and reduce the solution time. Experimental results demonstrate the effectiveness of these techniques in reducing both the size of the model instances and the solution time, enabling the resolution of previously unsolved instances on a notebook computer in less than 30 minutes.