UPM Institutional Repository

Hybrid genetic algorithm for uncapacitated university examination timetabling problem


Citation

Ishak, Suhada (2015) Hybrid genetic algorithm for uncapacitated university examination timetabling problem. Masters thesis, Universiti Putra Malaysia.

Abstract

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.


Download File

[img]
Preview
Text
FS 2015 55 IR.pdf

Download (1MB) | Preview

Additional Metadata

Item Type: Thesis (Masters)
Subject: Genetic algorithms
Subject: Schedules, School - Mathematical models
Subject: Mathematics
Call Number: FS 2015 55
Chairman Supervisor: Lee Lai Soon, PhD
Divisions: Faculty of Science
Depositing User: Mas Norain Hashim
Date Deposited: 21 Mar 2019 00:39
Last Modified: 21 Mar 2019 00:39
URI: http://psasir.upm.edu.my/id/eprint/67728
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item