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