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

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.
• 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.
• 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.
• 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.
• 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.
• 6: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 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.
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory

Keywords:
examination timetabling, genetic programming, hyper-heuristics