Nurse Rostering Benchmark Data Sets

[ home ] [ nurse ] [ multi-activity ] [ changes ] [ contact ]

Lower bounds and references

The benchmark data sets are taken from a variety of sources around the world. These sources include industrial collaborators and scientific publications. Most of the instances are based on real world scenarios and a lot of them are nurse rostering problems.

All problem instances and best known solutions can also be found under /Benchmarks in the installation directory of RosterViewer.

ANROM

These instances are based on the data used by Greet Vanden-Berghe in her PhD thesis "An Advanced Model and Novel Meta-heuristic Solution Methods to Personnel Scheduling in Healthcare" [VAN02] and in the papers [BUR99] and [BUR01]. A formal description of her model is also available here.

BCV-2.46.1

Best Solutions Date Found by
1572
Lower Bounds Date Found by
1572 The only employees able to receive D shifts are A, B and C and A, B and C cannot work any shift type other than D. Using this decomposition, the optimal assignment of D shifts to these employees has a combined penalty of 612. Looking at all the other employees and examining the constraints for cover, complete weekends and personal requests only, it is possible to show that there is an unavoidable penalty of 960. Therefore a total unavoidable penalty of 1572.

BCV-3.46.2

Best Solutions Date Found by
894
Lower Bounds Date Found by
894 Linear programming formulation solved using column generation.

BCV-4.13.1

Best Solutions Date Found by
10
Lower Bounds Date Found by
10 Only employee A can be assigned DH shifts without a penalty being incurred. However there are 29 DH shifts to assign and A can work a maximum of 19 without incurring a penalty which is larger than if they were assigned to other employees. Therefore the other 10 DH shifts must be assigned to other employees at the expense of an unavoidable penalty of 10.
10 Linear programming formulation solved using column generation.

BCV-5.4.1

Best Solutions Date Found by
48
Lower Bounds Date Found by
48 This very small instance can be solved to optimality using CPLEX.

BCV-7.10.1

Best Solutions Date Found by
381
Lower Bounds Date Found by
381 Looking at the cover constraints, there are 1184 hours of work to assign. There are also 5 annual leave requests which counts as 30 hours of work. However, looking at the max hours worked constraint, the employees request a max total of 1026 hours of work. Therefore in order to satisfy cover, (1184 + 30) - 1026 = 188 hours of overtime will have to be assigned. This creates an unavoidable penalty of 376 (weight=2). Using this IP model we can also show using CPLEX that there is an unavoidable penalty of 5 in the week in which the annual leave requests are made. This gives a lower bound for the full problem of 381.

BCV-8.13.1

Best Solutions Date Found by
148
Lower Bounds Date Found by
148 Employee A can only work DH shifts and no other employees can work the DH shifts. Hence in order to satisfy cover, A has an unavoidable penalty of 20. Looking at the cover constraints, there are 1600 hours of work to assign. There are also 20 annual leave requests which counts as 160 hours of work. However, looking at the max hours worked constraint, the employees request a max total of 1632 hours of work. Therefore in order to satisfy cover, (1600 + 160) - 1632 = 128 hours of overtime will have to be assigned. This creates an unavoidable penalty of 128. Therefore there is a total unavoidable penalty of 148.

BCV-A.12.2

Best Solutions Date Found by
1875 Feb-2012 Fan Xue, C.Y. Chan, W.H. Ip and C.F. Cheung at Department of Industrial and Systems Engineering, Hong Kong Polytechnic University.
Algorithm: Pearl Hunter hyper-heuristic, low-level heuristics provided by HyFlex (CHeSC 2011).
Lower Bounds Date Found by

Azaiez

This instance is taken from Azaiez and Sharif's 2005 paper [AZA05].

BCDT

This instance is based on the nurse rostering problem described in Bellanti et al's 2004 paper [BEL04].

Lower Bounds Date Found by
100 Feb-2010 Column generation.

GPost

These instances were provided by Gerhard Post. A description of the problem is available here.

GPost

Best Solutions Date Found by
5
Lower Bounds Date Found by
5 28-Aug-2008 CPLEX solving a relaxed model. The relaxation assumes one shift type and removes all constraints except: Cover, one shift per day, no split weekends, min and max shifts per week, max consecutive working weekends, on-off-on and off-on-off sequences, shift requests and consecutive working days.
5 Apr-2009 Linear programming formulation solved using column generation.

GPost-B

Best Solutions Date Found by
3 07-Oct-2008 Enumerating all feasible schedules (work patterns) with score <= 2 (there are 16679 for full timers and 65298 for part timers) and then using CPLEX to assign them. It takes CPLEX 10 about 8 seconds to solve it (on a Core 2 Duo 2.83GHz). The OPL project is available here.
Lower Bounds Date Found by
3 07-Oct-2008 Solved to optimality using CPLEX by enumerating all feasible schedules (work patterns) with score <= 2.
3 Apr-2009 Linear programming formulation solved using column generation.

HED

This instance is based on the physician rostering problem described in Puente et al's 2009 paper [PUE09].

Lower Bounds Date Found by
136 Feb-2010 Column generation.

Ikegami

These instances are the ones described in Ikegami and Niwa's 2003 paper [IKE03]. They are also available at Ikegami's homepage. They were originally solved by Ikegami and Niwa using a hybrid tabu search.

Ikegami-3Shift-DATA1

Best Solutions Date Found by
2 Oct-2009 Nobuo Inui, Kenta Maeda and Atsuko Ikegami using CPLEX 11.
Lower Bounds Date Found by
2 Apr-2009 Linear programming formulation solved using column generation.

Ikegami-3Shift-DATA1.1

Best Solutions Date Found by
3 Oct-2009 Nobuo Inui, Kenta Maeda and Atsuko Ikegami using CPLEX 11.
Lower Bounds Date Found by
3 Apr-2009 Linear programming formulation solved using column generation.

Ikegami-3Shift-DATA1.2

Best Solutions Date Found by
3 Oct-2009 Nobuo Inui, Kenta Maeda and Atsuko Ikegami using CPLEX 11.
Lower Bounds Date Found by
3 Apr-2009 Linear programming formulation solved using column generation.

LLR

This instance is taken from Li, Lim and Rodrigues' 2003 paper [LI03].

Best Solutions Date Found by
301 Enumerating all feasible work patterns and using CPLEX to assign them produces an optimal solution of 301. The ILOG OPL project is available here.
Lower Bounds Date Found by
301 Solved to optimality using CPLEX.
301 Apr-2009 Linear programming formulation solved using column generation.

Millar

This instance is described in Ikegami and Niwa's 2003 paper [IKE03] (and is also available at Ikegami's homepage). It was originally presented by Millar and Kiragu [MIL98].

Montreal

These data sets are physician and nurse rostering problems from hospitals in the area of Montreal, Canada. Most of the data sets are relatively large (up to 6 weeks planning horizon and 50+ employees). In these instances, cover requirements are specified by time period of the day rather than per shift type. The data was provided by Gilles Pesant.

CHILD

Best Solutions Date Found by
149
Lower Bounds Date Found by
149 Oct-2009 Linear programming formulation solved using column generation.

ERMGH

Best Solutions Date Found by
779
Lower Bounds Date Found by
779 Oct-2009 Linear programming formulation solved using column generation.

ERRVH

Best Solutions Date Found by
2001
Lower Bounds Date Found by
2001 Oct-2009 Linear programming formulation solved using column generation.

MER

Best Solutions Date Found by
7081
Lower Bounds Date Found by
7079 Sep-2010 Linear programming formulation solved using column generation.

MER

Best Solutions Date Found by
7081
Lower Bounds Date Found by
7079 Sep-2010 Linear programming formulation solved using column generation.

CHILD-A2

Best Solutions Date Found by
1095 July-2011 Fan Xue using a hyperheuristic method.
Lower Bounds Date Found by

ERMGH-A

Best Solutions Date Found by
795
Lower Bounds Date Found by

ERMGH-B

Best Solutions Date Found by
1355 Feb-2012 Fan Xue, C.Y. Chan, W.H. Ip and C.F. Cheung at Department of Industrial and Systems Engineering, Hong Kong Polytechnic University.
Algorithm: Pearl Hunter hyper-heuristic, low-level heuristics provided by HyFlex (CHeSC 2011).
1459
Lower Bounds Date Found by

ERRVH-A

Best Solutions Date Found by
2135 Feb-2012 Fan Xue, C.Y. Chan, W.H. Ip and C.F. Cheung at Department of Industrial and Systems Engineering, Hong Kong Polytechnic University.
Algorithm: Pearl Hunter hyper-heuristic, low-level heuristics provided by HyFlex (CHeSC 2011).
2142 July-2011 Fan Xue using a hyperheuristic method.
Lower Bounds Date Found by

ERRVH-B

Best Solutions Date Found by
3105 Feb-2012 Fan Xue, C.Y. Chan, W.H. Ip and C.F. Cheung at Department of Industrial and Systems Engineering, Hong Kong Polytechnic University.
Algorithm: Pearl Hunter hyper-heuristic, low-level heuristics provided by HyFlex (CHeSC 2011).
3121 July-2011 Fan Xue using a hyperheuristic method.
Lower Bounds Date Found by

MER-A

Best Solutions Date Found by
8814 Feb-2012 Fan Xue, C.Y. Chan, W.H. Ip and C.F. Cheung at Department of Industrial and Systems Engineering, Hong Kong Polytechnic University.
Algorithm: Pearl Hunter hyper-heuristic, low-level heuristics provided by HyFlex (CHeSC 2011).
9017 July-2011 Fan Xue using a hyperheuristic method.
Lower Bounds Date Found by

Musa

This is an instance taken from a fairly early nurse rostering paper by Musa and Saxena [MUS84]. The solution given in their paper with objective function value 199 required 28.3 seconds using a UNIVAC 1100. The optimal solution is 175 (solved using this IP model).

ORTEC01

This is the January instance in [BUR05] and instance 12 in [BUR07] by Burke et al. To model the problem with minimal changes, some of the hard constraints in the original problem have been changed to soft constraints but with very large weights. Feasible solutions (i.e. solutions without the highly weighted soft constraints broken) are known to exist though.

ORTEC01

Best Solutions Date Found by
270 02-Aug-2008 DeWolf Fan Xue using a hybrid variable depth search.
Lower Bounds Date Found by
270 13-Aug-2008 CPLEX solving a relaxed model. The relaxation models the first five days only, assumes one shift type and removes all constraints except: Cover, one shift per day, no split weekends, min and max shifts per week, and min and max consecutive working days.
270 Apr-2009 Linear programming formulation solved using column generation.

ORTEC02

Best Solutions Date Found by
270 2009 Celia Glass and Roger Knight [GLA09].
Lower Bounds Date Found by
270 ORTEC01 is a relaxed version of ORTEC02 hence ORTEC01's optimal solution of 270 is also a lower bound for ORTEC02.
270 Apr-2009 Linear programming formulation solved using column generation.

Ozkarahan

This instance is taken from a 1989 publication by Ozkarahan [OZK89].

QMC

This data is based on a problem from Queen's Medical Centre University Hospital NHS Trust, Nottingham, UK. The problem was originally examined by Petrovic and Beddoe [BED04, BED06, PET03] who used case-based reasoning to solve it. In 2006, the problem was re-examined by Landa Silva and Le, who used a multi-objective evolutionary approach. The instances provided here are based on the problem formulation used by Landa Silva and Le (which is also very similar to the original problem). In instance QMC-1, the only changes from Landa Silva and Le's model are: the hard constraints have been changed to soft constraints but with a weight of 1000 and the coverage constraint is a hard constraint.
Instance QMC-2 is a alternative formulation which is closer to the original formulation and in which over and under cover is allowed but penalised (that is, part of the objective function).

QMC-1

Lower Bounds Date Found by
13 Apr-2009 Linear programming formulation solved using column generation provides a solution of 12.5.

QMC-2

Lower Bounds Date Found by
29 Apr-2009 Linear programming formulation solved using column generation.

SINTEF

This instance was provided by SINTEF.

T1, T2

These tour scheduling instances were created to test the tour scheduling capabilities of RosterViewer. They are loosely based on a problem presented in [TEL06].

T1-15m1d

Best Solutions Date Found by
12 01-Jul-2009 Variable depth search (construction heuristics on)
Lower Bounds Date Found by
12 01-Jul-2009 Solving a linear programming formulation using column generation.

T2-15m5d

Best Solutions Date Found by
80 01-Jul-2009 Variable depth search (construction heuristics on)
Lower Bounds Date Found by
80 01-Jul-2009 Solving a linear programming formulation using column generation.

Valouxis

This instance was taken from [VAL00] by Valouxis and Housos. It is problem number 1 in their paper. In the formulation here the hard constraints all have weight 1000 or higher. As described in the paper, the soft constraints are related to the lengths of feasible shift stretches. That is, stretches of length two have weight x, stretches of length three have weight y etc. The actual weights used by the authors are not mentioned in the paper but I am trying to contact the authors to find out out the weights used for the results given in their paper. The solution given in their paper has three workstretches of length two and two of length three. The current best solution given on this website has one workstretch of length three.

Valouxis

Best Solutions Date Found by
20
Lower Bounds Date Found by
20 06-Oct-2008 CPLEX solving a relaxed model. The relaxation merges all the shifts into one type. All feasible schedules with score <= 40 are then generated. The problem is then to select 16 of these schedules in order to satify cover whilst minimising the total score. The OPL project is available here.
20 Apr-2009 Solving a linear programming formulation using column generation provides a solution of 8. The lowest feasible integer solution >= 8 is 20. Hence a lower bound of 20.

WHPP

This instance was presented by Weil et al. in [WEI95]. The hard constraints have a weight of 1000 or higher. The constraints they describe as soft, have weights of 1.

WHPP

Best Solutions Date Found by
5
Lower Bounds Date Found by
5 02-Sep-2008 In order to satisfy cover, 90 D shifts, 110 E shifts and 70 N shifts must be assigned. This equals exactly 2100 hours. Each employee requests max 70 hours work and there are 30 employees. Therefore each employee has to receive exactly 70 hours in order to satisfy cover. N shifts are 10 hours and D and E shifts are 7 hours each. An employee cannot work N and D or E shifts and achieve exactly 70 hours work (there are no combinations of shifts which equal 70 hours other than 7 N's or 10 D's and E's). The problem can then be decomposed into assigning N's to 10 employees and E's and D's to the other 20 employees. Solving a relaxed model of the latter problem using CPLEX provides a lower bound of 5.
5 Apr-2009 Linear programming formulation solved using column generation.

References

AZA05   Azaiez, M.N. and S.S. Al Sharif, A 0-1 goal programming model for nurse scheduling. Computers and Operations Research, 2005. 32(3): pp. 491 - 507.
BED04   Beddoe, G.R. Case-Based Reasoning in Personnel Rostering. PhD Thesis, University of Nottingham, UK, 2004.
BED06   Beddoe, G.R. and S. Petrovic, Selecting and Weighting Features Using a Genetic Algorithm in a Case-Based Reasoning Approach to Personnel Rostering. European Journal of Operational Research, 2006. 175(2): pp. 649-671.
BEL04   Bellanti, F., G. Carello, F.D. Croce, and R. Tadei, A greedy-based neighborhood search approach to a nurse rostering problem. European Journal of Operational Research, 2004. 153: pp. 28-40.
BRU07   Brucker P., E.K. Burke, T. Curtois, R. Qu and G. Vanden Berge. Adaptive Construction of Nurse Schedules: A Shift Sequence Based Approach. Technical Report NOTTCS-TR-2007-1, School of Computer Science and IT, University of Nottingham, 2007.
BRU09   Brucker P., E.K. Burke, T. Curtois, R. Qu and G. Vanden Berge. A Shift Sequence Based Approach for Nurse Scheduling and a New Benchmark Dataset. Journal of Heuristics, Accepted for publication, 2009.
BUR99   Burke, E.K., P. De Causmaecker, and G. Vanden Berghe. A Hybrid Tabu Search Algorithm for the Nurse Rostering Problem, in Simulated Evolution and Learning, Selected Papers from the 2nd Asia-Pacific Conference on Simulated Evolution and Learning, SEAL 98, Springer Lecture Notes in Artificial Intelligence Volume 1585. B. McKay, et al., Editors. 1999: Springer. pp. 187-194.
BUR01   Burke, E.K., P. Cowling, P. De Causmaecker, and G. Vanden Berghe, A Memetic Approach to the Nurse Rostering Problem. Applied Intelligence, 2001. 15(3): pp. 199-214.
BUR05   Burke E.K., T. Curtois, G. Post, R. Qu and B. Veltman. A Hybrid Heuristic Ordering and Variable Neighbourhood Search for the Nurse Rostering Problem. Technical Report NOTTCS-TR-2005-3, School of Computer Science and IT, University of Nottingham, 2005.
BUR06   Burke E.K., J. Li and R. Qu. A Hybrid Model of Integer Programming and Variable Neighbourhood Search for Highly-Constrained Nurse Rostering Problems. Technical Report NOTTCS-TR-2007-2, School of Computer Science and IT, University of Nottingham, 2006.
BUR07   Burke E.K., T. Curtois, G. Post, R. Qu and B. Veltman. A Hybrid Heuristic Ordering and Variable Neighbourhood Search for the Nurse Rostering Problem. European Journal of Operational Research, 2008. 188(2): p. 330-341.
BUR07b   Burke E.K., T. Curtois, R. Qu and G. Vanden Berge. A Time Predefined Variable Depth Search for Nurse Rostering. Technical Report NOTTCS-TR-2007-6, School of Computer Science and IT, University of Nottingham, 2007. pdf
BUR07c   Burke E.K., T. Curtois, R. Qu and G. Vanden Berge. A Scatter Search for the Nurse Rostering Problem. Technical Report NOTTCS-TR-2007-7, School of Computer Science and IT, University of Nottingham, 2007. pdf
BUR09   Burke E.K., T. Curtois, R. Qu and G. Vanden Berge. A Scatter Search Methodology for the Nurse Rostering Problem. Journal of the Operational Research Society, Accepted for publication, 2009.
FIJ06   Fijn van Draat L., G. Post, B. Veldman, and W. Winkelhuijzen. Harmonious personnel scheduling. Medium Econometrische Toepassingen, 2006. 14: p 4-7.
GLA09   Glass, C.A. and R.A. Knight, The nurse rostering problem: A critical appraisal of the problem structure. European Journal of Operational Research, Accepted for publication 2009.
IKE03   Ikegami A. and A. Niwa. A Subproblem-centric Model and Approach to the Nurse Scheduling Problem. Mathematical Programming, 2003. 97(3): p. 517-541.
LI03   Li, H., A. Lim, and B. Rodrigues. A Hybrid AI Approach for Nurse Rostering Problem, in Proceedings of the 2003 ACM symposium on Applied computing. 2003. pp. 730-735.
MIL98   Millar H. H. and M. Kiragu. Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming. European Journal of Operational Research, 1998. 104: p. 582-592.
MUS84   Musa, A. and U. Saxena, Scheduling nurses using goal-programming techniques. IIE transactions, 1984. 16: pp. 216-221.
OZK89   Ozkarahan, I. The Zero-One Goal Programming Model of a Flexible Nurse Scheduling Support System, in Proceedings of International Industrial Engineering Conference, May 1989. pp.436-441.
PET03   Petrovic, S., G.R. Beddoe, and G. Vanden Berge. Storing and adapting repair experiences in employee rostering, in Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2002), Springer Lecture Notes in Computer Science Volume 2740. ed. E.K. Burke and P. De Causmaecker. 2003. p. 149-166.
PUE09   Puente, J., A. Gomez, I. Fernandez, and P. Priore, Medical doctor rostering problem in a hospital emergency department by means of genetic algorithms. Computers & Industrial Engineering, 2009. 56: pp. 1232-1242.
SOL13   Solos, Ioannis P., Ioannis X. Tassopoulos and Grigorios N. Beligiannis, A Generic Two-Phase Stochastic Variable Neighborhood Approach for Effectively Solving the Nurse Rostering Problem. Algorithms, 2013. 6: pp. 278-308.
TEL06   Tellier, P. and G. White. Generating Personnel Schedules in an Industrial Setting Using a Tabu Search Algorithm, in Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling. 2006. Brno, Czech Republic. pp. 293-302.
VAL00   Valouxis, C. and E. Housos. Hybrid optimization techniques for the workshift and rest assignment of nursing personnel. Artificial Intelligence in Medicine, 2000. 20: p. 155-175.
VAN02   Vanden Berge, G. An Advanced Model and Novel Meta-Heuristic Solution Methods to Personnel Scheduling in Healthcare. Ph.D. Thesis, University of Gent, Belgium, 2002.
WEI95   Weil, G., K. Heus, P. Francois, and M. Poujade. Constraint programming for nurse scheduling. IEEE Engineering in Medicine and Biology Magazine, 1995. 14(4): p. 417-422.