An electromagnetism meta-heuristic for the nurse scheduling problem
Maenhout, Broos Vanhoucke, Mario
Maenhout, Broos
Vanhoucke, Mario
Citations
Altmetric:
Publication Type
Working paper
Editor
Supervisor
Publication Year
2005
Journal
Book
Publication Volume
Publication Issue
26
Publication Begin page
Publication End page
Publication Number of pages
51
Collections
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 taking both hard and soft constraints into account. The objective is to maximize the preferences of the nurses and to minimize the total penalty cost from violations of the soft constraints. 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 versions of the NSP. The enormous amount of different constraints has led to an overwhelming amount of exact and meta-heuristic procedures, and hence comparison and state-of-the-art reporting of standard results seem to be a utopian idea. The contribution of this paper is twofold. First, we present a meta-heuristic procedure for the NSP based on the framework proposed by Birbil and Fang (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. Second, we present computational experiments on a standard benchmark dataset, and solve problem instances under different assumptions. We show that our procedure performs consistently well under many different circumstances, and hence, can be considered as robust against case-specific constraints. Keywords: meta-heuristics, electromagnetism, nurse scheduling
Research Projects
Organizational Units
Journal Issue
Keywords
Programme & Portfolio Management