×

A graph-based hyper-heuristic for educational timetabling problems. (English) Zbl 1137.90602

Summary: An investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyper-heuristic framework, a tabu search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the tabu search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.

MSC:

90B90 Case-oriented studies in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C90 Applications of mathematical programming

Software:

Hyperheuristics
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abdullah, S., Ahmadi, S., Burke, E.K., Dror, M., 2004. Investigating Ahuja-Orlin’s large neighbourhood search for examination timetabling. Technical Report NOTTCS-TR-2004-8, School of CSiT, University of Nottingham, UK.; Abdullah, S., Ahmadi, S., Burke, E.K., Dror, M., 2004. Investigating Ahuja-Orlin’s large neighbourhood search for examination timetabling. Technical Report NOTTCS-TR-2004-8, School of CSiT, University of Nottingham, UK. · Zbl 1170.90383
[2] Abramson, D.; Krishnamoorthy, M.; Dang, H., Simulated annealing cooling schedules for the school timetabling problem, Asia-Pacific Journal of Operational Research, 16, 1-22 (1999) · Zbl 1053.90508
[3] Asmuni, H., Burke, E.K., Garibaldi, J., 2005. Fuzzy multiple ordering criteria for examination timetabling. In: Burke, E.K., Trick, M. (Eds.), Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 3616, pp. 344-354.; Asmuni, H., Burke, E.K., Garibaldi, J., 2005. Fuzzy multiple ordering criteria for examination timetabling. In: Burke, E.K., Trick, M. (Eds.), Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 3616, pp. 344-354.
[4] Banks, D., Beek, P., Meisles, A., 1998. A heuristic incremental modelling approach to course timetabling. In: Proceedings of the 12th Canadian Conference on Artificial Intelligence, pp. 16-29.; Banks, D., Beek, P., Meisles, A., 1998. A heuristic incremental modelling approach to course timetabling. In: Proceedings of the 12th Canadian Conference on Artificial Intelligence, pp. 16-29.
[5] Bardadym, V., Computer-aided school and university timetabling: The new wave, (Burke, E. K.; Ross, P., Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 1153 (1996)), 22-45
[6] Beddoe, G., Petrovic, S., in press. Determining feature weights using a genetic algorithm in a case-based reasoning approach to personnel rostering. European Journal of Operational Research.; Beddoe, G., Petrovic, S., in press. Determining feature weights using a genetic algorithm in a case-based reasoning approach to personnel rostering. European Journal of Operational Research. · Zbl 1142.90393
[7] Brelaz, D., New methods to color the vertices of a graph, Communications of the ACM, 22, 4, 251-256 (1979) · Zbl 0394.05022
[8] (Burke, E. K.; Carter, M., Selected Papers from the 2nd International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 2nd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 1408 (1998))
[9] (Burke, E. K.; De Causmaecker, P., Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 2740 (2003))
[10] (Burke, E. K.; Erben, W., Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 2079 (2001)) · Zbl 0968.68560
[11] Burke, E. K.; Newall, J., A multi-stage evolutionary algorithm for the timetabling problem, The IEEE Transactions on Evolutionary Computation, 3, 1, 63-74 (1999)
[12] Burke, E. K.; Newall, J., Enhancing timetable solutions with local search methods, (Burke, E. K.; De Causmaecker, P., Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 2740 (2003)), 195-206
[13] Burke, E. K.; Petrovic, S., Recent research directions in automated timetabling, European Journal of Operational Research, 140, 2, 266-280 (2002) · Zbl 1001.90030
[14] (Burke, E. K.; Ross, P., Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 1153 (1996))
[15] Burke, E.K., Trick, M. (Eds.), 2005. Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, Pittsburg PA, USA, August 2004. Lecture Notes in Computer Science, vol. 3616.; Burke, E.K., Trick, M. (Eds.), 2005. Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, Pittsburg PA, USA, August 2004. Lecture Notes in Computer Science, vol. 3616.
[16] Burke, E. K.; Newall, J.; Weare, R., A memetic algorithm for university exam timetabling, (Burke, E. K.; Ross, P., Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 1153 (1996)), 241-250
[17] Burke, E. K.; Jackson, S.; Kingston, H.; Weare, F., Automated timetabling: The state of the art, The Computer Journal, 40, 9, 565-571 (1997)
[18] Burke, E. K.; Newall, J.; Weare, R., Initialization strategies and diversity in evolutionary timetabling, Evolutionary Computation, 6, 1, 81-103 (1998)
[19] Burke, E. K.; MacCarthy, B.; Petrovic, S.; Qu, R., Structured cases in case-based reasoning—Re-using and adapting cases for time-tabling problems, Knowledge-Based Systems, 13, 2-3, 159-165 (2000)
[20] Burke, E. K.; MacCarthy, B.; Petrovic, S.; Qu, R., Case-based reasoning in course timetabling: An attribute graph approach, (David, A.; Watson, I., Case-Based Reasoning Research and Development. Case-Based Reasoning Research and Development, Lecture Notes in Artificial Intelligence, vol. 2080 (2001)), 90-104 · Zbl 0987.68880
[21] Burke, E. K.; Kendall, G.; Newall, J.; Hart, E.; Ross, P.; Schulenburg, S., Hyper-heuristics: An emerging direction in modern search technology, (Glover, F.; Kochenberger, G., Handbook of Meta-Heuristics (2003), Kluwer), 457-474 · Zbl 1102.90377
[22] Burke, E. K.; Kendall, G.; Soubeiga, E., A tabu search hyperheuristic for timetabling and rostering, Journal of Heuristics, 9, 6, 451-470 (2003)
[23] Burke, E. K.; MacCarthy, B.; Petrovic, S.; Qu, R., Knowledge discovery in hyper-heuristic using case-based reasoning on course timetabling, (Burke, E. K.; De Causmaecker, P., Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 2740 (2003)), 90-103
[24] Burke, E. K.; Bykov, Y.; Newall, J.; Petrovic, S., A time-predefined local search approach to exam timetabling problems, IIE Transactions on Operations Engineering, 36, 6, 509-528 (2004)
[25] Burke, E. K.; De Causmaecker, P.; Vanden Berghe, G.; Van Landeghem, H., The state of the art of nurse rostering, Journal of Scheduling, 7, 6, 441-499 (2004) · Zbl 1154.90422
[26] Burke, E. K.; Kingston, J.; de Werra, D., Applications to timetabling, (Gross, J.; Yellen, J., Handbook of Graph Theory (2004), Chapman Hall/CRC Press), 445-474
[27] Burke, E. K.; Dror, M.; Petrovic, S.; Qu, R., Hybrid graph heuristics within a hyper-heuristic approach to exam timetabling problems, (Golden, B. L.; Raghavan, S.; Wasil, E. A., The Next Wave in Computing, Optimization, and Decision Technologies (2005), Springer), 79-91
[28] Burke, E. K.; Landa Silva, J. D.; Soubeiga, E., Multi-objective hyper-heuristic approaches for space allocation and timetabling, (Ibaraki, T.; Nonobe, K.; Yagiura, M., Meta-heuristics: Progress as Real Problem Solvers (2005), Springer), 129-158
[29] Burke, E.K., MacCarthy, B., Petrovic, S., Qu, R., in press. Multiple-retrieval case-based reasoning for course timetabling problems. Journal of Operations Research Society.; Burke, E.K., MacCarthy, B., Petrovic, S., Qu, R., in press. Multiple-retrieval case-based reasoning for course timetabling problems. Journal of Operations Research Society. · Zbl 1090.90100
[30] Burke, E. K.; Petrovic, S.; Qu, R., Case based heuristic selection for timetabling problems, Journal of Scheduling, 2, 9 (2006) · Zbl 1090.90100
[31] Caramia, M.; Dell’Olmo, P.; Italiano, G., New algorithms for examination timetabling, (Naher, S.; Wagner, D., Algorithm Engineering 4th International Workshop, WAE 2000. Algorithm Engineering 4th International Workshop, WAE 2000, Lecture Notes in Computer Science, vol. 1982 (2001)), 230-241
[32] Carter, M., A lagrangian relaxation approach to the classroom assignment problem, INFOR, 27, 2, 230-246 (1986)
[33] Carter, M.; Laporte, G., Recent developments in practical exam timetabling, (Burke, E. K.; Ross, P., Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 1153 (1996)), 3-21
[34] Carter, M.; Laporte, G., Recent developments in practical course timetabling, (Burke, E. K.; Ross, P., Selected Papers from the 2nd International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 2nd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 1408 (1998)), 3-19
[35] Carter, M.; Laporte, G.; Lee, S., Examination timetabling: Algorithmic strategies and applications, Journal of Operations Research Society, 47, 373-383 (1996)
[36] Casey, S.; Thompson, J., GRASPing the examination scheduling problem, (Burke, E. K.; De Causmaecker, P., Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 2740 (2003)), 232-246
[37] Costa, D., A tabu search for computing an operational timetable, European Journal of Operational Research, 76, 98-110 (1994) · Zbl 0809.90075
[38] Cheang, B.; Li, H.; Lim, A.; Rodrigues, B., Nurse rostering problems: A bibliographic survey, European Journal of Operational Research, 151, 3, 447-460 (2003) · Zbl 1045.90027
[39] Côté, P.; Wong, T.; Sabourin, R., Application of a hybrid multi-objective evolutionary algorithm to the uncapacitated exam proximity problem, (Burke, E. K.; Trick, M., Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 3616 (2005), Springer), 294-312
[40] de Werra, D., Graphs, hypergraphs and timetabling, Methods of Operations Research., 49, 201-213 (1985) · Zbl 0569.90042
[41] Deris, B.; Omatu, S.; Ohta, H.; Samat, D., University timetabling by constraint-based reasoning: A case study, Journal of Operational Research Society, 48, 12, 1178-1190 (1997) · Zbl 0895.90115
[42] Di Gaspero, L.; Schaerf, A., Tabu search techniques for examination timetabling, (Burke, E. K.; Erben, W., Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 2079 (2001)), 104-117 · Zbl 0982.68784
[43] Dowsland, K., Off the peg or made to measure, (Burke, E. K.; Carter, M., Selected Papers from the 2nd International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 2nd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 1408 (1998)), 37-52
[44] Dowsland, K., Soubeiga, E., Burke, E.K., in press. A simulated annealing hyper-heuristic for determining shipper sizes. European Journal of Operational Research, doi:10.1016/j.ejor.2005.03.058; Dowsland, K., Soubeiga, E., Burke, E.K., in press. A simulated annealing hyper-heuristic for determining shipper sizes. European Journal of Operational Research, doi:10.1016/j.ejor.2005.03.058 · Zbl 1127.90007
[45] Easton, K.; Nemhauser, G.; Trick, M., Sports scheduling, (Leung, J., Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004), CRC Press), (Chapter 52)
[46] Erben, W., A grouping genetic algorithm for graph coloring and exam timetabling, (Burke, E. K.; Erben, W., Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 2079 (2001)), 132-158 · Zbl 0982.68512
[47] Gaw, A., Rattadilok, P., Kwan, R.S., 2005. Distributed choice function hyperheuristics for timetabling and scheduling. In: Burke, E.K., Trick, M. (Eds.), Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 3616, pp. 51-70.; Gaw, A., Rattadilok, P., Kwan, R.S., 2005. Distributed choice function hyperheuristics for timetabling and scheduling. In: Burke, E.K., Trick, M. (Eds.), Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling. Lecture Notes in Computer Science, vol. 3616, pp. 51-70.
[48] Glover, F.; Kochenberger, G., Handbook of Metaheuristics (2003), Kluwer · Zbl 1058.90002
[49] Han, L., Kendall, G., 2003. Investigation of a tabu assisted hyper-heuristic genetic algorithm. In: Congress on Evolutionary Computation, Canberra, Australia, pp. 2230-2237.; Han, L., Kendall, G., 2003. Investigation of a tabu assisted hyper-heuristic genetic algorithm. In: Congress on Evolutionary Computation, Canberra, Australia, pp. 2230-2237.
[50] Kendall, G., Cowling, P., Soubeiga, E., 2002. Choice function and random hyperheuristics. In: Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning, pp. 667-671.; Kendall, G., Cowling, P., Soubeiga, E., 2002. Choice function and random hyperheuristics. In: Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning, pp. 667-671. · Zbl 1044.68749
[51] Kwan, R., Bus and train driver scheduling, (Leung, J., Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004), CRC Press), (Chapter 51)
[52] (Leake, D., Case-based Reasoning: Experiences, Lessons and Future Directions (1996), AAAI Press: AAAI Press Menlo Park, CA)
[53] Lewis, R., Paechter, B., 2004. New crossover operators for timetabling with evolutionary algorithms. In: 5th International Conference on Recent Advances in Soft Computing, Nottingham, UK, vol. 5, pp. 189-195.; Lewis, R., Paechter, B., 2004. New crossover operators for timetabling with evolutionary algorithms. In: 5th International Conference on Recent Advances in Soft Computing, Nottingham, UK, vol. 5, pp. 189-195.
[54] Merlot, L.; Boland, N.; Hughes, B.; Stuckey, P., A hybrid algorithm for the examination timetabling problem, (Burke, E. K.; De Causmaecker, P., Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling. Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 2740 (2003)), 207-231
[55] Nonobe, K.; Ibaraki, T., A tabu search approach to the constraint satisfaction problem as a general problem solver, European Journal of Operational Research, 106, 599-623 (1998) · Zbl 0991.90102
[56] Petrovic, S.; Burke, E. K., University timetabling, (Leung, J., Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004), CRC Press), (Chapter 45) · Zbl 1188.90090
[57] Qu, R., Burke, E.K., 2005. Hybrid variable neighborhood hyper-heuristics for exam timetabling problems. In: Meta-heuristic International Conference 2005 (MIC2005), Vienna, August 2005.; Qu, R., Burke, E.K., 2005. Hybrid variable neighborhood hyper-heuristics for exam timetabling problems. In: Meta-heuristic International Conference 2005 (MIC2005), Vienna, August 2005.
[58] Reeves, C. R., Modern heuristic techniques, (Rayward-Smith, V. J.; Osman, I. H.; Reeves, C. R.; Smith, G. D., Modern Heuristic Search Methods (1996)), 1-25
[59] Ross, P.; Marin Blasques, J. G.; Schulenburg, S.; Hart, E., Learning a procedure that can solve hard bin-packing problems: A new GA-based approach to hyper-heuristics, (Cantú-Paz, E.; etal., Genetic and Evolutionary Computation 2003. Genetic and Evolutionary Computation 2003, Lecture Notes in Computer Science, vol. 2724 (2003)), 1295-1306 · Zbl 1038.68841
[60] Schaerf, A., A survey of automated timetabling, Artificial Intelligence Review., 13, 2, 87-127 (1999)
[61] Socha, K.; Knowles, J.; Sampels, M., A max-min ant system for the university course timetabling problem, (Proceedings of the 3rd International Workshop on Ant Algorithms. Proceedings of the 3rd International Workshop on Ant Algorithms, Lecture Notes in Computer Science, vol. 2463 (2002)), 1-13
[62] Terashima-Marin, H.; Ross, P.; Valenzuela-Rendon, M., Evolution of constraint satisfaction strategies in examination timetabling, (Genetic Algorithms and Classifier Systems 1999 (2002)), 635-642
[63] Welsh, D. J.A.; Powell, M. B., The upper bound for the chromatic number of a graph and its application to timetabling problems, The Computer Journal, 11, 41-47 (1967) · Zbl 0147.15206
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.