dc.description.abstract | The International Timetabling Competition (ITC) has a long tradition of arranging
scientific competitions within the research area of timetabling and its applications. The
2020-2021 edition is devoted to sports timetabling. The aim of ITC 2021 is to stimulate
the development of solution approaches for the construction of round-robin timetables,
meaning that each team plays every other team a fixed number of times. Each instance
consists of a time-constrained double round-robin tournament. Further, the competition
considers two types of constraints: hard constraints represent fundamental properties of
the timetable that can never be violated, while soft constraints represent conditions that
are desirable to satisfy. The resulting problem is to find a timetable the penalties from
violated soft constraints.
In this thesis, we present a heuristic solution approach using a combination of Mixed-
Integer Linear Programming (MILP) and cluster patterns for generating timetables in
sports tournaments. Further, we examine how our solution approach perform on 45
experimental problem instances presented in the ITC 2021.
To the best of out knowledge, this is the first time a approach including clusters patterns,
has been tested on an experimental database.
The computational results show that our solution method is capable of generating a double
round robin timetable for most of the data instances. Further, it provides better results
in a shorter amount of time when compared to running the default MILP model. | en_US |