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 con-straint satisfaction problem (CSP) and a theoretical framework is proposed, which guides the approach used to formulate the algorithm. The constraints are expressed mathemat-ically 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
CHAPTER ONE
1 Introduction
1.1 Research Context
1.2 Methodology
CHAPTER TWO
2 State of the Art
2.1 The Timetable Problem
2.2 Genetic Algorithm Concepts
2.3 Literature Review
CHAPTER THREE
3 Contribution and Analysis
3.1 Theoretical Framework
3.1.1 Model Formulation
3.1.2 Nature of Search Space
3.1.3 Convergence of a GA-based Timetable Search
3.1.4 Genetic Operators
3.2 Proposed Algorithm
3.2.1 Serial Algorithm Overview
3.2.2 Phase 1: Group Matrix Optimization
3.2.3 Phase 2: Group-local Timetable Optimization
3.2.4 Implementation and Results
3.2.5 Performance Analysis
3.2.6 Parallel/Distributed Algorithm
CHAPTER FOUR
4 Conclusion
4.1 Summary
4.2 Limitations and Future Work
A Algorithms and Sample Output
A.1 Pseudocode
A.2 Output data samples
A.3 Sample output matrices
Chapter 1
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 con-vergence 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.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 GA-based 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....
================================================================
Item Type: Project Material | Size: 51 pages | Chapters: 1-5
Format: MS Word | Delivery: Within 30Mins.
================================================================
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.