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

- MIN s and MAX s : Each element of these vectors shows, respectively, the

required minimal and permitted maximal length of periods of consecutive
shifts of the same type.

- MIN w and MAX w : Minimal and maximal length of blocks of consecutive

work shifts. This constraint limits the number of consecutive days on which
the employees can work without having a day off.

The task in rotating workforce scheduling is to construct a cyclic schedule ,which
we represent as an n×w matrix S n,w ∈ A∪{ day-off } .Eachelement S i,j denotes

the shift that employee , or whether the employee has

time off. In a cyclic schedule, the scheduleforoneemployeeconsistsofasequence
of all rows of the matrix

i is assigned during day j

.
The task is called rotating or cyclic scheduling because the last element of
each row is adjacent to the first element of the next row, and the last element of
the matrix is adjacent to its first element. Intuitively, this means that employee

S

i

( i<n ) assumes the place (and thus the schedule) of employee i + 1 after each

week, and employee assumes the place of employee 1. This cyclicity must be

taken into account for the last three constraints above.
In the present paper, we consider the generation of a single schedule that
satisfies all the hard constraints given in the problem definition. Fulfilling all
these constraints is usually sucient in practice. The same constraints that we
use in this paper are used in the commercial software FCS for generating rotating
workforce schedules. This system has been used since 2000 in practice for many
companies in Europe and the scheduling variant we discuss in this paper proved
to be sucient for a broad range of uses. However, FCS has several shortcomings
that led us to consider constraint programming as an alternative approach. We
discuss these shortcomings and their remedies with CP-Rota in the next section.

n

4 Shortcomings of FCS and Their Remedies in CP-Rota

Although FCS has been in commercial use since 2000 in several companies and
proved to be an acceptable solution for many applications in practice, it has
several disadvantages that hinder its further development:

- Thecodebaseof FCS has gotten quite large and hard to maintain. This

makes user modifications dicult and error-prone. New scheduling ideas
cannot be rapidly prototyped but require substantial development effort.

-

FCS was implemented in Visual Basic and thus depends on essentially a sin-
gle supported language implementation, which is in addition also not freely
available. This complicates the sharing of code with other researchers and
practitioners for joint development and turns every mistake in the language
implementation into a potentially show-stopping problem.

- From [10], it is known that local search approaches - although incomplete -

can significantly outperform FCS on some instances. Clearly, it is highly
desirable to improve the running times of FCS to more closely match such
competing approaches while retaining the completeness of the search.