文章基本信息

标题：PARTIAL GRAPH HEURISTIC WITH HILL CLIMBING FOR EXAMINATION TIMETABLING PROBLEM
本地全文：下载
作者：ASHIS KUMAR MANDAL ; M N M KAHAR
期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2016
卷号：88
期号：2
出版社：Journal of Theoretical and Applied
摘要：Generating an examination timetable for an institution is a challenging and time-consuming task due to its inherent complexity and lots of constraints associated with scheduling the exams. In fact, it is a combinatorial optimization problem that requires heuristic searches to converge the solution into an optimized area. This paper presents combining the partial graph heuristic with hill climbing search (PGH-HC) to solve the examination timetabling problem. The approach first orders the exams using graph heuristics, and partially selected exams, which are generated based on predefined constant called exam assignment value (EAV), are assigned to timeslots and / or rooms. Next, the hill climbing search is employed to improve the partially scheduled exams. The above process continues until all exams have been scheduled. The overall aim here is to devise a straightforward approach which employs tuning of fewer parameters in solving the exam timetabling problem. Two benchmark examination timetabling datasets, Toronto un-capacitated datasets and ITC2007 capacitated datasets are considered for measuring the efficiency of the proposed method. We analyse the PGH-HC with different EAV, graph heuristics and termination criteria on these benchmark datasets. Experimental results reveal that, in general, PGH-HC with relatively a smaller EAV and a higher number of iterations (i.e. longer termination durations) is found to produce better quality solutions for all problem instances. Besides, the proposed approach is able to generate better quality solutions for all problem instances compared to traditional graph heuristic with hill climbing search (TGH-HC) and produce competitive results while comparing with the state-of-the-art approaches.
关键词：Combinatorial optimization problem; graph heuristics; hill climbing; scheduling; Timetabling