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...

Full description

Saved in:

Bibliographic Details
Main Author:	Ishak, Suhada
Format:	Thesis
Language:	English
Published:	2015
Subjects:	Genetic algorithms Mathematics
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	my-upm-ir.67728
record_format	uketd_dc
spelling	my-upm-ir.677282019-03-21T00:39:53Z Hybrid genetic algorithm for uncapacitated university examination timetabling problem 2015-12 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 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. Genetic algorithms Schedules, School - Mathematical models Mathematics 2015-12 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 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.
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

Hybrid genetic algorithm for uncapacitated university examination timetabling problem

Similar Items