research-article

An analysis of representations for hyper-heuristics for the uncapacitated examination timetabling problem in a genetic programming system

Author:

SAICSIT '08: Proceedings of the 2008 annual research conference of the South African Institute of Computer Scientists and Information Technologists on IT research in developing countries: riding the wave of technology

Pages 188 - 192

https://doi.org/10.1145/1456659.1456681

Published: 06 October 2008 Publication History

Get Access

Abstract

Earlier research into the examination timetabling problem focused on applying different methodologies to generate solutions to the problem. More recently research has been directed at developing hyper-heuristic systems for timetable construction. Hyper-heuristic systems are used to decide which examination to schedule next during the timetable construction process and aim at allocating those examinations that are most difficult to schedule first. This study investigates using a genetic programming based hyper-heuristic system to evolve heuristic combinations for the uncapacitated examination timetabling problem. More specifically it presents and evaluates three different representations for heuristic combinations in a genetic programming system. The performance of the genetic programming based system using the different representations is applied to three examination timetabling problems with different characteristics and the performance on these problems is compared. The results obtained are also compared to that of other hyper-heuristic systems applied to the same problems.

References

[1]

Asumni, H., Burke, E. K., and Garibaldi, J. M. Fuzzy Multiple Ordering Criteria for Examination Timetabling. In: Burke EK, Trick M (Eds.), Selected Papers from the 5^th International Conference on the Theory and Practice of Automated Timetabling (PATAT 2004)- The Theory and Practice of Automated Timetabling V, Lecture Notes in Computer Science, Vol. 3616. Springer-Berlin, 2005, 795--825.

Google Scholar

[2]

Burke E., Hart E., Kendall G., Newall J., Ross P., and Schulenburg S. Hyper-Heuristics: An Emerging Direction in Modern Research. In Handbook of Metaheuristics, Chapter 16. Kluwer Academic Publishers, 2003, 457--474.

Google Scholar

[3]

Burke E. K., Dror M., Petrovic S., and Qu R. Hybrid Graph Heuristics with a Hyper-Heuristic Approach to Exam Timetabling Problems. In: Golden B. L., Raghavan S., Wasil E. A. (Eds.), The Next Wave in Computing, Optimization, and Decision Technologies - Conference Volume of the 9^th Informs Computing Society Conference. Springer, 2005, 79 -- 91.

Google Scholar

[4]

Burke E. K., McCollum B., Meisels A., Petrovic S., and Qu R. A Graph-Based Hyper-Heuristic for Educational Timetabling Problems. European Journal of Operational Research, 176. 2007, 177 -- 192.

Google Scholar

[5]

Carter M. W., Laporte G., and Lee S. Y. Examination Timetabling: Algorithmic Strategies and Applications. The Journal of the Operational Research Society, 47, 3. 1996, 373 -- 383.

Google Scholar

[6]

Koza J. R. Genetic Programming I: On the Programming of Computers by Natural Selection, MIT Press, 1992.

Digital Library

Google Scholar

[7]

Qu R., and Burke E. K. Hybrid Neighbourhood HyperHeuristic for Exam Timetabling Problems. In: Proceedings of the MIC2005: The Sixth Metaheuristics International Conference, Vienna, Austria. 2005.

Google Scholar

[8]

Qu R., Burke E. K., McCollum B., Merlot L. T. G., and Lee S. Y. A Survey of Search Methodologies and Automated Approaches for Examination Timetabling. Computer Science Technical Report No. NOTTCS-TR-2006-4, UK, 2006.

Google Scholar

Cited By

View all

Barros Rde Carvalho AFreitas ABarros Rde Carvalho AFreitas A(2015)Evolutionary Algorithms and Hyper-HeuristicsAutomatic Design of Decision-Tree Induction Algorithms10.1007/978-3-319-14231-9_3(47-58)Online publication date: 5-Feb-2015
https://doi.org/10.1007/978-3-319-14231-9_3
Pillay N(2014)A review of hyper-heuristics for educational timetablingAnnals of Operations Research10.1007/s10479-014-1688-1239:1(3-38)Online publication date: 9-Aug-2014
https://doi.org/10.1007/s10479-014-1688-1
Sabar NAyob MQu RKendall G(2012)A graph coloring constructive hyper-heuristic for examination timetabling problemsApplied Intelligence10.1007/s10489-011-0309-937:1(1-11)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/s10489-011-0309-9
Show More Cited By

Index Terms

An analysis of representations for hyper-heuristics for the uncapacitated examination timetabling problem in a genetic programming system
1. Computing methodologies
  1. Artificial intelligence
    1. Philosophical/theoretical foundations of artificial intelligence

Recommendations

A study into the use of hyper-heuristics to solve the school timetabling problem
SAICSIT '10: Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists

Research in the domain of school timetabling has not developed as rapidly as other areas of educational timetabling such as university course and examination timetabling. A lot of research has been conducted into using hyper-heuristics to solve the ...
A comparative study of hyper-heuristics for solving the school timetabling problem
SAICSIT '13: Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference

Hyper-heuristics have proven to be an effective means of obtaining generalized solutions to optimization problems. One such domain in which they have been a success is educational timetabling. However, all the research in this area has focused on ...
A genetic programming approach to the generation of hyper-heuristics for the uncapacitated examination timetabling problem
EPIA'07: Proceedings of the aritficial intelligence 13th Portuguese conference on Progress in artificial intelligence

Research in the field of examination timetabling has developed in two directions. The first looks at applying various methodologies to induce examination timetables. The second takes an indirect approach to the problem and examines the generation of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

October 2008

304 pages

ISBN:9781605582863

DOI:10.1145/1456659

Program Chairs:
Reinhardt Botha
Nelson Mandela Metropolitan University, South Africa
,
Charmain Cilliers
Nelson Mandela Metropolitan University, South Africa

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAICSIT '08

Sponsor:

Microsoft

SAICSIT '08: 2008 Annual Conference of the South African Institute of Computer Scientists and Information Technologists

October 6 - 8, 2008

Wilderness, South Africa

Acceptance Rates

Overall Acceptance Rate 187 of 439 submissions, 43%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
260
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Barros Rde Carvalho AFreitas ABarros Rde Carvalho AFreitas A(2015)Evolutionary Algorithms and Hyper-HeuristicsAutomatic Design of Decision-Tree Induction Algorithms10.1007/978-3-319-14231-9_3(47-58)Online publication date: 5-Feb-2015
https://doi.org/10.1007/978-3-319-14231-9_3
Pillay N(2014)A review of hyper-heuristics for educational timetablingAnnals of Operations Research10.1007/s10479-014-1688-1239:1(3-38)Online publication date: 9-Aug-2014
https://doi.org/10.1007/s10479-014-1688-1
Sabar NAyob MQu RKendall G(2012)A graph coloring constructive hyper-heuristic for examination timetabling problemsApplied Intelligence10.1007/s10489-011-0309-937:1(1-11)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/s10489-011-0309-9
Pillay NKotzé Pvan der Merwe AGerber A(2010)A study into the use of hyper-heuristics to solve the school timetabling problemProceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists10.1145/1899503.1899532(258-264)Online publication date: 11-Oct-2010
https://dl.acm.org/doi/10.1145/1899503.1899532
Pillay NKotzé Pvan der Merwe AGerber A(2010)An empirical study into the structure of heuristic combinations in an evolutionary algorithm hyper-heuristic for the examination timetabling problemProceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists10.1145/1899503.1899531(251-257)Online publication date: 11-Oct-2010
https://dl.acm.org/doi/10.1145/1899503.1899531
Garrido PRiff M(2010)DVRP: a hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristicJournal of Heuristics10.1007/s10732-010-9126-216:6(795-834)Online publication date: 12-Feb-2010
https://doi.org/10.1007/s10732-010-9126-2

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A study into the use of hyper-heuristics to solve the school timetabling problem

A comparative study of hyper-heuristics for solving the school timetabling problem

A genetic programming approach to the generation of hyper-heuristics for the uncapacitated examination timetabling problem