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:

• Sequences of shifts not permitted to be assigned to employees. For example, one such sequence is “3 1$ (Night Day): after working in the night shift, it is not allowed to work the next day in the day shift.
• Maximum and minimum length of periods of consecutive shifts
• Maximum and minimum length of blocks of days-off
• Maximum and minimum length of blocks of workdays. A Work block is a sequence consisting only from the working shifts (without day-off in between).

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

Predicates

• Input: employee_no/1, shifts/1, matrix/8, shift/1, minlenshiftblock/2, maxlenshiftblock/2, minlendaysoffblock/1, maxlendaysoffblock/1, minlenworkblock/1, maxlenworkblock/1, nonseq2/2, nonseq3/2

• Output: sched/8

Input format

• Number of employees: n
• Number of working shifts: m
• Length of schedule: w
• A cyclic schedule is represented by a matrix S_nw. Each element s_ij of matrix S corresponds to one shift or day off. Element s_ij shows on which shift employee i works during day j or whether the employee has time off. In a cyclic schedule, the schedule for one employee consists of a sequence of all rows of the matrix S. The last element of a row is adjacent to the first element of the next row, and the last element of the matrix is adjacent to its first element.
• Temporal requirements: matrix R_mw, where each element r_ij of R shows the required number of employees for shift i during day j.

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(0,2,2,2,2,2,2,2). matrix(1,2,2,2,3,3,3,2). matrix(2,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).

The output of the solver should look like:

% sched/8 matrix is output: employee_no x length
sched(0, -, 2, 2, 2, 2, 2, 3). sched(1, 3, -, -, 2, 2, 2, 2). sched(2, 2, 3, 3, -, -, 1, 1). 
sched(3, 1, 1, 1, 3, 3, -, -). sched(4, -, 1, 1, 2, 2, 3, 3). sched(5, 3, -, -, 1, 1, 2, 2). 
sched(6, -, -, -, 1, 1, 1, 1). sched(7, 1, 3, 3, -, -, -, -). sched(8, 2, 2, 2, 3, 3, 3, -).

Problem Peculiarities

Type: Search Competition: Both

Problems 1-3 appeared previously in the literature and have been solved by constraint programming based approaches (see [2], [1]). Instances 4-20 are real life problems which have been created from shifts and temporal requirements which appeared in a broad range of organizations, like airports, factories, health care organizations, etc. (see [4]). These instances have been solved by heuristic methods presented in [4] and some of them have been solved by constraint programming based approaches presented in [1] and [3]. Problems 21-100 are generated randomly for this competition. The heuristic solver presented in [4] solves each of these instances within few seconds.

Notes and Updates

Author(s)

• Author: Nysret Musliu
  • Affiliation: DBAI, Vienna University of Technology, Austria

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.