GENETIC ALGORITHMS FOR TIMETABLE GENERATION

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 fulfill 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 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 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)

Department: Computer Science (M.Sc Thesis)

Format: MS Word

Chapters: 1 - 5, Preliminary Pages, Abstract, References, Appendix.

No. of Pages: 54

Price: 20,000 NGN

In Stock

Buy Now

Our Customers are Happy!!!

See What Some of Our Customers are Saying About Us