1.2. STATEMENT OF THE PROBLEM.. 11
1.3. AIM AND OBJECTIVES OF RESEARCH.. 11
1.4. RESEARCH METHODOLOGY.. 12
1.6. SIGNIFICANCE OF THE STUDY.. 13
REVIEW OF RELEVANT LITERATURE. 15
2.2. REVIEW OF RELEVANT EXISTING THEORIES AND TECHNOLOGIES 16
2.3. TIMETABLING AS AN NP-COMPLETE PROBLEM.. 19
2.4. THOROUGH EXAMINATION OF THE GENETIC ALGORITHM.. 20
2.4.1. A BRIEF HISTORY OF GENETIC ALGORITHMS. 20
2.4.3 METHODS OF REPRESENTATION.. 24
2.4.4 METHODS OF SELECTION.. 25
2.4.6. STRENGTHS OF GENETIC ALGORITHMS. 28
2.4.7. LIMITATIONS OF GENETIC ALGORITHMS. 33
2.5. APPLICATION OF GENETIC ALGORITHMS IN THIS RESEARCH.. 37
SYSTEM ANALYSIS AND DESIGN.. 40
3.2.1. REVIEW OF THE EXISTING SYSTEM.. 40
3.2.2. ADVANTAGES OF THE EXISTING SYSTEM.. 41
3.2.3. LIMITATIONS OF THE EXISTING SYSTEM.. 41
3.3.1. REVIEW OF THE PROPOSED SYSTEM.. 41
3.3.2. ADVANTAGES OF THE PROPOSED SYSTEM.. 42
3.3.3. LIMITATIONS OF THE PROPOSED SYSTEM.. 42
3.5. MODELLING THE SYSTEM.. 43
3.5.1. UML (UNIFIED MODELLING LANGUAGE) MODELLING.. 43
4.2. CHOICE OF PROGRAMMING LANGUAGE. 61
4.4.1. HARDWARE REQUIREMENTS. 62
4.4.2. SOFTWARE REQUIREMENTS. 62
4.5.1. PROGRAM MODULES AND INTERFACE. 62
SUMMARY, CONCLUSION AND RECOMMENDATIONS. 69
5.4. PROBLEMS ENCOUNTERED.. 70
5.5. SCOPE FOR FURTHER WORKS. 70
LIST OF FIGURES
Figure 2.1. Diagram of Program trees used in genetic programming
Figure 2.2. Diagram to show the effect of mutation in a population
Figure 2.3. Diagram to show the effect single-point crossover in a population
Figure 2.4. Diagram depicting the Hybrid Genetic Algorithm
Figure 3.1. Use Case Diagram
Figure 3.2. Class Diagram
Figure 3.3. Sequence Diagram
Figure 3.4. Activity Diagram
Figure 3.5. State Diagram
Figure 3.6. Collaboration Diagram
Figure 3.7. Component Diagram
Figure 3.8. Hall File Processing Diagram
Figure 3.9. Program File Processing Diagram
Figure 3.10. Building File Processing Diagram
Figure 3.11. Lecturer File Processing Diagram
Figure 3.12. Departments File Processing Diagram
Figure 3.12. Course File Processing Diagram
Figure 4.1. Building and Hall Input Section
Figure 4.2. Department Input Section
Figure 4.3. Program Input Section
Figure 4.4. Lecturer Input Section
Figure 4.5. Level Constraint Input Section
Figure 4.6. Course Input Section
Figure 4.7. Report Section
LIST OF TABLES
Table 3.1. Hall Table
Table 3.2. Programs Table
Table 3.3. Buildings Table
Table 3.4. Lecturers Table
Table 3.5. Buildings Table
Table 3.6. Buildings Table
ABSTRACT
Scheduling course timetables for a large array of courses is a very complex problem which often has to be solved manually by the center staff even though results are not always fully optimal. Timetabling being a highly constrained combinatorial problem, this work attempts to put into play the effectiveness of evolutionary techniques based on Darwin’s theories to solve the timetabling problem if not fully optimal but near optimal.
Genetic Algorithm is a popular meta-heuristic that has been successfully applied to many hard combinatorial optimization problems which includes timetabling and scheduling problems. In this work, the course sets, halls and time allocations are represented by a multidimensional array on which a local search is performed and a combination of the direct representation of the timetable with heuristic crossover is made to ensure that fundamental constraints are not violated.
Finally, the genetic algorithm was applied in the development of a viable timetabling system which was tested to demonstrate the variety of possible timetables that can be generated based on user specified constraint and requirements.
CHAPTER ONE
INTRODUCTION
1.1. BACKGROUND STATEMENT
Timetabling concerns all activities with regard to making a timetable that must be subjective to different constraints. According to Collins Concise Dictionary (4th Edition) “a timetable is a table of events arranged according to the time when they take place.”
A critical factor in running a university or essentially an academic environment is the need for a well-planned and clash-free timetable. Back in the times when technology was not in wide use, academic timetables were manually created by the educational center staff.
Every school year, institutions of education face the rigorous task of drawing up timetables that satisfies the various courses and their respective examinations being offered by the different department. The difficulty is due to the great complexity of the construction of timetables for lectures and exams, due to the scheduling size of the lectures and examinations periods and the high number of constraints and criteria of allocation, usually circumvented with the use of little strict heuristics, based on solutions from previous years (Jose, 2008).
Nowadays, this process has been simplified by semi-automatic solutions based on timetable generation applications (e.g. Open Course Timetabler). A timetable management system is designed and created to handle as much course data as fed while ensuring the avoidance of redundancy. An educational timetable must meet a number of requirements and should satisfy the desires of all entities involved simultaneously as well as possible. The timing of events must be such that nobody has more than one event at the same time (Robertus, 2002).
The proposed timetabling system is designed to handle events of course lectures offered at a university (university course timetabling).
Based on the above event, the system would have only one module which is the Course Lecture Timetable Module.
1.2. STATEMENT OF THE PROBLEM
The systems available currently can build or generate a set of timetables, but still have issues with generating a clash-free and complete timetable. The tedious tasks of data introduction and revision of usually incomplete solutions are the bottleneck in these cases (Luisa et. al., 2006). Most educational institutions have resorted to manual generation of their timetables which according to statistics takes over a month to get completed and optimal. Even at the optimal stage of the manually generated timetable, there are still a few clashes and it is the lecturer that takes a clashing course that works out the logistics of the course so as to avoid the clash.
1.3. AIM AND OBJECTIVES OF RESEARCH
The literature on and implementation of educational timetabling problems is quite scattered. Different research papers that have been brought out on timetabling may refer to the same type of institution but they mostly deal with different kinds of assignments, i.e., decisions like the timing of events, sectioning students into groups, or assigning events to locations. Moreover, each institution has its own characteristics which are reflected in the problem definition (Robertus, 2002). Yet, there have been no leveling grounds for developing a system that can work for most of these institutions.
The aim of this work is the generation of course schedules while demonstrating the possibility of building these schedules automatically through the use of computers in such a way that they are optimal and complete with little or no redundancy through the development of a viable lecture timetabling software.
The primary objective is to be able to optimize the algorithm used in today’s timetable systems to generate the best of timetabling data with fewer or no clashes.
The secondary objective is to expand the scope of timetable automation systems by making it generic thereby bringing about uniformity in the creation of timetables as it applies to different universities or educational institutions i.e. will be able to generate timetables that fit the requirements of any academic institution.
1.4. RESEARCH METHODOLOGY
This research is concerned with the problem of constructing timetables for schools. School timetable construction problems are interesting objects to study because neither modeling nor solving them is straightforward. It is difficult to make a clear-cut distinction between acceptable and not acceptable timetables. Because of the large diversity in acceptance criteria, realistic timetable construction problems are multidimensional. Each dimension may introduce its own characteristic aspects that add to the complexity of the problem. Therefore, only heuristic solution approaches without known performance guarantees are practically feasible (Robertus , 2002).
As a result of the large data input a timetable management system is supposed to handle, a linear method or algorithm cannot be employed to handle such validation and generation, hence the usage of a heuristic method. The heuristic method to be used in this study is the genetic algorithm. The genetic algorithm is one that seeks to find the most optimal solutions where the search space is great and conventional methods is inefficient.; it works on a basis of the Darwinian evolution theory (Alberto, 1992).
The data (i.e. course data) used in the program are gotten from the CU Intranet site (datacenter.cu). The different validation and constraint was as a result of careful observation of the timetable release of the school from past years.
Due to the many processing and constraint validations the genetic algorithm will be performing in the proposed system, a programming tool like Delphi IDE (Object Pascal) which has over the years proven to be able to optimize programs compilation and C.P.U. usage will be used for the backend design.
External physical files will serve as the database to which the system will hold the generated output i.e. the final timetable and requirement specification, the choice of file handling is because of its non-complex support, portability and its ability to handle large amounts of data.
1.5. SCOPE OF THE STUDY
The boundaries of this work take into consideration all academic institutions from the primary level to the higher institution level– whether this be in a Nigerian campus environment, the UK or worldwide. It will only involve the technical skills of one academic personnel and a few data collaborators to handle the data input and constraint specifications. The proposed system will be able to handle as much data input as possible i.e. the course data, halls data, lecturers data etc.
1.6. SIGNIFICANCE OF THE STUDY
Outlined below is the significance of the proposed system and the improvements on existing systems that are featured in this system:
- The proposed system will provide an attractive graphical front-end which acts as the main point of interaction with user and data collaborators.
- It will also improve flexibility in timetable construction.
- The system will be able to generate reports on conflicting constraint specifications.
- The system will seek to improve on previous versions of timetable generating system.
- Stress in creating timetable manually will be greatly reduced as output would be automated.
- The system will save time.
- Productivity will be improved.
- The system can be revised i.e. its backend can be revised.
1.7. LIMITATIONS
Below are some of the limitations that may hinder the functionalities of the system:
- Unserious collaborative work from staffs in the various departments.
- Incomplete data from data collaborators.
- Wrong data input by technical user: the system will only work with data supplied; hence wrong data input might have to be edited manually.
- Wrong constraints specification.
- Low system memory capacity.
1.8. RESEARCH OUTLINE
This report contains a further four sections. Chapter 2 gives further background information while reviewing in details the workings of existing systems. Chapter 3 discusses the structure, design and internal workings of each module in the project, it also details the tasks required to complete the project, and a timescale to complete them in. Chapter 4 details the backend of the system and shows the development and testing of each stage in the project. Chapter 5 presents my summary, conclusions and recommendations. The final section lists the references used while writing this report
DISCLAIMER: All project works, files and documents posted on this website, eProjectTopics.com are the property/copyright of their respective owners. They are for research reference/guidance purposes only and some of the works may be crowd-sourced. Please don’t submit someone’s work as your own to avoid plagiarism and its consequences. Use it as a reference/citation/guidance purpose only and not copy the work word for word (verbatim). The paper should be used as a guide or framework for your own paper. The contents of this paper should be able to help you in generating new ideas and thoughts for your own study. eProjectTopics.com is a repository of research works where works are uploaded for research guidance. Our aim of providing this work is to help you eradicate the stress of going from one school library to another in search of research materials. This is a legal service because all tertiary institutions permit their students to read previous works, projects, books, articles, journals or papers while developing their own works. This is where the need for literature review comes in. “What a good artist understands is that nothing comes from nowhere. The paid subscription on eProjectTopics.com is a means by which the website is maintained to support Open Education. If you see your work posted here by any means, and you want it to be removed/credited, please contact us with the web address link to the work. We will reply to and honour every request. Please notice it may take up to 24 – 48 hours to process your request.
