School of Computer Science

[ benchmarks ] [ changes ] [ contact ]

ASAP Logo

Employee Shift Scheduling Benchmark Data Sets

Staff scheduling problems are found in a wide range of industries and settings. These include airlines, airports, armed forces, call/contact centres, emergency services (police, fire and ambulance crews), factories, healthcare (physicians and nurses), hospitality, retail, security personnel, transportation sector (train and bus drivers). Creating staff rosters is a challenging and time consuming process. In fact, it is known to belong to a mathematical class of problems (NP-Hard) considered intractable. Although there is no known algorithm that can guarantee optimal solutions in practical computation times, it is possible to generate rosters which are significantly better than those produced by an expert human planner, and in a fraction of the time. These models and algorithms are the focus of our research.

To help test and develop the algorithms we have compiled a diverse and challenging collection of benchmark test instances from various sources including industrial collaborators and scientific publications.

The benchmark instances and solutions are modelled using Staff Roster Solutions' XML based modelling format. It is a flexible format which handles the range of rules and requirements found in different workplaces. The data files can also be read by Staff Roster Solutions' modelling software - Roster Booster. Roster Booster is a graphical user interface which can be used to view and verify new solutions.

NEW: 24 new instances have been added to the benchmarks. The instances are designed to be easier to understand and use but still challenging to solve. They are available in a simple, plain text file format as well as an XML format.

See also:

  • - A spreadsheet of published results and papers under review.
  • - How to verify new solutions.
  • - Lower bounds.
  • - A formal description and model for the BCV instances (a zip file containing all the BCV instances is available here).
  • - The instances in the format used by HyFlex in the Cross-domain Heuristic Search Challenge are available here.

New instances

A zip file of all the instances is available. For more information on the file format, how to interpret the constraints and objectives see the new instances guide. An initial set of results using these instances is presented here. New results are announced on the changes page.

Instance Weeks Employees Shift types Best known lower bound Best known solution
Instance1 txt xml 2 8 1 607 607
Instance2 txt xml 2 14 2 828 828
Instance3 txt xml 2 20 3 1001 1001
Instance4 txt xml 4 10 2 1716 1716
Instance5 txt xml 4 16 2 1141 1148
Instance6 txt xml 4 18 3 1949 1952
Instance7 txt xml 4 20 3 1055 1058
Instance8 txt xml 4 30 4 1297 1308
Instance9 txt xml 4 36 4 406 439
Instance10 txt xml 4 40 5 4631 4631
Instance11 txt xml 4 50 6 3443 3443
Instance12 txt xml 4 60 10 4040 4046
Instance13 txt xml 4 120 18 ? 3840
Instance14 txt xml 6 32 4 1254 2149
Instance15 txt xml 6 45 6 3740 5660
Instance16 txt xml 8 20 3 3224 3323
Instance17 txt xml 8 32 4 5706 7315
Instance18 txt xml 12 22 3 4175 6300
Instance19 txt xml 12 40 5 2689 5215
Instance20 txt xml 26 50 6 4091 7480
Instance21 txt xml 26 100 8 ? 32129
Instance22 txt xml 52 50 10 ? 87848
Instance23 txt xml 52 100 16 ? 44819
Instance24 txt xml 52 150 32 ? 71765

 

Original instances

Best known solutions
GPost
File GPost.ros
Problem GPost Flag of The Netherlands
Employees 8
Schedule length 4 weeks
Cover type Cover is specified per shift.
5 html xml
7 html xml
8 html xml
Other versions GPost-B.ros Same as GPost.ros but without the requests on the first two days.
3 html xml
5 html xml
SINTEF
File SINTEF.ros
Problem SINTEF Flag of Norway
Employees 24
Schedule length 3 weeks
Cover type Cover is specified per shift.
0 html xml
1 html xml
2 html xml
ORTEC
File ORTEC01.ros
Problem ORTEC Flag of The Netherlands
Employees 16
Shift types 4
Period 31 days
Cover type Cover is specified per shift.
References [BUR06, BUR07, BUR07b, BUR07c, FIJ06]
270 html xml
280 html xml
285 html xml
290 html xml
Other versions ORTEC02.ros Identical to ORTEC01 except employee B has five "Vacation" shifts in the first full week.
270 html xml
290 html xml
QMC
File QMC-1.ros
Problem QMC Flag of the United Kingdom
Employees 19
Shift types 3
Period 28 days
Cover type Cover is specified per shift.
13 html xml
14 html xml
15 html xml
16 html xml
Other versions QMC-2.ros An alternative formulation with a couple of different constraints and in which cover may deviate from a preferred level.
29 html xml
30 html xml
31 html xml
Ikegami2
File Ikegami-2Shift-DATA1.ros
Problem Ikegami Flag of Japan
Employees 28
Shift types 2
Period 30 days
Cover type Cover is per shift and by skill level.
References [IKE03]
0 html xml
Ikegami3
File Ikegami-3Shift-DATA1.ros
Problem Ikegami Flag of Japan
Employees 25
Shift types 3
Period 30 days
Cover type Cover is per shift and by skill level.
References [IKE03]
2 html xml
5 html xml
6 html xml
Other versions Ikegami-3Shift-DATA1.1.ros Some extra personal requests.
3 html xml
9 html xml
13 html xml
Ikegami-3Shift-DATA1.2.ros More requests.
3 html xml
11 html xml
12 html xml
Millar
File Millar-2Shift-DATA1.ros
Problem Millar Flag of Japan
Employees 8
Shift types 2
Period 14 days
Cover type Cover is per shift. Over and under coverage is not allowed.
References [IKE03, MIL98]
0 html xml
0 html xml
Other versions Millar-2Shift-DATA1.1.ros A simpler version with less constraints.
0 html xml
BCV3
File BCV-3.46.2.ros
Problem ANROM Flag of Belgium
Employees 46
Shift types 3
Period 26 days
Cover type Cover is specified per shift.
References [BRU07, BRU09, BUR07b, BUR07c]
894 html xml
895 html xml
896 html xml
BCV4
File BCV-4.13.1.ros
Problem ANROM Flag of Belgium
Employees 13
Shift types 4
Period 29 days
Cover type Cover is specified per shift.
References [BRU07, BRU09, BUR07b, BUR07c]
10 html xml
Azaiez
File Azaiez.ros
Problem Azaiez Flag of Saudi Arabia
Employees 13
Shift types 2
Period 28 days
Cover type Cover is per shift and by skill level.
References [AZA05]
0 html xml
Valouxis
File Valouxis-1.ros
Problem Valouxis Flag of Greece
Employees 16
Schedule length 28 days
Shift types 3
Cover type Cover is specified per shift.
References [VAL00]
20 html xml
40 html xml
60 html xml
120 html xml
HED01
File HED01.ros 
Problem HED01 Flag of Spain
Employees 20
Schedule length 31 days
Shift types 5
Cover type Cover is per shift and includes skills.
Comments (Uses the Conditional constraint).
References [PUE09]
136 html xml
138 html xml
140 html xml
Other versions HED01b.ros A modified version used in SOL13.
129 html xml
BCDT-Sep
File BCDT-Sep.ros 
Problem BCDT Flag of Italy
Employees 20
Schedule length 30 days
Shift types 4
Cover type Cover is per shift.
References [BEL04]
100 html xml
140 html xml
160 html xml
WHPP
File WHPP.ros
Problem WHPP Flag of France
Employees 30
Schedule length 2 weeks
Shift types 3
Cover type Cover is specified per shift.
References [WEI95]
5 html xml
LLR
File LLR.ros
Problem LLR Flag of Hong Kong
Employees 27
Schedule length 7 days
Shift types 3
Cover type Cover is specified per shift.
References [LI03]
301 html xml
366 html xml
Musa
File Musa.ros
Problem Musa Flag of USA
Comments This instance is taken from a fairly early publication on nurse rostering. A UNIVAC 1100 was used to solve it in 1982!
Employees 11
Schedule length 14 days
Shift types 1
Cover type Cover is specified per shift, minimum and preferred levels are used.
References [MUS84]
175 html xml
199 html xml
Ozkarahan
File Ozkarahan.ros
Problem Ozkarahan Flag of USA
Employees 14
Schedule length 7 days
Shift types 2
Cover type Cover is specified per shift.
References [OZK89]
0 html xml
MER
File MER.ros
Problem Montreal Flag of Canada
Employees 54
Shift types 12
Period 6 weeks
Cover type Cover is per time period of the day.
7081 html xml
7213 html xml
7248 html xml
CHILD
File CHILD.ros
Problem Montreal Flag of Canada
Employees 41
Shift types 5
Period 6 weeks
Cover type Cover is per time period of the day.
149 html xml
154 html xml
155 html xml
ERRVH
File ERRVH.ros
Problem Montreal Flag of Canada
Employees 51
Shift types 8
Period 6 weeks
Cover type Cover is per time period of the day.
2001 html xml
2021 html xml
2080 html xml
ERMGH
File ERMGH.ros
Problem Montreal Flag of Canada
Employees 41
Shift types 4
Period 6 weeks
Cover type Cover is per time period of the day.
779 html xml
(bold denotes proven optimal solution)

Other personnel scheduling problem data sets

Problem Cyclical scheduling
Reference Bard, J.F. and H.W. Purnomo. Cyclic Preference Scheduling of Nurses Using A Lagrangian-Based Heuristic. Journal of Scheduling, 2007. 10(1).
Data BardPurnomoJoS_2007_10.zip
Problem Rotating Workforce Scheduling
Reference Musliu, Nysret. Heuristic Methods for Automatic Rotating Workforce Scheduling. International Journal of Computational Intelligence Research, 2006. 2(4): pp. 309-326.
Data http://www.dbai.tuwien.ac.at/staff/musliu/benchmarks/
Problem Shift Design Problem
Reference Nysret Musliu, Andrea Schaerf, and Wolfgang Slany. Local Search for Shift Design. European Journal of Operational Research, 2004. 153(1): pp 51-64.
Data http://www.dbai.tuwien.ac.at/proj/Rota/benchmarks.html
Problem Aggregated Instances
Reference S. van Veldhoven, G. Post, E. van der Veen and T. Curtois. An assessment of a days off decomposition approach to personnel scheduling. Working paper. pdf
Data AggregatedInstances.zip

Contact

Copyright © University of Nottingham