GENETIC ALGORITHMS FOR TIMETABLE GENERATION
Need help with a related project topic or New topic? Send Us Your Topic
DOWNLOAD THE COMPLETE PROJECT MATERIAL
GENETIC ALGORITHMS FOR TIMETABLE GENERATION
CHAPTER ONE: Introduction
1.1 Background of the study
Timetabling is a well-known NP-Hard combinatorial optimisation issue that has yet to be solved in polynomial time using deterministic algorithms.
Timetabling can be solved via manual building, search heuristics (e.g. tabu search, simulated annealing, evolutionary algorithms), neural networks, and graph colouring methods. To increase computing efficiency in timetabling problems, domain-specific patterns are sometimes used in conjunction with other techniques (e.g., [9] and [18]).
Despite the effectiveness of these solutions, timetabling remains a challenge, especially for huge data sets with several limitations. This study examines the effectiveness of employing genetic algorithms (GAs) to find the best school schedule in a broad search area.
Our work differs from earlier studies in that we developed a theoretical foundation to ensure the suggested method converges. Our research focuses on real-time data sets with competing constraints, which is uncommon in previous studies. The work aims to achieve the following objectives.
1. Investigate a theoretical framework for using GAs in timetable construction.
2. Create and evaluate a genetic algorithm to address the timetabling problem with a trial dataset.
3. Using the results of objective (2), propose a distributed timetabling GA.
1
1.2 Methodology.
The research begins by modelling the timetable problem and developing a theoretical foundation to ensure the proposed algorithm converges.
Secondly, a serial algorithm is created and prototyped to generate a timetable from a subset of real-world university student data, with the goal of analysing how different parameters affect convergence behaviour.
Next, the technique is tested on a larger dataset to determine its scalability. This paper proposes a parallel/distributed GA that takes advantage of existing architectures to improve performance on real-world datasets.
The remainder of this work is structured as follows: Section 2 provides an overview of essential schedule and GA ideas to build the groundwork for further discussion.
This section reviews and analyses the literature on GA-based scheduling algorithms and heuristics. The analysis compares the proposed research topic to existing work and situates it within the field. Section 3 presents the theoretical framework
suggested genetic algorithm, and findings from prototype and test data sets. The section finishes with a description of the suggested distributed genetic algorithm.
Section 4 summarises the analytical results, discusses the algorithm’s weaknesses, and offers future directions.
Need help with a related project topic or New topic? Send Us Your Topic