= 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 might be {{{3,1}}}: after a day spent on shift {{{3}}}, it is not allowed to take the shift {{{1}}} the day after, for any employee.
 * 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). 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).}}}, fixed to 7.
 * 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(1,3,3,2,3,3,2,1)}}} means that for shift {{{1}}} (first attribute), we require {{{3}}} employees on Monday (second attribute), {{{3}}} employeess on Tuesday (third attribute), and so on until {{{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 any employee taking 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 any employee - ( {{{minlendaysoffblock(Min). maxlendaysoffblock(Max).}}} )
 * Minimum and maximum length of work blocks for any employee, i.e. days of consecutive work, no matter the shifts taken) - ({{{minlenworkblock(Min). maxlenworkblock(Max).}}})
 * Sequences of shifts not permitted to be assigned to any employee (only length 2 and 3 are possible) - {{{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(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

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