University Examination Timetable Scheduling Using Constructive Heuristic Compared to Genetic Algorithm

Examination Timetable Scheduling can be defined as assigning a set of exams into a limited number of days and periods, subject to a set of constraints, some of which contradict each other. An issue that makes timetabling a challenging task most universities have to solve every semester. It usually takes days or even weeks to find a solution that does not even “entirely” satisfy the universities’ constraints. Automating this task is really challenging, since timetabling problem is a Nondeterministic Polynomial time (NP) complete problem. The most known characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases exponentially as the size of the problem grows. NP-complete problems have tremendous solution space, so brute-force methods cannot be used . This research builds and compares the performance of two proposed solutions; Genetic Algorithm and Constructive Heuristic models when both used to solve a real-world examination time-tabling problem at Misr University for Science and Technology (MUST). This re-search shows how the Constructive Heuristic proposed outperformed the Genetic Algorithm in creating optimized schedules which solves all the students’ conflicts. An easy to use, GUI desktop application was created to be used by all universities’ members, to automate their timetabling tasks, the program creates many feasible schedules, meeting all requirements of MUST examination timetables, while reducing the pressure on the students, in seconds, which will result in saving a lot of time and effort for the universities’ members.