Design and Implementation of Timetable Generating System
Chapter One
AIM AND OBJECTIVES OF THE STUDY
The aim of this study is to generate a lecture timetable for Ogun State Institute of Technology, Igbesa.
The objective at this project is to solve the problem that has been encountered in the manual or existing system of the department. Other aims and objectives are started below:
- The objective of the automated timetable generated project was to be developed a tool that enables department to dynamically generate timetable for student to access directly from the schedule table data.
- It enables the department to present changes to their schedule immediately tiding public.
- It enables the department to plan well in advance to design the student schedule.
- It will also enable the management and student with updated schedule information when changes occur.
- It will enable the management to provide timely accurate schedule data.
CHAPTER TWO
LITERATURE REVIEW
INTRODUCTION
A timetable is an organized list, usually set out in tabular form, providing information about a series of arranged events in particular, the time at which it is planned these events will take place. They are applicable to any institution where activities have to be carried out by various individuals in a specified timeframe. From the time schools became organized environments, timetables have been the framework for all school activities. As a result, schools have devoted time, energy and human capital to the implementation of nearly optimal timetables, which must be to satisfy all required constraints as specified by participating entities (Robertus, 2002).
The lecture-timetabling problem is a typical scheduling problem that appears to be a tedious job in every academic institute once or twice a year. The problem involves the scheduling of classes, students, teachers and rooms at a fixed number of time-slots, subject to a certain number of constraints. An effective timetable is crucial for the satisfaction of educational requirements and the efficient utilization of human and space resources, which make it an optimization problem. Traditionally, the problem is solved manually by trial and hit method, where a valid solution is not guaranteed. Even if a valid solution is found, it is likely to miss far better solutions. These uncertainties have motivated for the scientific study of the problem, and to develop an automated solution technique for it. The problem is being studied for last more than four decades, but a general solution technique for it is yet to be formulated (Datta D. et.al, 2006).
Timetabling problem is one of the hardest problem areas already proven to NP-complete and it is worthy of note that as educational institutions are challenged to grow in number and complexity, their resources and events are becoming harder to schedule (Ossam Chohan, 2009).
REVIEW OF RELEVANT THEORIEDS AND TECHNOLOGIES
Solutions to timetabling problems have been proposed since the 1980s. Research in this area is still active as there are several recent related papers in operational research and artificial intelligence journals. This indicates that there are many problems in timetabling that need to be solved in view of the availability of more powerful computing facilities and advancement of information technology (S.B. Deris et.al, 1997).
The problem was first studied by Gotlieb (1962), who formulated a class-teacher timetabling problem by considering that each lecture contained one group of students, one teacher, and any number of times, which could be chosen freely. Since then the problem is being continuously studied using different methods under different conditions. Initially it was mostly applied to schools. Since the problem in schools is relatively simple because of their simple class structures, classical methods, such as linear or integer programming approaches, could be used easily.
However, the gradual consideration of the cases of higher secondary schools and universities, which contain different types of complicated class-structures, is increasing the complexity of the problem. As a result, classical methods have been found inadequate to handle the problem, particularly the huge number of integer and/or real variables, discrete search space and multiple objective functions.
This inadequacy of classical methods has drawn the attention of the researchers towards the heuristic-based non-classical techniques. Worth mentioning non-classical techniques that are being applied to the problem are Genetic Algorithms, Neural Network, and Tabu Search Algorithm (Costa D., 1994). However, compared to other non-classical methods, the widely used are the genetic/evolutionary algorithms (GAs/EAs). The reason might be their successful implementation in a wider range of applications. Once the objectives and constraints are defined, EAs appear to offer the ultimate free lunch scenario of good solutions by evolving without a problem solving strategy.
Since 1995, a large amount of timetabling research has been presented in the series of international conferences on Practice and Theory of Automated Timetabling (PATAT). Papers on this research have been published in conference proceedings, see e.g., (Burke & Carter, 1997), and three volumes of selected papers in the Lecture Notes in Computer Science Additionally, there is a EURO working group on automated timetabling (EURO-WATT) which meets once a year regularly sends out a digest via e-mail, and maintains a website with relevant information on timetabling problems, e.g., a bibliography and several benchmarks.
Carter (1997), in his doctoral thesis, investigates the use of genetic algorithms to solve a group of timetabling problems. He presents a framework for the utilization of genetic algorithms in solving of timetabling problems in the context of learning institutions. This framework has the following important points, which give you considerable flexibility: a declaration of the specific constraints of the problem and use of a function for evaluation of the solutions, advising the use of a genetic algorithm, since it is independent of the problem, for its resolution.
Carter presents an approach to generalize all the timetabling problems, describing the basic structure of this problem and proposes a generic language that can be used to describe timetabling problems and its constraints.
Chan (1997) discusses the implementation of two genetic algorithms used to solve class-teacher timetabling problem for small schools.
Oliveira (2000) presents a language for representation of the timetabling problem, the UniLang. UniLang intends to be a standard suitable as input language for any timetabling system. It enables a clear and natural representation of data, constraints, quality measures and solutions for different timetabling (as well as related) problems, such as school timetabling, university timetabling and examination scheduling.
CHAPTER THREE
RESEARCH METHODOLOGY
INTRODUCTION
Waterfall model is employed as the software model in designing this system because of its simplicity. All the phases of SDLC will function one after another in linear manner. That is, when the first phase is finished then only the second phase will start and so on.
ANALYSIS OF EXISTING SYSTEM
In Ogitech, Igbesa, timetable scheduling is done by:
- The submission of examinable and non-examinable courses by the department officer/secretary of each department.
- The submitted documents are taken by the timetable committee.
- At the end of receiving inputs from students and lectures alike, the final timetable is presented to the school and it will become a working document for that semester.
The traditional manual generations of timetables encounters a lot of problems which may include the following:
- Repeated time allocations may be made for a particular course thereby leading to data redundancy.
- A lot of administrative error may occur as a result of confusing time requirements.
- Timetable generation by center staff may have a slow turnaround.
- Final generated timetable may not be near optimal as a result of clashing course requirements and allocations.
- It generates a lot of paperwork and is very tasking.
- It is not flexible as changes may not be easily made.
OVERVIEW OF PROPOSED SYSTEM
The proposed systems was developed to solve the timetabling problem being faced by institution every academic year and reduce high cost and slow turnaround involved in the generation of near-optimal timetables.
The system has capabilities for input of the various courses, departments, levels, lecturers and the specification of a few constraints from which the timetable is constructed. The proposed timetabling system for this project seeks to generate near optimal timetables using the principles of genetic algorithm (selection and crossover).
CHAPTER FOUR
SYSTEM TESTING AND IMPLEMENTATION
INTRODUCTION
System testing and implementation is the last step in software development. It involves a process of putting into action, a formulated plan. Before implementation, plans must have been completed and objectives must be clear.
CHAPTER FIVE
SUMMARY, CONCLUSION AND RECOMMENDATION
SUMMARY
The idea of the automated time table generation package is to eliminate the problem of manual time table generation which delays the commencement of lectures in every new academic calendar.
All said and done in this project, we have seen the inevitability of automation the department time tables. It gives the management and a more wide range of information at once, it saves time and effort user would have wasted in the existing system
CONCLUSION
The importance of this package to compute r science department cannot be over emphasized. The new system has carefully worked on a more advantageous way in which information will be processed quickly, by eliminating the problems encountered in the existing (manual timetable). It is very clear evidence that the automated tie table generation package system can be very timely, accurate, consistent, and efficient.
It can therefore be concluded that this package will greatly reduce the setback encounter in the manual system of operation.
RECOMMENDATION
To achieve its objectives in the new system, the institution should setup a committee that would, at intervals maintain the general option of system and make report on the performance of the hardware and software management.
For maintenance and modification, an expert should be consulted for proper research or investigation to be carried out on the hardware and the software manual before maintenance.
REFERENCES
- Adam B (2004). Genetic Algorithm. Retrieved from https://www.researchgate.net/profile/chibuzo_ukegbu2/publication/3076338797 on June 22, 2018
- Carter J (1997). Introduction to using genetic algorithm. Retrieved from https://www.sciencedirect.com/science/article/pii/s037673610380000798 on June 27, 2018
- Chan F (1997). Optimum Genetic Algorithm Structure Selection in Pavement. Retrieved from https://scialert.net/fulltextmobile%3Fdoi%3Dajaps on July 1, 2018
- Costa D., (1994). Genetic Algorithms. Retrieved from https://www.researchgate.net/profile/chibuzo_ukegbu2/publication/30763387 on June 24, 2018
- Datta D. et.al (2006). Utilization of Timetable Management. Retrieved from https://www.researchgate.net/publication/320708066_Utilization_of_a_Timetable_Management_System_to_a_Medium_Scaled_University on July 2, 2018
- Fernandes H (2002). Class teacher timetabling problems. Retrieved from https://pdfs.semanticscholar.org/3405/dc77d36d4eaec922.pdf on July 1, 2018
- Gotlieb (1962). Timetable Construction – PATAT Conference. Retrieved from https://www.patatconference.org/pata2010/proceedings/1_3.pdf on June 22, 2018
- Oliveira R (2000). Genetic Algorithm. Retrieved from https://www.researchgate.net/profile/chibuzo_ukegbu2/publication/3076338797 on June 22, 2018
