Adaptive linear combination of heuristic orderings in constructing examination timetables
In this paper, we investigate adaptive linear combinations of graph coloring heuristics with a heuristic modifier to address the examination timetabling problem. We invoke a normalisation strategy for each parameter in order to generalise the specific problem data. Two graph coloring heuristics were...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2014
|
| Online Access: | https://eprints.nottingham.ac.uk/3386/ |
| _version_ | 1848791027243024384 |
|---|---|
| author | Abdul-Rahman, Syariza Bargiela, Andrzej Burke, Edmund Özcan, Ender McCollum, Barry McMullan, Paul |
| author_facet | Abdul-Rahman, Syariza Bargiela, Andrzej Burke, Edmund Özcan, Ender McCollum, Barry McMullan, Paul |
| author_sort | Abdul-Rahman, Syariza |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | In this paper, we investigate adaptive linear combinations of graph coloring heuristics with a heuristic modifier to address the examination timetabling problem. We invoke a normalisation strategy for each parameter in order to generalise the specific problem data. Two graph coloring heuristics were used in this study (largest degree and saturation degree). A score for the difficulty of assigning each examination was obtained from an adaptive linear combination of these two heuristics and examinations in the list were ordered based on this value. The examinations with the score value representing the higher difficulty were chosen for scheduling based on two strategies. We tested for single and multiple heuristics with and without a heuristic modifier with different combinations of weight values for each parameter on the Toronto and ITC2007 benchmark data sets. We observed that the combination of multiple heuristics with a heuristic modifier offers an effective way to obtain good solution quality. Experimental results demonstrate that our approach delivers promising results. We conclude that this adaptive linear combination of heuristics is a highly effective method and simple to implement. |
| first_indexed | 2025-11-14T18:21:59Z |
| format | Article |
| id | nottingham-3386 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:21:59Z |
| publishDate | 2014 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-33862020-05-04T16:41:39Z https://eprints.nottingham.ac.uk/3386/ Adaptive linear combination of heuristic orderings in constructing examination timetables Abdul-Rahman, Syariza Bargiela, Andrzej Burke, Edmund Özcan, Ender McCollum, Barry McMullan, Paul In this paper, we investigate adaptive linear combinations of graph coloring heuristics with a heuristic modifier to address the examination timetabling problem. We invoke a normalisation strategy for each parameter in order to generalise the specific problem data. Two graph coloring heuristics were used in this study (largest degree and saturation degree). A score for the difficulty of assigning each examination was obtained from an adaptive linear combination of these two heuristics and examinations in the list were ordered based on this value. The examinations with the score value representing the higher difficulty were chosen for scheduling based on two strategies. We tested for single and multiple heuristics with and without a heuristic modifier with different combinations of weight values for each parameter on the Toronto and ITC2007 benchmark data sets. We observed that the combination of multiple heuristics with a heuristic modifier offers an effective way to obtain good solution quality. Experimental results demonstrate that our approach delivers promising results. We conclude that this adaptive linear combination of heuristics is a highly effective method and simple to implement. Elsevier 2014-01-16 Article PeerReviewed Abdul-Rahman, Syariza, Bargiela, Andrzej, Burke, Edmund, Özcan, Ender, McCollum, Barry and McMullan, Paul (2014) Adaptive linear combination of heuristic orderings in constructing examination timetables. European Journal of Operational Research, 232 (2). pp. 287-297. ISSN 0377-2217 http://www.sciencedirect.com/science/article/pii/S0377221713005596 doi:10.1016/j.ejor.2013.06.052 doi:10.1016/j.ejor.2013.06.052 |
| spellingShingle | Abdul-Rahman, Syariza Bargiela, Andrzej Burke, Edmund Özcan, Ender McCollum, Barry McMullan, Paul Adaptive linear combination of heuristic orderings in constructing examination timetables |
| title | Adaptive linear combination of heuristic orderings in constructing examination timetables |
| title_full | Adaptive linear combination of heuristic orderings in constructing examination timetables |
| title_fullStr | Adaptive linear combination of heuristic orderings in constructing examination timetables |
| title_full_unstemmed | Adaptive linear combination of heuristic orderings in constructing examination timetables |
| title_short | Adaptive linear combination of heuristic orderings in constructing examination timetables |
| title_sort | adaptive linear combination of heuristic orderings in constructing examination timetables |
| url | https://eprints.nottingham.ac.uk/3386/ https://eprints.nottingham.ac.uk/3386/ https://eprints.nottingham.ac.uk/3386/ |