GENETIC ALGORITHMS FOR TIMETABLE GENERATION

For more Computer Science projects click here


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


For more Computer Science projects click here
___________________________________________________________________________
This is a Postgraduate Thesis and the complete research material plus questionnaire and references can be obtained at an affordable price of N3,000 within Nigeria or its equivalent in other currencies.


INSTRUCTION ON HOW TO GET THE COMPLETE PROJECT MATERIAL

Kindly pay/transfer a total sum of N3,000 into any of our Bank Accounts listed below:
·         Diamond Bank Account:
A/C Name:      Haastrup Francis
A/C No.:         0096144450

·         GTBank Account:
A/C Name:      Haastrup Francis
A/C No.:         0029938679

After payment, send your desired Project Topic, Depositor’s Name, and your Active E-Mail Address to which the material would be sent for downloading (you can request for a downloading link if you don’t have an active email address) to +2348074521866 or +2348066484965. You can as well give us a direct phone call if you wish to. Projects materials are sent in Microsoft format to your mail within 30 Minutes once payment is confirmed. 

--------------------------------------------------------
N/B:    By ordering for our material means you have read and accepted our Terms and Conditions


Terms of Use: This is an academic paper. Students should NOT copy our materials word to word, as we DO NOT encourage Plagiarism. Only use as guide in developing your original research work.

Delivery Assurance
We are trustworthy and can never SCAM you. Our success story is based on the love and fear for God plus constant referrals from our clients who have benefited from our site. We deliver project materials to your Email address within 15-30 Minutes depending on how fast your payment is acknowledged by us.

Quality Assurance
All research projects, Research Term Papers and Essays on this site are well researched, supervised and approved by lecturers who are intellectuals in their various fields of study.
Share:

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.

Search for your topic here

See full list of Project Topics under your Department Here!

Featured Post

Article: How to Write a Research Proposal

Most students and beginning researchers do not fully understand what a research proposal means, nor do they understand ...

Popular Posts