Hybrid genetic algorithm for uncapacitated university examination timetabling problem
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...
Saved in:
Main Author:  

Format:  Thesis 
Language:  English 
Published: 
2015

Subjects:  
Online Access:  http://psasir.upm.edu.my/id/eprint/67728/1/FS%202015%2055%20IR.pdf 
Tags: 
Add Tag
No Tags, Be the first to tag this record!

id 
myupmir.67728 

record_format 
uketd_dc 
spelling 
myupmir.6772820190321T00:39:53Z Hybrid genetic algorithm for uncapacitated university examination timetabling problem 201512 Ishak, Suhada 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 domainspecific knowledges in the form of lowlevel 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 realworld 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. Genetic algorithms Schedules, School  Mathematical models Mathematics 201512 Thesis http://psasir.upm.edu.my/id/eprint/67728/ http://psasir.upm.edu.my/id/eprint/67728/1/FS%202015%2055%20IR.pdf text en public masters Universiti Putra Malaysia Genetic algorithms Schedules, School  Mathematical models Mathematics 
institution 
Universiti Putra Malaysia 
collection 
PSAS Institutional Repository 
language 
English 
topic 
Genetic algorithms Genetic algorithms Mathematics 
spellingShingle 
Genetic algorithms Genetic algorithms Mathematics Ishak, Suhada Hybrid genetic algorithm for uncapacitated university examination timetabling problem 
description 
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 domainspecific knowledges in the form of lowlevel 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 realworld 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. 
format 
Thesis 
qualification_level 
Master's degree 
author 
Ishak, Suhada 
author_facet 
Ishak, Suhada 
author_sort 
Ishak, Suhada 
title 
Hybrid genetic algorithm for uncapacitated university examination timetabling problem 
title_short 
Hybrid genetic algorithm for uncapacitated university examination timetabling problem 
title_full 
Hybrid genetic algorithm for uncapacitated university examination timetabling problem 
title_fullStr 
Hybrid genetic algorithm for uncapacitated university examination timetabling problem 
title_full_unstemmed 
Hybrid genetic algorithm for uncapacitated university examination timetabling problem 
title_sort 
hybrid genetic algorithm for uncapacitated university examination timetabling problem 
granting_institution 
Universiti Putra Malaysia 
publishDate 
2015 
url 
http://psasir.upm.edu.my/id/eprint/67728/1/FS%202015%2055%20IR.pdf 
_version_ 
1747812510203904000 