ABSTRACT
Timetabling presents an NP-hard combinatorial optimization problem which requires
an efficient search algorithm. This research aims at designing a genetic algorithm for
timetabling real-world school resources to fulfil a given set of constraints and preferences.
It further aims at proposing a parallel algorithm that is envisaged to speed up convergence
to an optimal solution, given its existence. The timetable problem is modeled as a constraint
satisfaction problem (CSP) and a theoretical framework is proposed, which guides
the approach used to formulate the algorithm. The constraints are expressed mathematically
and a conventional algorithm is designed that evaluates solution fitness based on
these constraints. Test results based on a subset of real-world, working data indicate that
convergence on a feasible (and optimal/Pareto) solution is possible within the search space
presented by the given resources and constraints. The algorithm also degrades gracefully
to a workable timetable if an optimal one is not located. Further, a SIMD-based parallel
algorithm is proposed that has the potential to speed up convergence on multi-processor
or distributed platforms.
CHAPTER ONE
Introduction
1.1 Research Context
Timetabling is a well known NP-Hard combinatorial optimization problem that has not
yet been solved in polynomial time using a deterministic algorithm. Several techniques are
used to solve the timetabling problem including manual construction, search heuristics
(tabu search, simulated annealing and genetic algorithms), neural networks and graph
colouring algorithms. Most timetabling problems have application specific peculiarities
and hence, the use of domain-specific patterns together with most of the aforementioned
techniques to improve computational efficiency is not uncommon (see [9], [18]).
However, despite the considerable success of the aforementioned techniques, the timetabling
problem still remains a challenge especially when dealing with large data sets with many
constraints. This research investigates the suitability of using genetic algorithms (GAs)
to locate an optimal school timetable in a large search space. Our work is set apart from
previous studies by the prior development of a theoretical framework as a basis for convergence
of the proposed algorithm. In addition, our investigation targets real-time data
sets governed by potentially conflicting constraints, a goal that is seldom seen in most
similar past research efforts. In particular, the work endeavours to achieve the following
objectives:
1. Explore a theoretical framework for using GAs for timetable construction
2. Design and prototype a genetic algorithm to solve the timetabling problem and test
it using a trial dataset
3. Propose a distributed timetabling GA based on the results of objective (2)
1
1.2 Methodology
The research sets out by modeling the timetable problem and proposing a theoretical
framework as a basis for the convergence of the proposed algorithm. Secondly, a serial
algorithm is designed and prototyped to furnish a timetable from a subset of real-world
university student data with the aim of investigating the effects of various parameters on
its convergence behaviour. This is followed by application of the algorithm to a bigger
data set to investigate its scalability properties. Finally, a parallel/distributed GA is
proposed with the goal of exploiting current distributed/parallel architectures to enhance
performance when applied to real-world data sets.
The rest of this paper is organised as follows: The next section (2) briefly introduces
critical timetable and GA concepts with the aim of laying a foundation for understanding
subsequent discussion. The section also includes a review and analysis of literature on GAbased
scheduling algorithms and heuristics. The analysis relates the proposed research
topic to the state of the art and endeavours to situate it in the context of already existing
work. Section 3 documents and discusses the theoretical framework and the proposed
genetic algorithm and analyses the results obtained from the prototype and a test data
set. The section concludes with details of the proposed distributed genetic algorithm.
Finally, Section 4 summarizes the results of the analysis, explores the limitations of the
algorithm and suggests directions for future work.
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
