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.
|