A hybrid fix-and-optimize and simulated annealing approaches for nurse rostering problem. (July 2020)

• Record Type: Journal Article
• Authors: Turhan, Aykut Melih; Bilgen, Bilge
• Is Part Of: Computers & industrial engineering. Volume 145(2020)
• Publication Date: 2020-07
• Subjects: OR in health services -- Nurse rostering problem -- Fix-and-relax -- Fix-and-optimize -- Simulated annealing; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106531
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The Nurse Rostering Problem is solved via a hybrid algorithm. The hybrid algorithm combines MIP-based heuristics and Simulated Annealing. Initial solutions are found by the Fix-and-Relax heuristic. Solutions are improved by the Fix-and-Optimize heuristic and Simulated Annealing. Seven new best-known results are reported outperforming the state-of-the-art. Abstract: The Nurse Rostering Problem (NRP) is a complex scheduling problem in which nurses must be assigned to shifts according to a set of constraints. The NRP is difficult to solve to optimality due to its combinatorial structure. In this paper, we propose a hybrid solution algorithm that combines Mixed Integer Programming (MIP) based heuristics—namely Fix-and-Relax (F&R) and Fix-and-Optimize (F&O)—and Simulated Annealing (SA) to solve the NRP. In MIP-based heuristics, a problem is decomposed into a set of smaller problems and each problem is iteratively solved to optimality. In the hybrid approach, high-quality initial solutions are obtained via the F&R algorithm and fed to the SA part of the algorithm. When solutions can no longer be improved, the F&O algorithm is inserted into the SA algorithm. This enables the hybrid algorithm to diversify the search space and provide better solutions. To assess the quality and efficiency of the hybrid approach, we use 24 publicly available test instances recently introduced in literature in the field. Computational results show that the hybrid method outperforms other advanced solution techniques in most of the test data and seven new best-known results are reported.