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).

• The number of possible days is 7 (from Monday to Sunday), and possible shifts are three (0,1 and 2). Each employee can take 1 shift per day at most.

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/3, length/1

• Output: sched/8

Input format

• Number of employees: n - (employee_no(N).)

• Number of working shifts: m - shifts(M).

• Length of schedule: w - length(W).

• Temporal requirements: matrix R_mw, where each element r_ij of R shows the required number of employees for shift i during day j. This is encoded using matrix/8. Example: the assertion matrix(0,3,3,2,3,3,2,1) means that for shift 0 (first attribute), we require 3 employees on Monday (second attribute) till 1 employee on Sunday (last attribute).

• Maximum and minimum length of periods of consecutive shifts -

  • shift(S). minlenshiftblock(S,Min). maxlenshiftblock(S,Max)., means that employee taking a shift S must carry out the shift S at least for Min consecutive days and for no more than Max consecutive days.

• Maximum and minimum length of blocks of days-off for all employees - (minlendaysoffblock(Min). maxlendaysoffblock(Max).)

• Minimum and maximum length of work blocks (i.e. days of consecutive work, no matter of which shift is taken during the day) - (minlenworkblock(Min). maxlenworkblock(Max).)

• Sequences of shifts not permitted to be assigned to employees (only length 2 and 3 are possible) - e.g. nonseq2(S1,S2). means that an employee cannot take S1 and then S2 the next day. Similarly, the assertion nonseq3(S3,S4,S5). means that no employee can take the sequence of shifts S3,S4 and S5 in three consecutive days.

Output format

• 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. - (sched/8, see example below).

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: First attribute is employee code, the other 7 attributes are shift taken in given workdays
& '-' encoding day off.
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

Notes and Updates

Author(s)

• Author: Nysret Musliu
  • Affiliation: DBAI, Vienna University of Technology, Austria
• Author: Thomas Krennwallner
  • Affiliation: KR, Vienna University of Technology, Austria
• Author: Francesco Calimeri
  • Affiliation: University of Calabria, Italy

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.