Case-based heuristic selection for timetabling problems. (English) Zbl 1154.90423
Summary: This paper presents a case-based heuristic selection approach for automated university course and exam timetabling. The method described in this paper is motivated by the goal of developing timetabling systems that are fundamentally more general than the current state of the art. Heuristics that worked well in previous similar situations are memorized in a case base and are retrieved for solving the problem in hand. Knowledge discovery techniques are employed in two distinct scenarios. Firstly, we model the problem and the problem solving situations along with specific heuristics for those problems. Secondly, we refine the case base and discard cases which prove to be non-useful in solving new problems. Experimental results are presented and analyzed. It is shown that case based reasoning can act effectively as an intelligent approach to learn which heuristics work well for particular timetabling situations. We conclude by outlining and discussing potential research issues in this critical area of knowledge discovery for different difficult timetabling problems.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
Case based reasoning; Course timetabling; Exam timetabling; Graph heuristics; Knowledge discovery; Meta-heuristicsSoftware:
HyperheuristicsReferences:
| [1] | Amintoosi, M. and J. Haddadina, ”Feature selection in a fuzzy student sectioning algorithm,” in Burke, E. K. and M. Trick, (eds.), The 5th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 3616, Springer-Verlag 2005, pp. 148–161. |
| [2] | Asmuni, H., E. K. Burke, and J. M. Garibaldi, ”Fuzzy multiple ordering criteria for examination timetabling.” inBurke, E. K. and M. Trick, (eds.), The 5th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 3616, Springer-Verlag 2005, pp. 334–354. |
| [3] | Beddoe, G. and S. Petrovic, ”Determining feature weights using a genetic algorithm in a case-based reasoning approach to personnel rostering,” Accepted for publication in the European Journal of Operational Research, (2005). |
| [4] | Burke, E. K. and M. Carter (eds.), The 2nd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 1408. Springer-Verlag, 1998. |
| [5] | Burke, E. K. and P de Causmaecker (eds.), The 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 2740. Springer-Verlag, 2002. |
| [6] | Burke, E. K., P. De Causmaecker, G. Vanden Berghe, and H. Van Landeghem, ”The state of the art of nurse rostering,” Journal of Scheduling, 7(6), 441–499, (2004a). · Zbl 1154.90422 · doi:10.1023/B:JOSH.0000046076.75950.0b |
| [7] | Burke, E. K., D. De Werra, and J. Kingston, ”Applications to timetabling,” in J. Gross and J. Yellen (eds.), Handbook of Graph Theory. Chapman Hall/CRC Press 2004b, pp. 445–474. |
| [8] | Burke, E. K., M. Dror, S. Petrovic, and R. Qu, ”Hybrid graph heuristics within a hyper-heuristic approach to exam timetabling problems,” in B.L. Golden, S. Raghavan, and E. A. Wasil (eds.), The Next Wave in Computing, Optimization, and Decision Technologies, Conference Volume of the 9th informs Computing Society Conference Springer 2005, pp. 79–91. |
| [9] | Burke, E. K., A. Eckersley, B. McCollum, S. Petrovic, and R. Qu, ”Similarity measures for exam timetabling problem,” 1st Multidisciplinary Intl. Conf. on Scheduling: Theory and Applications, Nottingham, UK, Aug 13–16 2003a, Vol. 1, pp. 120–136,. · Zbl 1188.90090 |
| [10] | Burke, E. K. and W Erben (eds.), ”The 3rd International Conference on the Practice and Theory of Automated Timetabling,” Lecture Notes in Computer Science 2079, Springer-Verlag 2000. |
| [11] | Burke, E. K., E. Hart, G. Kendall, J. Newall, P. Ross, and S. Schulenburg, ”Hyper-heuristics: An emerging direction in modern search technology,” in F. Glover and G. Kochenberger (eds.), Handbook of Meta-Heuristics, Kluwer. pp. 457–474 2003b. · Zbl 1102.90377 |
| [12] | Burke, E. K., K. S. Jackson, J. H. Kingston, and R. F. Weare, ”Automated timetabling: The sate of the art,” The Computer Journal, 40(9), 565–571 (1997). · doi:10.1093/comjnl/40.9.565 |
| [13] | Burke, E. K., G. Kendall, and E. Soubeiga, ”A tabu-search hyperheuristic for timetabling and rostering,” Journal of Heuristics, 9(6), 451–470 (2003c). · doi:10.1023/B:HEUR.0000012446.94732.b6 |
| [14] | Burke, E. K., B. L. MacCarthy, S. Petrovic, and R. Qu, ”Structured cases in case-based reasoning-re-using and adapting cases for time-tabling problems,” Knowledge-Based Systems, 13(2–3), 159–165 (2000). · doi:10.1016/S0950-7051(00)00057-5 |
| [15] | Burke, E. K., B. L. MacCarthy, S. Petrovic, and R. Qu, ”Case-based reasoning in course timetabling: an attribute graph approach,” in D. W. Aha and I. Watson (eds.), Case-Based Reasoning Research and Development, Lecture Notes in Artificial Intelligence 2080, 2001 pp. 90–104. · Zbl 0987.68880 |
| [16] | Burke, E. K., B. MacCarthy, S. Petrovic, and R. Qu, ”Multiple-retrieval case-based reasoning for course timetabling problems,” Journal of the Operational Research Society, 57(2), 148–162 (2006a). · Zbl 1090.90100 |
| [17] | Burke, E. K., B. MacCarthy, S. Petrovic, and R. Qu, ”Knowledge discovery in hyper-heuristic using case-based reasoning on course timetabling,” in Burke, E. K. and P de Causmaecker (eds.), The 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 2740. Springer-Verlag, 2002 pp. 277–288. |
| [18] | Burke, E. K., B. McCollum, A. Meisels, S. Petrovic, and R. Qu, ”A graph-based hyper heuristic for educational timetabling problems,” (to appear) in the European Journal of Operational Research (2006b). · Zbl 1137.90602 |
| [19] | Burke, E. K. and J. P. Newall, ”A multi-stage evolutionary algorithm for the timetable problem,” IEEE Transactions on Evolutionary Computation, 3(1), 63–74 (1999). · doi:10.1109/4235.752921 |
| [20] | Burke, E.K., J. Newall, and R. Weare, ”A simple heuristically guided search for the timetabling problem,” in Proceedings of the International ICSC Symposium on Engineering of Intelligent Systems, 1998 pp. 574–579. |
| [21] | Burke, E. K. and S. Petrovic, ”Recent research directions in automated timetabling,” European Journal of Operational Research, 140(2), 266–280 (2002). · Zbl 1001.90030 · doi:10.1016/S0377-2217(02)00069-3 |
| [22] | Burke, E. K. and P. Ross, (eds.), The 1st international conference on the practice and theory of automated timetabling, Lecture Notes in Computer Science 1153, Springer-Verlag (1996). |
| [23] | Burke, E. K. and M. Trick, (eds.), The 5th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 3616, Springer-Verlag 2005. |
| [24] | Carrasco, M. P. and M. V. Pato, ”A multiobjective genetic algorithm for the class/teacher timetabling problem,” in Burke, E. K. and P de Causmaecker (eds.), The 4th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 2740. Springer-Verlag, 2002, pp. 179–192. · Zbl 0982.68523 |
| [25] | Carter, M. W., ”A lagrangian relaxation approach to the classroom assignment problem,” IFOR, 27(2), 230–246 (1986). · Zbl 0668.90041 |
| [26] | Carter, M. W. and G. Laporte, ”Recent developments in practical exam timetabling,” in Burke, E. K. and P. Ross, (eds.), The 1st international conference on the practice and theory of automated timetabling, Lecture Notes in Computer Science 1153, Springer-Verlag, (1996) pp. 3–21. |
| [27] | Carter, M. W. and G. Laporte, ”Recent developments in practical course timetabling,” in Burke, E. K. and M. Carter (eds.), The 2nd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 1408. Springer-Verlag, 1998, pp. 3–19. |
| [28] | Carter, M. W., G. Laporte and S. Y. Lee, ”Examination timetabling: Algorithmic strategies and applications,” Journal of Operations Research Society, 74, 373–383 (1996). |
| [29] | Chan, P. and G. Weil, ”Cyclic staff scheduling using constraint logic programming,” in Burke, E. K. and W Erben (eds.), ”The 3rd International Conference on the Practice and Theory of Automated Timetabling,” Lecture Notes in Computer Science 2079, Springer-Verlag 2000, pp. 159–175. · Zbl 0982.68607 |
| [30] | Colorni, A., M. Dorigo, and V. Maniezzo, ”Metaheuristics for school timetabling,” Computational Optimisation and Applications, 9(3), 277–298 (1998). · Zbl 0897.90124 |
| [31] | Costa, D., ”A tabu search algorithm for computing an operational timetable,” European Journal of Operational Research, 76, 98–110 (1994). · Zbl 0809.90075 · doi:10.1016/0377-2217(94)90009-4 |
| [32] | Cunningham, P. and B. Smyth, ”Case-based reasoning in scheduling: reusing solution components,” The International Journal of Production Research, 35, 2947–2961 (1997). · Zbl 0946.90524 · doi:10.1080/002075497194237 |
| [33] | Dorn, J., ”Case-based reactive scheduling,” Technical Report CD-TR 95/75. Vienna University of Technology, Institut for Information Systems (1995). · Zbl 0875.68769 |
| [34] | Dowsland, K. A., ”Off the peg or made to measure,” in Burke, E. K. and M. Carter (eds.), The 2nd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 1408. Springer-Verlag, 1998, pp. 37–52 . |
| [35] | Easton, K., G. Nemhauser, and M. Tick, ”Sports Scheduling,” in Leung JYT (ed.), Handbook of Scheduling, Chapter 52. CRC Press LLC (2004). |
| [36] | Erben, W., ”A grouping genetic algorithm for graph coloring and exam timetabling,” in Burke, E. K. and W Erben (eds.), ”The 3rd International Conference on the Practice and Theory of Automated Timetabling,” Lecture Notes in Computer Science 2079, Springer-Verlag 2000, pp. 132–158. · Zbl 0982.68512 |
| [37] | Fayyad, U., G. Piatetsky-Shapiro, P. Smyth, and R. (eds.), Uthurusamy, Advances in Knowledge Discovery and Data Mining, AAAI Press, Melo Park, CA (1996). |
| [38] | Foulds, L. R. and D. G. Johnson, ”SlotManager: A microcomputer-based decision support system for university timetabling,” Decision Support Systems, 27, 307–381 (2000). · doi:10.1016/S0167-9236(99)00082-2 |
| [39] | Gaspero, L. D. and A. Schaerf, ”Tabu search techniques for examination timetabling,” in Burke, E. K. and W Erben (eds.), ”The 3rd International Conference on the Practice and Theory of Automated Timetabling,” Lecture Notes in Computer Science 2079, Springer-Verlag 2000, pp. 104–117. · Zbl 0982.68784 |
| [40] | Han, L. and G. Kendall, ”Investigation of a tabu assisted hyper-heuristic genetic algorithm,” in Proceedings of Congress on Evolutionary Computation (CEC2003), Vol. 3, 2003, 2230–2237. |
| [41] | Kendall, G. and N. M. Hussin, ”An investigation of a tabu-search-based hyper-heuristic for examination timetabling,” in Kendall, G., E. Burke, S. Petrovic and M. Gendreau (eds.), Multidisciplinary Scheduling: Theory and Applications, Springer, USA (2005a). |
| [42] | Kendall, G. and N.M. Hussin, ”A tabu search hyper-heuristic approach to the examination timetabling problem at the MARA UNIVERSITY OF TECHNOLOGY,” in Burke, E. K. and M. Trick, (eds.), The 5th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 3616, Springer-Verlag 2005b, pp. 270–293. |
| [43] | Kolodner, J. L. and D. Leake, ”A tutorial introduction to case-based reasoning,” in Leake, D. (ed.), Case-based Reasoning: Experiences, Lessons and Future Directions, AAAI Press, Menlo Park, CA (1996), pp. 31–65. |
| [44] | Kong, S. C. and L. F. Kwok, ”A conceptual model of knowledge-based timetabling system,” Knowledge-Based Systems, 12, 81–93 (1999). · doi:10.1016/S0950-7051(98)00090-2 |
| [45] | Leake, D. (ed.), Case-based Reasoning: Experiences, Lessons and Future Directions, AAAI Press, Menlo Park, CA (1996). |
| [46] | MacCarthy, B. L. and P. Jou, ”Case-based reasoning in scheduling,” in M. K. Khan and C. S. Wright, (eds.), in Proceedings of the Symposium on Advanced Manufacturing Processes, Systems and Techniques, (MEP Publications Ltd, 1996), 1996 pp. 211–218. |
| [47] | Mantaras, R. L. and E. Plaza,”Case-based reasoning: An overview,” Al Communications, 10, 21–29 (1997). |
| [48] | T-Marin, H., P. Ross, and M. V-Rendon, ”Evolution of constraint satisfaction strategies in examination timetabling,” in Proceedings of the Genetic and Evolutionary Computation Conference, 1999 pp. 635–642. |
| [49] | Miyashita, K. and K. Sycara, ”CABINS: A framework of knowledge acquisition and iterative revision for schedule improvement and reactive repair,” Artificial Intelligence, 76, 377–426 (1995). · doi:10.1016/0004-3702(94)00089-J |
| [50] | Petrovic, S. and E. K. Burke, ”University timetabling,” in J. Y. T. Leung (ed.), Handbook of Scheduling, Chapter 45. CRC Press LLC (2004). · Zbl 1139.90420 |
| [51] | Petrovic, S., V. Patel, and Y. Yang, ”Examination timetabling with fuzzy constraints,” in Burke, E. K. and M. Trick, (eds.), The 5th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 3616, Springer-Verlag 2005, pp. 313–333. |
| [52] | Reeves, C. R., ”Modern heuristic techniques,” in V. J. R-Smith, I. H. Osman, C. R. Reeves and G. D. Smith (eds.), Modern Heuristic Search Methods, 1996 pp. 1–25. |
| [53] | Ross, P., ”Hyper-heuristics,” in E. K. Burke and G. Kendall (eds.), Introductory Tutorials in Optimisation, Decision Support and Search Methodology, Chapter 17. Kluwer (2004). |
| [54] | Ross, P., E. Hart, and D. Corne, ”Some observations about GA based timetabling,” in Burke, E. K. and M. Carter (eds.), The 2nd International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 1408. Springer-Verlag, 1998, pp. 115–229 . |
| [55] | Rattadilok, P., A. Gaw, and R. S. K. Kwan, ”Distributed choice function hyper-heuristics for timetabling and scheduling,” in Burke, E. K. and M. Trick, (eds.), The 5th International Conference on the Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science 3616, Springer-Verlag 2005, 51–70. |
| [56] | Schaef, A., ”A survey of automated timetabling,” Artificial Intelligence Review, 13, 87–127 (1999). · doi:10.1023/A:1006576209967 |
| [57] | Schmidt, G.,” Case-based reasoning for production scheduling,” International Journal of Production Economics, 56–57, 537–546 (1998). · doi:10.1016/S0925-5273(97)00141-2 |
| [58] | Scott, S., R. Simpson, and R. Ward, ”Combining case-based reasoning and constraint logic programming techniques for packaged nurse rostering systems,” in Proceedings of the 3rd UK Case-Based Reasoning Workshop, University of Manchester, U.K. 9 September (1997). |
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.
