A comparison of integer programming formulations and variable-fixing method for the nurse scheduling problem

The nurse scheduling problem (NSP) aims to optimize a schedule of work periods (shifts) for nurses so that the schedule simultaneously balances the workload among nurses and maintains the skill level of the nurse team in each shift. In this paper, we present several mixed integer programming models for the NSP and compare them through computational experiments. The results are given for a typical benchmark instance with 25 nurses. In practical use, some constraints cannot be easily modeled, and so on-site schedulers often require either a flexible schedule or multiple good solutions so that they can adjust the final shift schedule. To satisfy this need, we propose a variable-fixing method to list the common features among all the optimal solutions and to generate solutions that are optimal with respect to divergence.