A grasp-knapsack hybrid for a nurse-scheduling problem

This paper is concerned with the application of a GRASP approach to a nurse-scheduling problem in which the objective is to optimise a set of preferences subject to a set of binding constraints. The balance between feasibility and optimality is a key issue. This is addressed by using a knapsack mode...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2009-08, Vol.15 (4), p.351-379
Main Authors: Goodman, Melissa D., Dowsland, Kathryn A., Thompson, Jonathan M.
Format: Article
Language:English
Subjects:
Artificial Intelligence
Calculus of Variations and Optimal Control
Optimization
Feasibility
Genetic algorithms
Heuristic
Management Science
Mathematical programming
Mathematics
Mathematics and Statistics
Neighborhoods
Nurses
Operations Research
Operations Research/Decision Theory
Scheduling
Shift work
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper is concerned with the application of a GRASP approach to a nurse-scheduling problem in which the objective is to optimise a set of preferences subject to a set of binding constraints. The balance between feasibility and optimality is a key issue. This is addressed by using a knapsack model to ensure that the solutions produced by the construction heuristic are easy to repair. Several construction heuristics and neighbourhoods are compared empirically. The best combination is further enhanced by a diversification strategy and a dynamic evaluation criterion. Tests show that it outperforms previously published approaches and finds optimal solutions quickly and consistently.
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-007-9066-7