INFORMS Journal on Computing
HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS
QUICK SEARCH:   [advanced]


     

INFORMS JOURNAL ON COMPUTING
Vol. 21, No. 3, Summer 2009, pp. 468-479
DOI: 10.1287/ijoc.1080.0298
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Download to citation manager
Right arrow reprints & permissions
Google Scholar
Right arrow Articles by Li, J.
Right arrow Articles by Burke, E. K.

A Component-Based Heuristic Search Method with Evolutionary Eliminations for Hospital Personnel Scheduling

Jingpeng Li, Uwe Aickelin, Edmund K. Burke

School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, United Kingdom
School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, United Kingdom
School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, United Kingdom
jpl{at}cs.nott.ac.uk
uxa{at}cs.nott.ac.uk
ekb{at}cs.nott.ac.uk

Nurse rostering is a complex scheduling problem that affects hospital personnel on a daily basis all over the world. This paper presents a new component-based approach with evolutionary eliminations for a nurse scheduling problem arising at a major UK hospital. The main idea behind this technique is to decompose a schedule into its components (i.e., the allocated shift pattern of each nurse), and then to implement two evolutionary elimination strategies mimicking natural selection and the natural mutation process on these components, respectively, to iteratively deliver better schedules. The worthiness of all components in the schedule has to be continuously demonstrated for them to remain there. This demonstration employs an evaluation function that evaluates how well each component contributes toward the final objective. Two elimination steps are then applied: the first elimination removes a number of components that are deemed not worthy to stay in the current schedule; the second elimination may also throw out, with a low level of probability, some worthy components. The eliminated components are replenished with new ones using a set of constructive heuristics using local optimality criteria. Computational results using 52 data instances demonstrate the applicability of the proposed approach in solving real-world problems.

Key words: nurse rostering; constructive heuristic; local search; evolutionary elimination
History: received December 2005; revised March 2008; accepted July 2008.






HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS
Copyright © 2009 by INFORMS.