Citation
Adaptive Selection of Heuristics within a GRASP for Exam Timetabling Problems. Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), 10-12 Aug 2009, Dublin, Ireland, pages 409-423, 2009.
Paper
Abstract
In this paper, we describe the development of a Greedy Random Adaptive Search Procedure (GRASP) where two low-level graph heuristics, Saturation Degree (SD) and Largest Weighted Degree (LWD) are dynamically hybridised in the construction phase to construct solutions for exam timetabling problems. The problem is initially solved using an intelligent adaptive LWD and SD graph hyper-heuristic which constructs the restricted candidate list (RCL) in the first phase of GRASP. It is observed that the size of the RCL used in each iteration affects the quality of the results obtained. In addition, the SD heuristic is essential to construct a RCL which leads to a feasible solution. However, SD does not perform well at the early stages of the construction. Therefore, LWD is used until a certain switching point is reached. The hyper-heuristic adaptively determines the size of the RCL in each iteration and the best switching point after evaluating the quality of the solutions produced. In the improvement phase of GRASP, it is observed that tabu search slightly improves the constructed solutions when compared to steepest descent but it takes a longer time. The approach adapts to all the benchmark problems tested. The comparison of this approach with state-of-the-art approaches indicates that it is a simple yet efficient technique. The results also indicate that the technique could adapt itself to construct good quality solutions for any timetabling problem with similar constraints.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2009-409-423-P, author = {E. K. Burke and R. Qu and A. Soghier},
title = {Adaptive Selection of Heuristics within a GRASP for Exam Timetabling Problems},
booktitle = {Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), 10-12 Aug 2009, Dublin, Ireland},
year = {2009},
editor = {J. Blazewicz and M. Drozdowski and G. Kendall and B. McCollum},
pages = {409--423},
note = {Paper},
abstract = {In this paper, we describe the development of a Greedy Random Adaptive Search Procedure (GRASP) where two low-level graph heuristics, Saturation Degree (SD) and Largest Weighted Degree (LWD) are dynamically hybridised in the construction phase to construct solutions for exam timetabling problems. The problem is initially solved using an intelligent adaptive LWD and SD graph hyper-heuristic which constructs the restricted candidate list (RCL) in the first phase of GRASP. It is observed that the size of the RCL used in each iteration affects the quality of the results obtained. In addition, the SD heuristic is essential to construct a RCL which leads to a feasible solution. However, SD does not perform well at the early stages of the construction. Therefore, LWD is used until a certain switching point is reached. The hyper-heuristic adaptively determines the size of the RCL in each iteration and the best switching point after evaluating the quality of the solutions produced. In the improvement phase of GRASP, it is observed that tabu search slightly improves the constructed solutions when compared to steepest descent but it takes a longer time. The approach adapts to all the benchmark problems tested. The comparison of this approach with state-of-the-art approaches indicates that it is a simple yet efficient technique. The results also indicate that the technique could adapt itself to construct good quality solutions for any timetabling problem with similar constraints.},
owner = {gxk},
timestamp = {2010.10.11},
webpdf = {2009-409-423-P.pdf} }