ABSTRACT
Scheduling course, examination, Invigilation timetables for a large array of courses is a very complex problem which often has to be solved manually by the Examination office 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 make sure scheduled timetables do not violate fundamental constraints.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, venues 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.
Table of Contents
CERTIFICATION/APPROVAL. i
DEDICATION.. ii
ACKNOWLEDGEMENT. iii
ABSTRACT. iv
LIST OF FIGURES. 5
LIST OF TABLES. 7
CHAPTER ONE. 8
INTRODUCTION.. 8
1.0 Background of the Project 8
1.1 Statement of the Research Problem.. 10
1.2 Aims and Objectives of the Project 11
1.3 Significance of the Project 12
1.4 Scope of the Project 12
1.5 Research Methodology. 12
1.6 Limitations of the Project. 14
1.7 Research Outline. 14
1.8 Definition Of Terms. 14
CHAPTER TWO.. 16
LITERATURE REVIEW… 16
2.1 Introduction. 16
2.2 Constraint Types In Automated Scheduling. 18
2.2.1 Hard Constraints. 18
2.2.2 Soft Constraints. 19
2.3. Review Of Relevant Existing Theories And Technologies. 19
2.3.1 Evolutionary and genetic algorithms. 23
2.3.2 Ant Colony algorithm.. 24
2.3.3 Memetic algorithm.. 25
2.3.4 Harmony search algorithm.. 25
2.3.5 Tabu search. 25
2.3.6 Simulated annealing. 26
2.3.7 Local search. 26
2.3.8 Fuzzy approach. 27
2.4. Timetabling As An Np-Complete Problem.. 28
2.5. Thorough Examination Of The Genetic Algorithm.. 29
2.5.1. A Brief History Of Genetic Algorithms. 29
2.5.2. Genetic Algorithms. 31
2.5.3 Methods Of Representation. 34
2.5.4 Methods Of Selection. 36
2.5.5. Methods Of Change. 38
2.5.6. Strengths Of Genetic Algorithms. 40
2.4.7. Limitations Of Genetic Algorithms. 47
2.6. Application Of Genetic Algorithms In This Research. 53
CHAPTER THREE. 55
SYSTEM ANALYSIS AND DESIGN.. 55
3.1. Introduction. 55
3.2. The Existing System.. 55
3.2.1. Review Of The Existing System.. 55
3.2.2. Advantages Of The Existing System.. 56
3.2.3. Limitations Of The Existing System.. 56
3.3. The Proposed System.. 57
3.3.1. Review Of The Proposed System.. 57
3.3.2. Advantages Of The Proposed System.. 57
3.3.3. Limitations Of The Proposed System.. 58
3.4. Systems Design. 58
3.5. Modelling The System.. 58
3.5.1. Uml (Unified Modelling Language) Modelling. 59
3.6. FILES DESIGN.. 72
CHAPTER FOUR.. 78
SYSTEM IMPLEMENTATION.. 78
4.1. INTRODUCTION.. 78
4.2. CHOICE OF PROGRAMMING LANGUAGE. 78
4.3. PROGRAM WRITING.. 78
4.4. SYSTEMS REQUIREMENTS. 78
4.4.1. HARDWARE REQUIREMENTS. 79
4.4.2. SOFTWARE REQUIREMENTS. 79
4.5. DOCUMENTATION.. 79
4.5.1. PROGRAM MODULES AND INTERFACE. 79
CHAPTER FIVE. 86
SUMMARY, CONCLUSION AND RECOMMENDATIONS. 86
5.1. Summary. 86
5.2. Conclusion. 86
5.3. Recommendations. 86
5.4. Problems Encountered. 87
5.5. Scope For Further Works. 87
REFERENCES. 88
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
Figure 4.8 View timetable section
Figure 4.9 View messages input 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
CHAPTER ONE
INTRODUCTION
1.0 Background of the Project
The Examinations Office is responsible for the central administration of the University examinations, both traditional and semesterised. Examination is a written, practical and spoken assessment that schools and colleges organize in order to assess their student’s level of understanding of their subjects. It is currently the most effectively known way the university assesses its students in order to determine the type of grades they obtain which in turn categorizes the students’ status in the university during the school years i.e. either to be promoted to the next level or otherwise. After completing the study, students are categorized based on their performance in the examinations, From the above, it could be seen that Examination is a very important process in the running of a tertiary institution more especially the university. They are a core function of educational institutions and Quality is considered to be very important in Examinations.(Vasupongayya, Noodam, & Kongyong, 2013)
The Examinations office provides centralized services and support to ensure consistent and high-quality conduct of examinations across all campuses of the University, as well the efficient utilization of resources.
The Examinations Section has the following primary functions:
- Centrally coordinated timetablingof teaching(in some cases)
- Information on transcripts
- Preparation of the Academic Administration Calendar
- Advice on and charts of the academic year
- Preparation of Programme & Unit Catalogues
- Student data and statistics, and reports to external bodies (g, NUC)
- Exam scheduling and supervision across all BUK campuses.
- Exam paper management for central exams, including printing, venue allocation, and prompt delivery to lecturers for marking.
- Recruitment and training of casual examination supervisors.
- Making alternative exam arrangements for students who, for a variety of reasons, are unable to sit their exams with the main cohort.
- Making arrangements for ill students to sit exams off-campus where applicable.
- Arranging venues and supervision for exams held by other institutions on our campus.
- Providing a central port of call for enquiries from students and staff about examinations matters.
Currently, in almost all educational tertiary institutes, there is no automated or efficient intelligent time table system which is a function of the Examination office. It is a reality that all educational tertiary institutions ranging from small to large ones are using the manual system which is a very difficult, prompt to error and time consuming process. This manual system becomes a hot issue at the start of each new semester for the Examination office and Head of Department. We cannot get historical data to make the job easy and comfortable. Among other fundamental problems of a manual system like lack of correctness, slow speed of the system and problems in sharing of information etc. the key problems usually are:
1) Keeping and managing of record for the previous data.
2) Management of multiple queries for the same subject.
3) Making available interested subjects for a lecturer.
4) Scheduling venues for lectures
5) Availability of sufficient information during the development of time table.
Therefore, to design and develop a time table for educational institutions is not an easy and comfortable job.
1.1 Statement of the Research Problem
All Examination office procedures and processes are usually implemented manually making it a bulky and tiring process, which poses serious problems due to factors such as human error, storage misfiling, and misplacement of files, inaccurate scheduling time table system where courses and lecturer schedules clash, inadequate information delivery methods. These are the problems currently being faced in the Examination Office.
1.2 Aims and Objectives of the Project
The project will majorly seek to design, develop and implement an Examination Office management system that automates all the processes for the examination office of the faculty of Computer Science and Information technology of the university.
The objectives the software wishes to achieve are
- To Publish and inform Faculties, Deans, Departments and other Administrative Offices on all examination deadlines, processes and procedures
- To Create and Issue lecture timetables and schedules for lecturers and students
- To Issue examination timetables in a timely manner, take feedback from Staff and Students, issue timetables to students online, provide one Single helpdesk for examination complains.
- To Process appeals and rechecks in a timely manner, ensuring students are notified of outcomes as soon as possible
- To Create and issue Examination Invigilation timetables.
1.3 Significance of the Project
This project which seeks to design and develop a software system that can automate the processes in the examination office will be useful in the following ways:
- Provide a central point of information to both staff and students of the faculty, making information available in a timely manner
- Greatly reduce the amount of work in the examination office, making the whole of the procedures in the examination office easy and flexible.
- Greatly reduce errors in the scheduling of examination, lecture and examination invigilation timetables, putting into consideration all the factors previously overlooked in the manual system like clashing of classes for carry over students.
- Make the processes in the examination office efficient and fast.
1.4 Scope of the Project
The project will cover the automation of the activities done in the examination office of the faculty of computer science and information technology.
1.5 Research Methodology
This research is based on the problem of automation of the activities in the examination office of FCSIT, which involves a lot of activities foremost among them that of timetabling scheduling. Timetable construction problems are interesting subjects of study because neither modeling nor solving them is easy or straightforward because of the number of constraints involved. It is difficult to make a clear-cut distinction between acceptable and not acceptable timetables (Adekunle 2012). 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 the timetable generation module of the examination office management system is supposed to handle, a linear method or algorithm cannot be put to use to handle such validation and generation, hence the usage of a heuristic method. The heuristic method to be used in this project 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 Examination Office. The different validation and constraint was as a result of careful observation of the timetable release of the Faculty from past years.
Due to the many processing and constraint validations the genetic algorithm will be performing in the proposed system, a programming tool Php (Hypertext preprocessor) which has over the years proven to be able to optimize programs compilation and C.P.U. usage will be used for the Frontend design and Mysql Database management System will be used for the Backend Design.
1.6 Limitations of the Project.
In carrying out this project work, we were faced with some limitations. Designing a management system is quite a complex task especially with the fact that the word management alone encompasses a lot of functions which the system will aim to meet and also the fact that one is not quite efficient or skillful in the programming language of implementation.
Below are some of the limitations that may hinder the functionalities of the system:
- 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.7 Research Outline
This Project 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
1.8 Definition Of Terms
Academic Planning: Activity carried out by the School or Campus leading to the identification of the staff, space, time and related non-financial resources required to deliver the approved instructional activity.
Academic Space: Includes space in which College-approved instructional activity may be scheduled. Generally this includes classrooms, laptop classrooms, lecture theatres, labs, shops and studios, and in some cases gymnasia, conference rooms, outdoor spaces and adjacent or related spaces used to support instructional activity.
Dedicated Space: An Academic Space that has been assigned to a School or Campus for a specified instructional activity.
Equitable: Fair and just (but not necessarily equal).
Master Timetable: The official product of the Scheduling process.
Room Utilization: The ratio of the audited in-use hours per week for a room divided by the hours per week that the room is available for Scheduling.
Seat Utilization: The ratio of the audited in-use hours per week of the seats in a room divided by the hours per week that the seats are available for Scheduling.
Scheduling: The process of assigning approved University academic activities into specific time and space.
Scheduling Deadlines Document: Defines points in time of the Scheduling process.
Timetable: A view of the Master Timetable from a specific perspective (e.g. student, Faculty, room, etc.).
FCSIT: This stands for Faculty of Computer Science and Information Technology, Bayero University Kano.
DISCLAIMER: All project works, files and documents posted on this website, UniProjectTopics.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. UniProjectTopics.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. All creative work builds on what came before. Nothing is completely original.” - Austin Kleon. The paid subscription on UniProjectTopics.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.
