Partial examination assignment approaches for solving examination timetabling problems

Examination timetabling is one type of scheduling problems faced by academic institutions when allocating examinations into a limited number of time slots and/or rooms. It is obvious that the task of constructing a quality timetable is a challenging and time-consuming due to its NP-hard nature, with...

Full description

Saved in:

Bibliographic Details
Main Author:	Mandal, Ashis Kumar
Format:	Thesis
Language:	English
Published:	2016
Subjects:	QA75 Electronic computers Computer science T Technology (General)
Online Access:	http://umpir.ump.edu.my/id/eprint/25157/1/Partial%20examination%20assignment%20approaches%20for%20solving%20examination%20timetabling.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-ump-ir.25157
record_format	uketd_dc
spelling	my-ump-ir.251572021-09-07T02:23:44Z Partial examination assignment approaches for solving examination timetabling problems 2016-10 Mandal, Ashis Kumar QA75 Electronic computers. Computer science T Technology (General) Examination timetabling is one type of scheduling problems faced by academic institutions when allocating examinations into a limited number of time slots and/or rooms. It is obvious that the task of constructing a quality timetable is a challenging and time-consuming due to its NP-hard nature, with a large number of constraints having to be accommodated. It is observed in the literature that most of the reported research starts with constructing the initial feasible timetable(s) by allocating all examinations and then performs an improvement on the timetable. However, these traditional approaches bias toward the initial timetable where the improvement algorithms (sometimes) are affected and unable to produce a quality timetable. This thesis presents partial examination assignment approaches to address the examination timetabling problem. The proposed algorithms work by first ordering all examinations using graph heuristics ordering strategies. After that, partially selected examinations are scheduled, followed by an improvement on the partially scheduled examinations. The entire process runs until all of the examinations are assigned successfully. We have implemented partial graph heuristic with hill climbing (PGH-HC) and partial graph heuristic with modified great deluge algorithm (PGH-mGD) into solving the examination timetabling. The proposed approaches are tested on two benchmark datasets, namely Toronto dataset and the Second International Timetabling Competition (ITC2007) dataset. Experimental results demonstrate that the proposed approaches are able to produce quality solutions compared to traditional approaches for all instances of the datasets. Additionally, while compared with the state-of-the-art algorithms, our proposed approaches generally are able to produce competitive results and even outperform some of the reported results found in the scientific literature. 2016-10 Thesis http://umpir.ump.edu.my/id/eprint/25157/ http://umpir.ump.edu.my/id/eprint/25157/1/Partial%20examination%20assignment%20approaches%20for%20solving%20examination%20timetabling.pdf pdf en public masters Universiti Malaysia Pahang Faculty of Computer System & Software Engineering
institution	Universiti Malaysia Pahang Al-Sultan Abdullah
collection	UMPSA Institutional Repository
language	English
topic	QA75 Electronic computers Computer science T Technology (General)
spellingShingle	QA75 Electronic computers Computer science T Technology (General) Mandal, Ashis Kumar Partial examination assignment approaches for solving examination timetabling problems
description	Examination timetabling is one type of scheduling problems faced by academic institutions when allocating examinations into a limited number of time slots and/or rooms. It is obvious that the task of constructing a quality timetable is a challenging and time-consuming due to its NP-hard nature, with a large number of constraints having to be accommodated. It is observed in the literature that most of the reported research starts with constructing the initial feasible timetable(s) by allocating all examinations and then performs an improvement on the timetable. However, these traditional approaches bias toward the initial timetable where the improvement algorithms (sometimes) are affected and unable to produce a quality timetable. This thesis presents partial examination assignment approaches to address the examination timetabling problem. The proposed algorithms work by first ordering all examinations using graph heuristics ordering strategies. After that, partially selected examinations are scheduled, followed by an improvement on the partially scheduled examinations. The entire process runs until all of the examinations are assigned successfully. We have implemented partial graph heuristic with hill climbing (PGH-HC) and partial graph heuristic with modified great deluge algorithm (PGH-mGD) into solving the examination timetabling. The proposed approaches are tested on two benchmark datasets, namely Toronto dataset and the Second International Timetabling Competition (ITC2007) dataset. Experimental results demonstrate that the proposed approaches are able to produce quality solutions compared to traditional approaches for all instances of the datasets. Additionally, while compared with the state-of-the-art algorithms, our proposed approaches generally are able to produce competitive results and even outperform some of the reported results found in the scientific literature.
format	Thesis
qualification_level	Master's degree
author	Mandal, Ashis Kumar
author_facet	Mandal, Ashis Kumar
author_sort	Mandal, Ashis Kumar
title	Partial examination assignment approaches for solving examination timetabling problems
title_short	Partial examination assignment approaches for solving examination timetabling problems
title_full	Partial examination assignment approaches for solving examination timetabling problems
title_fullStr	Partial examination assignment approaches for solving examination timetabling problems
title_full_unstemmed	Partial examination assignment approaches for solving examination timetabling problems
title_sort	partial examination assignment approaches for solving examination timetabling problems
granting_institution	Universiti Malaysia Pahang
granting_department	Faculty of Computer System & Software Engineering
publishDate	2016
url	http://umpir.ump.edu.my/id/eprint/25157/1/Partial%20examination%20assignment%20approaches%20for%20solving%20examination%20timetabling.pdf
_version_	1783732089688948736

Partial examination assignment approaches for solving examination timetabling problems

Similar Items