An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables
In this paper, we present an investigation into using fuzzy methodologies to guide the construction of high quality feasible examination timetabling solutions. The provision of automated solutions to the examination timetabling problem is achieved through a combination of construction and improvemen...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2009
|
| Subjects: | |
| Online Access: | http://eprints.utm.my/id/eprint/7848/3/HishammudinAsmuni2009_AnInvestigationOfFuzzyMultipleHeuristicOrderings.pdf http://eprints.utm.my/id/eprint/7848/ http://dx.doi.org/10.1016/j.cor.2007.12.007 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| id |
my.utm.7848 |
|---|---|
| record_format |
eprints |
| spelling |
my.utm.78482017-10-23T06:39:06Z http://eprints.utm.my/id/eprint/7848/ An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables Asmuni, Hishammuddin Burke, E. K. Garibaldi, J. M. McCollum, B. QA76 Computer software In this paper, we present an investigation into using fuzzy methodologies to guide the construction of high quality feasible examination timetabling solutions. The provision of automated solutions to the examination timetabling problem is achieved through a combination of construction and improvement. The enhancement of solutions through the use of techniques such as metaheuristics is, in some cases, dependent on the quality of the solution obtained during the construction process. With a few notable exceptions, recent research has concentrated on the improvement of solutions as opposed to focusing on investigating the ‘best’ approaches to the construction phase. Addressing this issue, our approach is based on combining multiple criteria in deciding on how the construction phase should proceed. Fuzzy methods were used to combine three single construction heuristics into three different pair wise combinations of heuristics in order to guide the order in which exams were selected to be inserted into the timetable solution. In order to investigate the approach, we compared the performance of the various heuristic approaches with respect to a number of important criteria (overall cost penalty, number of skipped exams, number of iterations of a rescheduling procedure required and computational time) on 12 well-known benchmark problems.We demonstrate that the fuzzy combination of heuristics allows high quality solutions to be constructed. On one of the 12 problems, we obtained lower penalty than any previously published constructive method and for all 12 we obtained lower penalty than when any of the single heuristics were used alone. Furthermore, we demonstrate that the fuzzy approach used less backtracking when constructing solutions than any of the single heuristics. We conclude that this novel fuzzy approach is a highly effective method for heuristically constructing solutions and, as such, has particular relevance to real-world situations in which the construction of feasible solutions is often a difficult task in its own right. Elsevier 2009-04 Article PeerReviewed application/pdf en http://eprints.utm.my/id/eprint/7848/3/HishammudinAsmuni2009_AnInvestigationOfFuzzyMultipleHeuristicOrderings.pdf Asmuni, Hishammuddin and Burke, E. K. and Garibaldi, J. M. and McCollum, B. (2009) An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables. Computers & Operations Research, 36 (4). pp. 981-1001. http://dx.doi.org/10.1016/j.cor.2007.12.007 10.1016/j.cor.2007.12.007 |
| institution |
Universiti Teknologi Malaysia |
| building |
UTM Library |
| collection |
Institutional Repository |
| continent |
Asia |
| country |
Malaysia |
| content_provider |
Universiti Teknologi Malaysia |
| content_source |
UTM Institutional Repository |
| url_provider |
http://eprints.utm.my/ |
| language |
English |
| topic |
QA76 Computer software |
| spellingShingle |
QA76 Computer software Asmuni, Hishammuddin Burke, E. K. Garibaldi, J. M. McCollum, B. An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables |
| description |
In this paper, we present an investigation into using fuzzy methodologies to guide the construction of high quality feasible examination timetabling solutions. The provision of automated solutions to the examination timetabling problem is achieved through a combination of construction and improvement. The enhancement of solutions through the use of techniques such as metaheuristics is, in some cases, dependent on the quality of the solution obtained during the construction process. With a few notable exceptions, recent research has concentrated on the improvement of solutions as opposed to focusing on investigating the ‘best’ approaches to the construction phase. Addressing this issue, our approach is based on combining multiple criteria in deciding on how the construction phase should proceed. Fuzzy methods were used to combine three single construction heuristics into three different pair wise combinations of heuristics in order to guide the order in which exams were selected to be inserted into the timetable solution. In order to investigate the approach, we compared the performance of the various heuristic approaches with respect to a number of important criteria (overall cost penalty, number of skipped exams, number of iterations of a rescheduling procedure required and computational time) on 12 well-known benchmark problems.We demonstrate that the fuzzy combination of heuristics allows high quality solutions to be constructed. On one of the 12 problems, we obtained lower penalty than any previously published constructive method and for all 12 we obtained lower penalty than when any of the single heuristics were used alone. Furthermore, we demonstrate that the fuzzy approach used less backtracking when constructing solutions than any of the single heuristics. We conclude that this novel fuzzy approach is a highly effective method for heuristically constructing solutions and, as such, has particular relevance to real-world situations in which the construction of feasible solutions is often a difficult task in its own right. |
| format |
Article |
| author |
Asmuni, Hishammuddin Burke, E. K. Garibaldi, J. M. McCollum, B. |
| author_facet |
Asmuni, Hishammuddin Burke, E. K. Garibaldi, J. M. McCollum, B. |
| author_sort |
Asmuni, Hishammuddin |
| title |
An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables |
| title_short |
An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables |
| title_full |
An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables |
| title_fullStr |
An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables |
| title_full_unstemmed |
An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables |
| title_sort |
investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables |
| publisher |
Elsevier |
| publishDate |
2009 |
| url |
http://eprints.utm.my/id/eprint/7848/3/HishammudinAsmuni2009_AnInvestigationOfFuzzyMultipleHeuristicOrderings.pdf http://eprints.utm.my/id/eprint/7848/ http://dx.doi.org/10.1016/j.cor.2007.12.007 |
| _version_ |
1643644864958562304 |
| score |
13.211869 |