Hybrid genetic algorithm for uncapacitated university examination timetabling problem

• المؤلف الرئيسي: Ishak, Suhada
• التنسيق: أطروحة
• اللغة: الإنجليزية
• منشور في: 2015
• الموضوعات: Genetic algorithms; Schedules, School - Mathematical models; Mathematics
• الوصول للمادة أونلاين: http://psasir.upm.edu.my/id/eprint/67728/1/FS%202015%2055%20IR.pdf

This study proposes a Hybrid Genetic Algorithm (HGA) for university examination timetabling problem (UETP). UETP is defined as the assignment of a given number of exams and their candidates to a number of available timeslots while satisfying a given set of constraints. This study presents a solution for an uncapacitated UETP where five domain-specific knowledges in the form of low-level heuristics are used to guide the construction of the timetable in the initial population. This study propose to use 10% from the total exams to be scheduled with the combination of Largest Degree (LD), Largest Weighted Degree (LWD) and Largest Enrollment (LE) while another 90% is the combination of Saturation Degree (SD) and Highest Cost (HC). The main components of the genetic operators in a Genetic Algorithm (GA) will be tested and the best combination of the genetic operators will be adopted to construct a Pure Genetic Algorithm (PGA). The PGA will then hybridised with three new local optimisation techniques, which will make up the HGA; to improve the solutions found. The first local optimisation technique focuses on inserting a scheduled exam to a new timeslot, second technique is concerned with the swapping of two scheduled exams between two different timeslots and the third technique deals with interchanging the timeslots in the timetable. These new local optimisation techniques will arrange the timeslots and exams using new explicit equations, if and only if, the modification will reduce the penalty cost function. All proposed algorithms are coded in C using Microsoft Visual C++ 6.0 as the compiler. The performance of the proposed HGA is compared with other metaheuristics from literature using the Carter set of benchmark problems which comprises of real-world timetabling problem from various universities. The computational results show that the proposed HGA outperformed some of the metaheuristic approaches and is comparable to most of the metaheuristic approaches.