= 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)
}}}

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' encoding 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.