Instant Download

Download your project material immediately after online payment.

Project File Details


3,000.00

100% Money Back Guarantee

File Type: MS Word (DOC) & PDF

File Size:  1,821KB

Number of Pages:54

 

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.

 

 

TABLE OF CONTENTS

Introduction 1
1.1 Research Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 State of the Art 3
2.1 The Timetable Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Genetic Algorithm Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Contribution and Analysis 8
3.1 Theoretical Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.1 Model Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.2 Nature of Search Space . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1.3 Convergence of a GA-based Timetable Search . . . . . . . . . . . . 9
3.1.4 Genetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.1 Serial Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.2 Phase 1: Group Matrix Optimization . . . . . . . . . . . . . . . . . 14
3.2.3 Phase 2: Group-local Timetable Optimization . . . . . . . . . . . . 17
3.2.4 Implementation and Results . . . . . . . . . . . . . . . . . . . . . . 21
3.2.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.6 Parallel/Distributed Algorithm . . . . . . . . . . . . . . . . . . . . 26
4 Conclusion 29
4.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Limitations and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 30
A Algorithms and Sample Output 34
A.1 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
A.2 Output data samples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
A.3 Sample output matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

 

 

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.
2

 

GET THE FULL WORK

DISCLAIMER: All project works, files and documents posted on this website, projects.ng are the property/copyright of their respective owners. They are for research reference/guidance purposes only and the works are crowd-sourced. Please don’t submit someone’s work as your own to avoid plagiarism and its consequences. Most of the project works are provided by the schools' libraries to help in guiding students on their research. Use it as a guidance purpose only and not copy the work word for word (verbatim). If you see your work posted here, and you want it to be removed/credited, please call us on +2348157165603 or send us a mail together with the web address link to the work, to hello@projects.ng. We will reply to and honor every request. Please notice it may take up to 24 or 48 hours to process your request.