Employee Shift Scheduling Benchmark Data Sets
[ benchmarks ] [ 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 Roster Booster.
These instances are based on the data used by Greet VandenBerghe in her PhD thesis "An Advanced Model and Novel Metaheuristic 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.
BCV2.46.1


BCV3.46.2


BCV4.13.1


BCV5.4.1


BCV7.10.1


BCV8.13.1


BCVA.12.2


This instance is based on the nurse rostering problem described in Bellanti et al's 2004 paper [BEL04].
Lower Bounds  Date  Found by 
100  Feb2010  Column generation. 
These instances were provided by Gerhard Post. A description of the problem is available in English and Dutch.
GPost


GPostB


This instance is based on the physician rostering problem described in Puente et al's 2009 paper [PUE09].
Lower Bounds  Date  Found by 
136  Feb2010  Column generation. 
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.
Ikegami3ShiftDATA1


Ikegami3ShiftDATA1.1


Ikegami3ShiftDATA1.2


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


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


ERMGH


ERRVH


MER


MER


CHILDA2


ERMGHA


ERMGHB


ERRVHA


ERRVHB


MERA


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


ORTEC02


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 casebased reasoning to solve it.
In 2006, the problem was reexamined by Landa Silva and Le, who used a
multiobjective 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 QMC1, 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 QMC2 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).
QMC1
Lower Bounds  Date  Found by 
13  Apr2009  Linear programming formulation solved using column generation provides a solution of 12.5. 
QMC2
Lower Bounds  Date  Found by 
29  Apr2009  Linear programming formulation solved using column generation. 
These tour scheduling instances were created to test the tour scheduling capabilities of Roster Booster. They are loosely based on a problem presented in [TEL06].
T115m1d


T215m5d


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


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


AZA05  Azaiez, M.N. and S.S. Al Sharif, A 01 goal programming model for nurse scheduling. Computers and Operations Research, 2005. 32(3): pp. 491  507.  
BED04  Beddoe, G.R. CaseBased Reasoning in Personnel Rostering. PhD Thesis, University of Nottingham, UK, 2004. pdf  
BED06  Beddoe, G.R. and S. Petrovic, Selecting and Weighting Features Using a Genetic Algorithm in a CaseBased Reasoning Approach to Personnel Rostering. European Journal of Operational Research, 2006. 175(2): pp. 649671. pdf  
BEL04  Bellanti, F., G. Carello, F.D. Croce, and R. Tadei, A greedybased neighborhood search approach to a nurse rostering problem. European Journal of Operational Research, 2004. 153: pp. 2840.  
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 NOTTCSTR20071, School of Computer Science and IT, University of Nottingham, 2007. pdf  
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. pdf  
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 AsiaPacific Conference on Simulated Evolution and Learning, SEAL 98, Springer Lecture Notes in Artificial Intelligence Volume 1585. B. McKay, et al., Editors. 1999: Springer. pp. 187194. pdf  
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. 199214. pdf  
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 NOTTCSTR20053, School of Computer Science and IT, University of Nottingham, 2005. pdf  
BUR06  Burke E.K., J. Li and R. Qu. A Hybrid Model of Integer Programming and Variable Neighbourhood Search for HighlyConstrained Nurse Rostering Problems. Technical Report NOTTCSTR20072, School of Computer Science and IT, University of Nottingham, 2006. pdf  
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. 330341. pdf  
BUR07b  Burke E.K., T. Curtois, R. Qu and G. Vanden Berge. A Time Predefined Variable Depth Search for Nurse Rostering. Technical Report NOTTCSTR20076, 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 NOTTCSTR20077, 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 47.  
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 Subproblemcentric Model and Approach to the Nurse Scheduling Problem. Mathematical Programming, 2003. 97(3): p. 517541.  
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. 730735.  
MIL98  Millar H. H. and M. Kiragu. Cyclic and noncyclic scheduling of 12 h shift nurses by network programming. European Journal of Operational Research, 1998. 104: p. 582592.  
MUS84  Musa, A. and U. Saxena, Scheduling nurses using goalprogramming techniques. IIE transactions, 1984. 16: pp. 216221.  
OZK89  Ozkarahan, I. The ZeroOne Goal Programming Model of a Flexible Nurse Scheduling Support System, in Proceedings of International Industrial Engineering Conference, May 1989. pp.436441.  
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. 149166. pdf  
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. 12321242.  
SOL13  Solos, Ioannis P., Ioannis X. Tassopoulos and Grigorios N. Beligiannis, A Generic TwoPhase Stochastic Variable Neighborhood Approach for Effectively Solving the Nurse Rostering Problem. Algorithms, 2013. 6: pp. 278308.  
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. 293302.  
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. 155175.  
VAN02  Vanden Berge, G. An Advanced Model and Novel MetaHeuristic Solution Methods to Personnel Scheduling in Healthcare. Ph.D. Thesis, University of Gent, Belgium, 2002. pdf  
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. 417422. 