An electromagnetic meta-heuristic for the nurse scheduling problem |
| |
Authors: | Broos Maenhout Mario Vanhoucke |
| |
Institution: | (1) Faculty of Economics and Business Administration, Ghent University, Gent, Belgium;(2) Operations & Technology Management Centre, Vlerick Leuven Gent Management School, Gent, Belgium |
| |
Abstract: | In this paper, we present a novel meta-heuristic technique for the nurse scheduling problem (NSP). This well-known scheduling
problem assigns nurses to shifts per day maximizing the overall quality of the roster while taking various constraints into
account. The problem is known to be NP-hard.
Due to its complexity and relevance, many algorithms have been developed to solve practical and often case-specific models
of the NSP. The huge variety of constraints and the several objective function possibilities have led to exact and meta-heuristic
procedures in various guises, and hence comparison and state-of-the-art reporting of standard results seem to be a utopian
idea.
We present a meta-heuristic procedure for the NSP based on the framework proposed by Birbil and Fang (J. Glob. Opt. 25, 263–282, 2003). The Electromagnetic (EM) approach is based on the theory of physics, and simulates attraction and repulsion
of sample points in order to move towards a promising solution. Moreover, we present computational experiments on a standard
benchmark dataset, and solve problem instances under different assumptions. We show that the proposed procedure performs consistently
well under many different circumstances, and hence, can be considered as robust against case-specific constraints. |
| |
Keywords: | Electromagnetic meta-heuristic Local search Nurse scheduling |
本文献已被 SpringerLink 等数据库收录! |
|