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

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

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

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.