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/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 -
(% ShiftName, MinlengthOfBlocks, MaxLengthOfBlocks
shift(S). minlenshiftblock(S,Min). maxlenshiftblock(S,Max).)
Maximum and minimum length of blocks of days-off - (minlendaysoffblock(Min). maxlendaysoffblock(Max).)
Minimum and maximum length of work blocks - (minlenworkblock(Min). maxlenworkblock(Max).)
Sequences of shifts not permitted to be assigned to employees (only length 2 and 3 are possible) - (nonseq2(S1,S2). nonseq3(S1,S2,S3).)
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: 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
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):8598, 2002.
[2] G. Laporte and G. Pesant. A general multi-shift scheduling system. Journal of the Operational Research Society, 55/11:12081217, 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.