= 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

## 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
 * 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.