A Constraint Programming Application for Rotating Workforce Scheduling - Developing Concepts in Applied Intelligence - page 83

2 Related Work

Many different approaches for solving rotating workforce instances are docu-
mented in the literature. Balakrishnan and Wong [1] solved a problem of rotating
workforce scheduling by modeling it as a network flow problem. Laporte [6] con-
sidered developing the rotating workforce schedules by hand and showed how the
constraints can be relaxed to get acceptable schedules. Musliu et al. [9] proposed
and implemented a method for the generation of rotating workforce schedules,
which is based on pruning the search space by involving the decision maker dur-
ing the generation of partial solutions. The algorithms have been included in
a commercial product called First Class Scheduler (FCS) [4], which is used by
many companies in Europe. In [10], Musliu applied a min-conflicts heuristic in
combination with tabu search. Although this yields good performance on many
instances, the resulting search method is incomplete and its results are there-
fore not directly comparable with FCS. This paper also introduced 20 real-life
problems collected from different areas in industry and the literature. 1
The use of constraint logic programming for rotating workforce scheduling was
first shown by Chan in [3]. Recently, Laporte and Pesant [7] have also proposed
a constraint programming algorithm for solving rotating workforce scheduling
problems, implemented in ILOG and requiring custom extensions.

3 The Rotating Workforce Scheduling Problem

With CP-Rota and in the present paper, we focus on a specific variant of a
general workforce-scheduling problem, which we formally define in this section.
The following definition is from [9] and proved to be able to satisfactorily handle
a broad range of real-life scheduling instances in commercial settings. A rotating
workforce scheduling instance as discussed in the present paper consists of:

- n : Number of employees.

- A m a 1 , a 2 , ..., a m .

:Setof shifts (activities) :

- w = 7, to assign one shift type

for each day of the week to each employee. The total length of a planning
period is

: Length of the schedule. A typical value is w

n × w due to the schedule's cyclicity as discussed below.

- R R i,j

shows the required number of employees that need to be assigned shift type

: Temporal requirements matrix, an m×w -matrix where each element

i

during day j .Thenumber o j of day-off “shifts” for a specific day j is implicit

n − i =1 R i,j . in the requirements and can be computed as o j =

- Sequences of shifts not permitted to be assigned to employees. For example,

one such sequence might be

ND

(Night Day): after working in the night shift,
it is not allowed to work the next day in the day shift. A typical rotating
workforce instance forbids several shift sequences, often due to legal reasons
and safety concerns.

1 Examples available from http://www.dbai.tuwien.ac.at/staff/musliu/benchmarks/