Proposed by Sven Löffler, Ilja Becker, Petra Hofstedt

Rotating Rostering Problem

This problem is taken from real life rostering challenges (like nurse rostering). The task is it to find a shift assignment for every employee for every day. A rotation system is used to decrease the size of the problem. Thus, only the rostering for one employee is calculated and all other employees gain a rotated version of the rostering. So Employee 2 has in the first week the rostering of Employee 1 in the second week. Employee 3 has in the first week the rostering of Employee 2 in the second week and Employee 1 in the third week etc. See the following example for 4 employees:

Employee 1	Week 1	Week 2	Week 3	Week 4
Employee 2	Week 2	Week 3	Week 4	Week 1
Employee 3	Week 3	Week 4	Week 1	Week 2
Employee 4	Week 4	Week 1	Week 2	Week 3

Thus, the number of employees is always also the number of weeks. Furthermore, it must be possible to have the shift assignments of the first week (week1) follow after the last week (week4) to create a continuous rolling schedule. Consider that every week in this example represents the shift assignment for 7 days, for example: week1 = Night, Day Off, Day Off, Day Off, Early, Early, Early. Thus, the resulting rostering can be read in two ways. Reading a line shows the rostering for one employee for all weeks. Reading a column (meaning a day of the week) shows the rostering for all employees for one day. Further details and restrictions follow below.

Definitions and restrictions

• let $w$ in N be the number of weeks (and also the number of employees) we’re planning for
  • ..be $x_1$ to $x_{(w*7)}$ the variables for the CSP, i.e. the days
• there are 4 possible shifts: early = 1, late = 2 and night shift = 3 and day off (rest day) = 0
  • ..resulting in the domains $D_1 = D_2 = … = D_{(w*7)} = {0,1,2,3}$
• $C_{shiftRequirements}$: for every weekday for each shift the number of required staff is provided (e.g. usually less staff is required on the weekend) see an example staff requirement matrix $M$ below
• $C_{shiftRepetitions}$: for every shift type a maximum number of consecutive assignments to this shift is given to comply with work regulations, e.g. we restrict the general number of repetitions to $s_{max} = 4$. A number of minimal consecutive assignments is given as well to comply with work regulations, e.g. we demand at least two days in a row with the same shift $s_{min} = 2$
• $C_{shiftOrder}$: restricts the order of shifts. There is a forward rotating principle. This means, that after an early shift there can only follow a shift with the same or a higher value, or a rest shift (day off).
• $C_{equalDays}$: constrains that weekend days (Saturday and Sunday) always have the same shift
• $C_{restDays}$: at least 2 days must be rest days every 14 days.

These restrictions are either based on regulations or academic findings on good work practices.

A rostering instance can be described by Rostering-w-M-$s_{min}$-$s_{max}$, where

• $w$ is the number of weeks
• $M$ is a 4 times 7 matrix, including at $M_{i,j}$ the needed employees for shift (i-1) and day j (shift types are 0-indexed, the matrix M is 1-indexed)
• $s_{min}$ is the minimum number of days in a row with the same shift
• $s_{max}$ is the maximum number of days in a row with the same shift

The following CSP $P = (X, D, C)$ can describe the problem:

• variables $X = \{x_{1}, …, x_{w * 7} \}$ ($w * 7$ variables for the days)

  • $X$ is also represented by a matrix $X^{2d}$ with matrix elements $X^{2d}_{i,j} = x_{(i-1)*7+j}, i \in \{1,…,w\}, j \in \{1,…,7\}$.

• domains $D = \{D_{1}, …, D_{w * 7} \ | \ D_1 = … = D_{w * 7} = \{0,1,2,3\}\}$ ($3+1$ different shifts)

• constraints $C$ is the conjunction of:

  • $\{global\_cardinality(\{(X_{1,i}^{2d}, X_{2,i}^{2d}, …, X_{w,i}^{2d}\}, \{(0,M_{1,i}),(1,M_{2,i}),(2,M_{3,i}),(3,M_{4,i})\}) \;\;\; | \;\;\; \forall i \in \{1,…,7\} \}$ $(C_{shiftRequirements})$
  • $\{X^{2d}_{j,7-1} = X^{2d}_{j,7} \;\;\; | \;\;\; \forall j \in \{1,…,w\}\}$ $(C_{equalDays})$
  • $\{ (x_i \neq x_{(i+1)_{mod}}) \rightarrow all\_equal(\{x_i, x_{(i-1)_{mod}}, …, x_{(i-s_{min}+1)_{mod}}\}) \;\;\; | \;\;\; \forall i \in \{1,…,w * 7\}\}$ $(C_{shiftRepetitions\ 1})$
  • $\{all\_equal(x_i, x_{(i+1)_{mod}}, x_{(i+2)_{mod}}, … , x_{(i+s_{max}-1)_{mod}}) \rightarrow (x_i \neq x_{(i+s_{max})_{mod}}) \;\;\; | \;\;\; \forall i \in \{1, …, w * 7\}\}$ $(C_{shiftRepetitions\ 2})$
  • $\{(x_i \leq x_{(i+1)_{mod}}) \vee (x_{(i+1)_{mod}} = 0) \;\;\; | \;\;\; \forall i \in \{1,…,w * 7\}\}$ $(C_{shiftOrder})$
  • $\{count(0,\{x_{i}, x_{(i+1)_{mod}}, …, x_{(i+2 * 7)_{mod}}\},\geq,2) \;\;\; | \;\;\; \forall i \in \{1,…,w * 7\}\}$ $(C_{restDays})$

where “$i_{mod}$” stands for “$(i\ mod\ (w * 7)) + 1$” and allows to describe a continuous schedule

and with an example staff requirement table like M:

Shift / Day	Mo	Tu	We	Th	Fr	Sa	Su
Day Off	2	2	2	2	2	4	4
Early	2	2	2	2	2	2	2
Late	2	2	2	2	2	1	1
Night	2	2	2	2	2	1	1

This represents an instance that covers 8 weeks with 8 employees, as can be calculated from the assignments to the shifts in M.