A greedy-based neighborhood search approach to a nurse rostering problem

A practical nurse rostering problem, which arises at a ward of an Italian hospital, is considered. The nurse rostering problem is a typical employee timetabling problem, where each month it is required to generate the nursing staff shifts subject to various contractual and operational requirements. These requirements may be in conflict especially for those months in which manpower is reduced due to seasonal holidays. It is required to consider both holidays planning and parametric contractual constraints, but no cyclic schedules and corresponding weekly patterns. A local search approach is introduced which is based on a neighborhood operating on partial solutions completed by means of a greedy procedure so as to avoid the generation of infeasible solutions. Both a tabu search procedure and an iterated local search procedure are proposed. The solutions computed by the proposed procedures compare well with respect to a straightforward lower bound and strongly outperform those manually generated in the hospital ward. The proposed approach is now currently used on site. (C) 2003 Elsevier B.V. All rights reserved.