TECHNICAL REPORT

Computational results on new staff scheduling benchmark instances
Tim Curtois, Rong Qu
ASAP Research Group, School of Computer Science, University of Nottingham, NG8 1BB, Nottingham, UK
First published online: 19-Sep-2014, last updated: 06-Oct-2014.

This report lists results of applying the algorithms presented in [2] to the staff scheduling problem
benchmark instances 1..24 [3]. The algorithms are an ejection chain metaheuristic and a branch andprice method. The branch and price method was shown to be very effective on smaller and medium
sized instances, often finding the optimal solution. Its weakness is on the larger instances on which it
may run out of memory trying to solve a sub-problem. The metaheuristic is a more robust andpractical method. Although it is outperformed on the smaller instances, it will still find good solutions
on the larger instances if given sufficient time. For additional comparisons we have also included theresults of applying Gurobi 5.6.3 [1] to an integer programming formulation.

Instances
Many of the original benchmark instances available at [3] can now be easily solved [2]. Most of theoriginal instances are also quite difficult to use due to their real world nature. They contain manydifferent types of constraints and objectives which are complicated to model and implement whatever
type of solving approach is being used (integer programming, metaheuristic, etc). For these reasonsthe collection of instances has been recently supplemented with a new set of instances. The newinstances are designed to reflect real world requirements and scheduling scenarios yet still be easy touse. They are also designed to represent a range of difficulty: from very easy to very challenging. To
make them easier to use and test, the number of constraint and objective types has been reduced to acore of constraints found commonly in staff rostering problems. The new instances are also given in aplain text format which is a lot simpler to parse and use. This allows researchers to spend less time
writing code for parsing the instances and more time on developing the algorithms and producing
results. Table 1 lists the instances and their dimensions. They range from very small (8 staff, 2 weeks,1 shift type) to very large (150 staff, 52 weeks, 32 shift types).

Instance
Instance1
Instance2
Instance3
Instance4
Instance5
Instance6
Instance7
Instance8
Instance9
Instance10
Instance11
Instance12

Planninghorizon(weeks)222444444444

Staff
81420
1016182030
3640
50
60

Shifttypes
1232233445610

Instance13
Instance14
Instance15
Instance16
Instance17
Instance18
Instance19
Instance20
Instance21
Instance22
Instance23
Instance244668812122626
52
5252

120
32
45
20
32
2240
50
100
50
100
150

1846343568101632

Table 1 Benchmark instances

Integer Programming FormulationAn integer programming model for the problem is given below. All instances start on a Monday andthe planning horizon h is always a whole number of weeks (h mod 7 = 0).
Parameters:I

set of employees.

hnumber of days in the planning horizon.

D

set of days in the planning horizon = {1…h}.

W

set of weekends in the planning horizon = {1...h/7}.

T

set of shift types.

Rt

set of shift types that cannot be assigned immediately after shift type t.

Ni

set of days that employee i cannot be assigned a shift on.

ltlength of shift type t in minutes.

mitmax maximum number of shifts of type t that can be assigned to employee i.
biminminimum number of minutes that employee i must be assigned.

bimax

maximum number of minutes that employee i can be assigned.

cimin

minimum number of consecutive shifts that employee i must work.

cimin

maximum number of consecutive shifts that employee i can work.

oimin

minimum number of consecutive days off that employee i can be assigned.

aimax

maximum number of weekends that employee i can work.

qidtpenalty if shift type t is not assigned to employee i on day d.

pidt

penalty if shift type t is assigned to employee i on day d.

udt

preferred total number of employees assigned shift type t on day d.

vdtminweight if below the preferred cover for shift type t on day d.

vdtmax

weight if exceeding the preferred cover for shift type t on day d.

Decision variables:
xidt

1 if employee i is assigned shift type t on day d, 0 otherwise

kiw

1 if employee i works on weekend w, 0 otherwiseydt

total below the preferred cover for shift type t on day d.

zdt

total above the preferred cover for shift type t on day d.

Constraints:
1. An employee cannot be assigned more than one shift on a single day.

∑ x ≤ 1,∀i ∈ I , d ∈ D

idt

t ∈T

2. Shift rotation. A minimum amount of rest is required after each shift. Therefore certain shifts
cannot follow others. For example, an early shift cannot follow a late shift.

xidt + xi ( d +1)u ≤ 1,

∀i ∈ I , d ∈ {1...h − 1}, t ∈ T , u ∈ Rt

3. The maximum numbers of shifts of each type that can be assigned to employees. For example,
some employees will have contracts which do not allow them to work night shifts or only a maximum
number of night shifts.

∑x ≤ md∈Dmax
itidt,∀i ∈ I , t ∈ T

4. Minimum and maximum work time. The total minutes worked by each employee must be between
a minimum and maximum. These limits can vary depending on whether the employee is full-time orpart-time.

bimin ≤ ∑∑ lt xidt ≤ bimax ,∀i ∈ Id∈D t∈T

5. Maximum consecutive shifts. The maximum number of shifts an employee can work without a dayoff. For example, part-time employees sometimes do not work as many consecutive shifts as full-time
staff.
d + c imax∑∑ x ≤ cj = d t∈T

ijt

max
i,

∀i ∈ I , d ∈ {1...h − cimax }6. Minimum consecutive shifts. This can be modelled by preventing every sequence of consecutive
shifts below the minimum. For example, if the minimum number of consecutive shifts is four then wemust not allow any of the sequences: {off-on-off, off-on-on-off, off-on-on-on-off} where off is a day
without a shift and on is a day with a shift assigned.
d +s


 + ∑ x i ( d + s +1) t > 0,x+s−x
∑
∑
∑
idt
ijt

t∈T
j=
d+t
∈
T1
 t∈T∀i ∈ I , s ∈{1...c imin − 1}, d ∈{1...h − ( s + 1)}

7. Minimum consecutive days off. This can be modelled in a similar way to the minimum consecutive
shifts constraint. For example, if the minimum number of consecutive days off is three then we must
not allow any of the sequences: {on-off-on, on-off-off-on}.

 d +s1 − ∑ x idt  + ∑ ∑ x ijt + 1 − ∑ x i ( d + s +1) t  > 0, t∈T j = d +1 t∈T t∈T∀i ∈ I , s ∈ {1...oimin − 1}, d ∈ {1...h − ( s + 1)}

8. Maximum number of weekends. A weekend is considered as being worked if the employee has ashift on the Saturday or the Sunday.

kiw ≤ ∑ xi ( 7 w−1) t + ∑ xi ( 7 w ) t ≤ 2kiw ,t∈T∀i ∈ I , w ∈ Wt∈T∑k ≤ aw∈Wmaxiiw,∀i ∈ I9. Days off. These are days that employees cannot work because, for example, they are on vacation.

xidt = 0,∀i ∈ I , d ∈ N i , t ∈ T

10. Cover requirements.

∑x −z + y =u ,i∈Iidt

dtdtdt∀d ∈ D, t ∈ T

Objective function:

Minimise∑ ∑∑ qidt (1 − xidt ) + ∑ ∑∑ pidt xidt + ∑∑ ydt vdtmin + ∑∑ z dt vdtmaxi∈I d∈D t∈Ti∈I d∈D t∈Td∈D t∈Td∈D t∈TThe objective function models the requirement to maximise the allocation of employee shift requests
and minimise under and over staffing. The parameters qidt and pidt are the weights for shift on and shift
off requests respectively. For example, an employee may request to work a certain shift type on aparticular day. The higher the weight, the more important the request is to the employee. If there is norequest then the parameter has the value zero.
The variables ydt and zdt are the total numbers of staff below and above the preferred cover level forminmax

each shift type t on each day d. The parameters vdt and vdt are weights to represent the importanceof minimising under and over coverage.

ResultsTo provide other researchers with results to compare against, we have used the two existingalgorithms presented in [2] and Gurobi 5.6.3 [1] and applied them to the new instances.
All the experiments were performed on Intel Core 2 Duo 3.16GHz, 8GB ram. The Gurobi solver waslimited to a single thread and a maximum time of 1 hour. Table 2. lists the results. Known optimal
solutions are in bold.Ejection chain
Instance
Instance1
Instance2
Instance3
Instance4
Instance5
Instance6
Instance7
Instance8
Instance9
Instance10
Instance11
Instance12
Instance13
Instance14
Instance15
Instance16
Instance17
Instance18
Instance19
Instance20
Instance21
Instance22
Instance23
Instance24

Branch and Price

Gurobi 5.6.3

Weeks Staff Shifts 10 min 60 min
LB
Sol. Time (s)
LB
28
1558
0.27
607
607
607
607
2 142923
837
828
0.13828
828
2 20
31003
1003
1001 1001
0.45
1001
4 1021719
1718
1716 1716
1.50
1716
4 1621439
1358
1141 1160
25.611143
4 1832344
2258
1949 1952
10.46
1950
4 20
312841269
1055 1058
93.73
1056
4 3042529
2260
1297 1308 11831.06
1281
4 364474
463
406
439
76.99
247
4 4054999
4797
4631 4631
113.44
4631
4 50
63967
3661
3443 3443
19.11
3443
4 60
1056115211
4040 4046
1336.44040
4 120
1887073037 Out of memory1346
6 3242542
1847 Out of memory
1277
6 45
66049
5935 Out of memory3806
8 2034343
4048
3224 3323
265.02
3211
8 32
47835
7835 Out of memory5726
12 2236404
6404 Out of memory4351
12 4056522
5531 Out of memory2945
26 50
6 235319750 Out of memory4743
26 1008 38294 36688 Out of memory
20868
52 50
10- 516686 Out of memory
52 100
16- 54384 Out of memory
52 15032- 156858 Out of memory- Out of memory

Sol. Time (s)
1.62
607
5.22
828
13.54
1001
1716 158.99
1143 1520.24
1950 440.93
1056 2152.48
1323 3599.83
439 3599.85
4631 244.20
3443 109.92
4040 2303.84
3109 3600.55
1280 3600.13
4964 3600.00
3233 3599.99
5851 3600.00
4760 3599.99
5420 3605.90- 3600.05- 3600.21- 3600.19- 3600.43-Table 2. Results

References
1.
2.
3.

Gurobi Optimization, Inc. Gurobi Optimizer Reference Manual. 2014; Available from:http://www.gurobi.com.
E.K. Burke and T. Curtois, New Approaches to Nurse Rostering Benchmark Instances,
European Journal of Operational Research 237(1) (2014) 71–81.
T. Curtois. Employee Shift Scheduling Benchmark Data Sets. 2014; Available from:www.cs.nott.ac.uk/~tec/NRP.