Results for the Nurse Rostering Problem

Computer Systems Laboratory
University of Patras

Last Update: 03/10/2010

CSL Timetabling Team
Dr. Christos Valouxis Dr. Christos Gogos, MSc Dr. George Goulas Dr. Panayiotis Alefragis Prof. Efthymios Housos
INRC2010 competition logo

The Nurse Rostering Problem (NRP) is a difficult combinatorial problem due to its size and complexity. This page presents the Computer Systems Laboratory research team results from working with this particular problem and more precisely to the International Nurse Rostering Competition 2010 problem.

The solution that was submitted by the CSL research team won all three tracks of the INRC2010 competition, which was organized by CODeS, SINTEF and SaTT, lasted between 1/3/2010 and 20/6/2010 and was supported by the PATAT 2010 International Conference. The solution scored the best results amongst 15 competitors who had submitted final solutions that conformed to the competition requirements. The three competition tracks were variations of the same problem, with differences in problem size and available computation time. The implemented software used Integer Programming combined with heuristic techniques. The solution approach was presented at the 8th Conference on Practice and Theory of Automated Timetabling 2010 at Belfast, Ireland.

The same research team achieved a second place award in the 2nd International Timetabling Competition in 2007. More on our work for this competition is available here.

The following table summarizes the non-hidden competition datasets.

Problem Instance Skills Shift Types Contracts Employees
sprint_early01, sprint_early02, sprint_early03, sprint_early04, sprint_early05, sprint_early06, sprint_early07, sprint_early08, sprint_early09, sprint_early10 1 4 4 10
sprint_late01 1 4 3 10
sprint_late02 1 3 3 10
sprint_late03, sprint_late04, sprint_late05, sprint_late06, sprint_late07, sprint_late08, sprint_late09, sprint_late10 1 4 3 10
medium_early01, medium_early02, medium_early03, medium_early04, medium_early05 1 4 4 31
medium_late01, medium_late03 1 4 4 30
medium_late02, medium_late04 1 4 3 30
medium_late05 2 5 4 30
long01_early, long_early02, long03_early, long_early04, long_early05 2 5 3 49
long_late01, long_late03, long_late05 2 5 3 50
long_late02 2 5 4 50
long_late04 2 5 5 50

The following table presents the cover requirements for the problem instance long_early01.

Shift Type Start – End Skills Mon Tue Wed Thu Fri Sat Sun
E 06:30-14:30 Nurse 8 8 8 8 8 6 6
D 08:30-16:30 Nurse 5 5 5 5 5 3 3
DH 08:30-16:30 Head Nurse 2 2 2 2 2 1 1
L 4:30-22:30 Nurse 8 8 8 8 8 6 6
N 22:30-06:30 Nurse 6 6 6 6 6 4 4

The following table presents the cost evaluation for the best solutions we have using our approach.

Instance Cost Instance Cost Instance Cost Instance Cost
sprint_early01 56 sprint_late01 37 medium_early01 240 long_early01 197
sprint_early02 58 sprint_late02 42 medium_early02 240 long_early02 219
sprint_early03 51 sprint_late03 48 medium_early03 236 long_early03 240
sprint_early04 59 sprint_late04 76 medium_early04 237 long_early04 303
sprint_early05 58 sprint_late05 44 medium_early05 303 long_early05 284
sprint_early06 54 sprint_late06 42 medium_late01 159 long_late01 239
sprint_early07 56 sprint_late07 43 medium_late02 20 long_late02 231
sprint_early08 56 sprint_late08 17 medium_late03 30 long_late03 222
sprint_early09 55 sprint_late09 17 medium_late04 35 long_late04 228
sprint_early10 52 sprint_late10 44 medium_late05 113 long_late05 83

© 2010, Computer Systems Laboratory, University of Patras. Maintained by Dr. George Goulas.

Valid XHTML 1.0 Transitional Valid CSS!