Full Project – University timetable automation using genetic algorithm
Click here to Get this Complete Project Chapter 1-5
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 arrangedaccording 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 redundancythrough 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 largediversity 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 mainpoint 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 alsodetails the tasks requiredto 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 usedwhile writing this report
Get the Complete Project
This is a premium project material and the complete research project plus questionnaires and references can be gotten at an affordable rate of N3,000 for Nigerian clients and $8 for international clients.
Click here to Get this Complete Project Chapter 1-5
You can also check other Research Project here:
- Accounting Research Project
- Adult Education
- Agricultural Science
- Banking & Finance
- Biblical Theology & CRS
- Biblical Theology and CRS
- Biology Education
- Business Administration
- Computer Engineering Project
- Computer Science 2
- Criminology Research Project
- Early Childhood Education
- Economic Education
- Education Research Project
- Educational Administration and Planning Research Project
- English
- English Education
- Entrepreneurship
- Environmental Sciences Research Project
- Guidance and Counselling Research Project
- History Education
- Human Kinetics and Health Education
- Management
- Maritime and Transportation
- Marketing
- Marketing Research Project 2
- Mass Communication
- Mathematics Education
- Medical Biochemistry Project
- Organizational Behaviour
- Political Science
- Psychology
- Public Administration
- Public Health Research Project
- More Research Project
- Transportation Management
- Nursing
Full Project – University timetable automation using genetic algorithm