Information Technology Reference
In-Depth Information
A Constraint Programming Application for
Rotating Workforce Scheduling
Markus Triska and Nysret Musliu
Database and Artificial Intelligence Group
Vienna University of Technology
{
triska,musliu
}
@
dbai.tuwien.ac.at
Abstract.
We describe
CP-Rota
, a new constraint programming appli-
cation for rotating workforce scheduling that is currently being developed
at our institute to solve real-life problems from industry. It is intended
to complement
FCS
, a previously developed application. The advantages
of
CP-Rota
over
FCS
are a significantly smaller and more maintainable
code base, portability across a range of different language implemen-
tations and a more declarative approach that makes extensions easier
and mistakes less likely. Our benchmarks show that
CP-Rota
is already
competitive with
FCS
and even outperforms it on several hard real-life
instances from the literature.
Keywords:
Staff Scheduling, Cyclic Schedule, Manpower Scheduling,
Timetabling.
1
Introduction
Computerized workforce scheduling has interested researchers for over 30 years.
To solve rotating workforce scheduling problems, different approaches have been
used in the literature, including exhaustive enumeration ([5], [2]), constraint
(logic) programming, genetic algorithms ([8]) and local search methods.
In the present paper, we describe
CP-Rota
, a new constraint application for
rotating workforce scheduling that is currently being developed at our institute
to solve real-life problems from industry. It is intended to complement
FCS
,a
previously developed application that is currently commercially used in many
companies in Europe.
CP-Rota
builds upon, contributes to and improves previ-
ous constraint programming approaches to rotating workforce scheduling in the
following ways:
-
CP-Rota
is written in portable Prolog and will eventually be released under
a permissive licence to benefit both researchers and practitioners. Much of
its code is already available on request at the time of publication.
-
CP-Rota
implements new allocation strategies (available as options for users
to choose) that we discovered and discuss in this paper, which yield signifi-
cantly improved performance on some real-life instances.
-
Our benchmarks on real-life instances show the tremendous potential of con-
straint programming in rotating workforce scheduling, also and especially
due to using different language implementations where they excel.
Search WWH ::
Custom Search