Rotating Workforce Scheduling

Problem Description

Workforce scheduling, in general, includes hard sub-problems which appear in many spheres of life as in industrial plants, hospitals, public transport, airlines companies etc. There are two main variants of workforce schedules: rotating (or cyclic) workforce schedules and non-cyclic workforce schedules.

In a rotating workforce schedule all employees have the same basic schedule but start with different offsets. The definition of problem is given below (see [1]).

Input consists of the number of employees, the number of working shifts, the length of schedule, a cyclic schedule, and the temporal requirements.

Constraints:

Problem: Find a cyclic schedule (assignment of shifts to employees) that satisfies the requirement matrix, and all other constraints.

Predicates

Input format

Output format

Example(s)

A possible input is as follows:

% Length of the schedule is fixed to 7-day week
length(7).

% Number of Employees is variable
employee_no(9).

% Number of Shifts is variable
shifts(3).

% Temporal Requirements Matrix
matrix(1,2,2,2,2,2,2,2). 
matrix(2,2,2,2,3,3,3,2). 
matrix(3,2,2,2,2,2,2,2).

% ShiftName, MinlengthOfBlocks, MaxLengthOfBlocks
shift(1). minlenshiftblock(1,2). maxlenshiftblock(1,7).
shift(2). minlenshiftblock(2,2). maxlenshiftblock(2,6).
shift(3). minlenshiftblock(3,2). maxlenshiftblock(3,4).

% Minimum and maximum length of days-off blocks
minlendaysoffblock(2). maxlendaysoffblock(4).

% Minimum and maximum length of work blocks
minlenworkblock(4). maxlenworkblock(7).

% Not allowed shift sequences (only length 2 and 3 are possible)

% Not allowed shift sequences of length 2
nonseq2(3,1). nonseq2(3,2). nonseq2(2,1).

% Not allowed shift sequences of length 3
% (empty for this instance)

The output of the solver should look like:

% sched/8 matrix is output: employee_no x length -- First attribute is employee code, the other 7 attributes are shift taken in given workdays - '0' encodes day off.
sched(0, 0, 2, 2, 2, 2, 2, 3). 
sched(1, 3, 0, 0, 2, 2, 2, 2). 
sched(2, 2, 3, 3, 0, 0, 1, 1). 
sched(3, 1, 1, 1, 3, 3, 0, 0). 
sched(4, 0, 1, 1, 2, 2, 3, 3). 
sched(5, 3, 0, 0, 1, 1, 2, 2). 
sched(6, 0, 0, 0, 1, 1, 1, 1). 
sched(7, 1, 3, 3, 0, 0, 0, 0). 
sched(8, 2, 2, 2, 3, 3, 3, 0).

Problem Peculiarities

Type: Search Competition: Both

Notes and Updates

Author(s)

References

[1] N. Musliu, J. Gaertner, and W. Slany. Efficient generation of rotating workforce schedules. Discrete Applied Mathematics, 118(1-2):85–98, 2002.

[2] G. Laporte and G. Pesant. A general multi-shift scheduling system. Journal of the Operational Research Society, 55/11:1208–1217, 2004.

[3] M. Triska, N. Musliu. A Constraint Programming Application for Rotating Workforce Scheduling. IEA/AIE 2011, Studies in Computational Intelligence, Volume 363, Springer 2011.

[4] Nysret Musliu. Heuristic Methods for Automatic Rotating Workforce Scheduling. International Journal of Computational Intelligence Research, Volume 2, Issue 4, pp. 309-326, 2006.