Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem

Examination timetabling problem is a nontrivial task due to its NP-hard nature as well as the involvement of numerous constraints. Moreover, solving capacitated examination timetabling is more challenging compared to uncapacitated one. This paper implements graph heuristic with hill climbing search...

Full description

Bibliographic Details
Main Authors:	Ashis Kumar, Mandal, M. N. M., Kahar
Format:	Conference or Workshop Item
Language:	English English
Published:	2015
Subjects:	QA76 Computer software
Online Access:	http://umpir.ump.edu.my/id/eprint/11072/ http://umpir.ump.edu.my/id/eprint/11072/ http://umpir.ump.edu.my/id/eprint/11072/1/Combination%20of%20Graph%20Heuristic%20with%20Hill%20Climbing%20Search%20for%20Solving%20Capacitated%20Examination%20Timetabling%20Problem.pdf http://umpir.ump.edu.my/id/eprint/11072/7/fskkp-ashis%20kumar%20mandal-combination%20of%20graph%20heuristic.pdf

id	ump-11072
recordtype	eprints
spelling	ump-110722020-02-21T07:44:04Z http://umpir.ump.edu.my/id/eprint/11072/ Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem Ashis Kumar, Mandal M. N. M., Kahar QA76 Computer software Examination timetabling problem is a nontrivial task due to its NP-hard nature as well as the involvement of numerous constraints. Moreover, solving capacitated examination timetabling is more challenging compared to uncapacitated one. This paper implements graph heuristic with hill climbing search to solve the capacitated examination timetabling considering partial examination assignment concepts. The algorithm starts with ordering all the exams according to graph heuristic approach and then partial exams are considered for construction. Afterwards, the qualities of these exams are improved using hill climbing search. The entire process continues until scheduling all the exams. The effects of different graph heuristic orderings and exam assignment values on the quality of the solutions are studied. We test the proposed approach on ITC2007 benchmark exam datasets which contains highly constraint capacitated datasets. Experimental results reveal that the approach is able to produce quality solutions for all datasets and competitive results with competition results. 2015 Conference or Workshop Item PeerReviewed application/pdf en http://umpir.ump.edu.my/id/eprint/11072/1/Combination%20of%20Graph%20Heuristic%20with%20Hill%20Climbing%20Search%20for%20Solving%20Capacitated%20Examination%20Timetabling%20Problem.pdf application/pdf en http://umpir.ump.edu.my/id/eprint/11072/7/fskkp-ashis%20kumar%20mandal-combination%20of%20graph%20heuristic.pdf Ashis Kumar, Mandal and M. N. M., Kahar (2015) Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem. In: 4th International Conference on Software Engineering and Computer Systems (ICSECS 2015), 19-21 August 2015 , Kuantan, Pahang. pp. 118-123.. http://dx.doi.org/10.1109/ICSECS.2015.7333095
repository_type	Digital Repository
institution_category	Local University
institution	Universiti Malaysia Pahang
building	UMP Institutional Repository
collection	Online Access
language	English English
topic	QA76 Computer software
spellingShingle	QA76 Computer software Ashis Kumar, Mandal M. N. M., Kahar Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem
description	Examination timetabling problem is a nontrivial task due to its NP-hard nature as well as the involvement of numerous constraints. Moreover, solving capacitated examination timetabling is more challenging compared to uncapacitated one. This paper implements graph heuristic with hill climbing search to solve the capacitated examination timetabling considering partial examination assignment concepts. The algorithm starts with ordering all the exams according to graph heuristic approach and then partial exams are considered for construction. Afterwards, the qualities of these exams are improved using hill climbing search. The entire process continues until scheduling all the exams. The effects of different graph heuristic orderings and exam assignment values on the quality of the solutions are studied. We test the proposed approach on ITC2007 benchmark exam datasets which contains highly constraint capacitated datasets. Experimental results reveal that the approach is able to produce quality solutions for all datasets and competitive results with competition results.
format	Conference or Workshop Item
author	Ashis Kumar, Mandal M. N. M., Kahar
author_facet	Ashis Kumar, Mandal M. N. M., Kahar
author_sort	Ashis Kumar, Mandal
title	Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem
title_short	Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem
title_full	Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem
title_fullStr	Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem
title_full_unstemmed	Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem
title_sort	combination of graph heuristic with hill climbing search for solving capacitated examination timetabling problem
publishDate	2015
url	http://umpir.ump.edu.my/id/eprint/11072/ http://umpir.ump.edu.my/id/eprint/11072/ http://umpir.ump.edu.my/id/eprint/11072/1/Combination%20of%20Graph%20Heuristic%20with%20Hill%20Climbing%20Search%20for%20Solving%20Capacitated%20Examination%20Timetabling%20Problem.pdf http://umpir.ump.edu.my/id/eprint/11072/7/fskkp-ashis%20kumar%20mandal-combination%20of%20graph%20heuristic.pdf
first_indexed	2023-09-18T22:11:26Z
last_indexed	2023-09-18T22:11:26Z
_version_	1777415053537968128

Combination of Graph Heuristic with Hill Climbing Search for Solving Capacitated Examination Timetabling Problem

Similar Items