A Hidden Markov Model Approach to the Problem of Heuristic Selection in Hyper-Heuristics with a Case Study in High School Timetabling Problems

Abramson, D. (1991). Constructing school timetables using simulated annealing: Sequential and parallel algorithms. Management Science, 37(1):98–113.

Abramson, D. A., Dang, H., and Krisnamoorthy, M. (1999). Simulated annealing cooling schedules for the school timetabling problem. Asia-Pacific Journal of Operational Research, 16(1):1–22.

Ahmed, L. N., Özcan, E., and Kheiri, A. (2015). Solving high school timetabling problems worldwide using selection hyper-heuristics. Expert Systems with Applications, 42(13):5463–5471.

Alvarez-Valdés, R., Parreño, F., and Tamarit, J. M. (2002). A tabu search algorithm for assigning teachers to courses. TOP, 10(2):239–259.

Baum, L. E., and Petrie, T. (1966). Statistical inference for probabilistic functions of finite state Markov chains. The Annals of Mathematical Statistics, 37(6):1554–1563.

Beligiannis, G. N., Moschopoulos, C. N., Kaperonis, G. P., and Likothanassis, S. D. (2008). Applying evolutionary computation to the school timetabling problem: The Greek case. Computers and Operations Research, 35(4):1265–1280.

Bello, G. S., Rangel, M. C., and Boeres, M. C. S. (2008). An approach for the class/teacher timetabling problem. In Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling, pp. 1–6.

Bilgin, B., Özcan, E., and Korkmaz, E. E. (2007). An experimental study on hyper-heuristics and exam scheduling. In E. K.Burke and H.Rudová (Eds.), Practice and Theory of Automated Timetabling VI, volume 3867 of Lecture Notes in Computer Science, pp. 394–412.

Birbas, T., Daskalaki, S., and Housos, E. (2009). School timetabling for quality student and teacher schedules. Journal of Scheduling, 12(2):177–197.

Bufé, M., Fischer, T., Gubbels, H., Häcker, C., Hasprich, O., Scheibel, C., Weicker, K., Weicker, N., Wenig, M., and Wolfangel, C. (2001). Automated solution of a highly constrained school timetabling problem—Preliminary results. In E. J. W.Boers (Ed.), Applications of Evolutionary Computing, volume 2037 of Lecture Notes in Computer Science, pp. 431–440.

Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., and Qu, R. (2013). Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society, 64(12):1695–1724.

Calderia, J. P., and Ross, A. C. (1997). School timetabling using genetic search. In Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, pp. 115–122.

Colorni, A., Dorigo, M., and Maniezzo, V. (1992). A genetic algorithm to solve the timetable problem. Technical Report Technical Report No. 90-060, Politecnico di Milano, Italy.

Cowling, P., Kendall, G., and Soubeiga, E. (2001). A hyperheuristic approach to scheduling a sales summit. In E.Burke and W.Erben (Eds.), Practice and Theory of Automated Timetabling III, volume 2079 of Lecture Notes in Computer Science, pp. 176–190.

Domrös, J., and Homberger, J. (2012). An evolutionary algorithm for high school timetabling. In Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling, pp. 485–488.

Dueck, G. (1993). New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104(1):86–92.

Even, S., Itai, A., and Shamir, A. (1976). On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4):691–703.

Fagerland, M. W., and Sandvik, L. (2009). The Wilcoxon–Mann–Whitney test under scrutiny. Statistics in Medicine, 28(10):1487–1497.

Filho, G. R., Antonio, L., and Lorena, L. A. N. (2001). A constructive evolutionary approach to school timetabling. In E. J. W.Boers (Ed.), Applications of Evolutionary Computing, volume 2037 of Lecture Notes in Computer Science, pp. 130–139.

Fonseca, G. H. G., Santos, H. G., and Carrano, E. G. (2015). Late acceptance hill-climbing for high school timetabling. Journal of Scheduling, pp. 1–13.

Fonseca, G. H. G., Santos, H. G., Toffolo, T. Â. M., Brito, S. S., and Souza, M. J. F. (2014). GOAL solver: A hybrid local search based solver for high school timetabling. Annals of Operations Research, pp. 1–21.

Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13(5):533–549.

Hajek, B. (1988). Cooling schedules for optimal annealing. Mathematics of Operations Research, 13(2):311–329.

Holland, J. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press.

Jacobsen, F., Bortfeldt, A., and Gehring, H. (2006). Timetabling at German secondary schools: Tabu search versus constraint programming. In Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling, pp. 439–442.

Kalender, M., Kheiri, A., Özcan, E., and Burke, E. K. (2013). A greedy gradient-simulated annealing selection hyper-heuristic. Soft Computing, 17(12):2279–2292.

Kendall, G., and Mohamad, M. (2004). Channel assignment optimisation using a hyper-heuristic. In Proceedings of the 2004 IEEE Conference on Cybernetic and Intelligent Systems, pp. 790–795.

Kheiri, A. (2014). Multi-stage hyper-heuristics for optimisation problems. PhD thesis, University of Nottingham, School of Computer Science.

Kheiri, A., and Keedwell, E. (2015a). Markov chain selection hyper-heuristic for the optimisation of constrained magic squares. 15th UK Workshop on Computational Intelligence.

Kheiri, A., and Keedwell, E. (2015b). A sequence-based selection hyper-heuristic utilising a hidden Markov model. In Proceedings of the 2015 on Genetic and Evolutionary Computation Conference, GECCO’15, pp. 417–424.

Kheiri, A., Keedwell, E., Gibson, M. J., and Savic, D. (2015). Sequence analysis-based hyper-heuristics for water distribution network optimisation. Procedia Engineering, 119:1269–1277.

Kheiri, A., Özcan, E., and Parkes, A. J. (2016). A stochastic local search algorithm with adaptive acceptance for high-school timetabling. Annals of Operations Research, 239(1):135–151.

Kingston, J. H. (2005). A tiling algorithm for high school timetabling. In E.Burke and M.Trick (Eds.), Practice and Theory of Automated Timetabling V, volume 3616 of Lecture Notes in Computer Science, pp. 208–225.

Kingston, J. H. (2014). KHE14: An algorithm for high school timetabling. In Proceedings of the 10th International Conference on the Practice and Theory of Automated Timetabling, pp. 269–291.

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.

Kruskal, W. H. (1957). Historical notes on the Wilcoxon unpaired two-sample test. Journal of the American Statistical Association, 52(279):356–360.

Lara, C., Flores, J. J., and Calderon, F. (2008). Solving a school timetabling problem using a bee algorithm. In A.Gelbukh and E. F.Morales (Eds.), MICAI 2008: Advances in Artificial Intelligence, volume 5317 of Lecture Notes in Computer Science, pp. 664–674.

Melício, F., Calderia, J. P., and Rosa, A. (2006). THOR: A tool for school timetabling. In Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling, pp. 532–535.

Moura, A. V., and Scaraficci, R. A. (2010). A GRASP strategy for a more constrained school timetabling problem. International Journal of Operational Research, 7(2):152–170.

Özcan, E., Bilgin, B., and Korkmaz, E. E. (2008). A comprehensive analysis of hyper-heuristics. Intelligent Data Analysis, 12(1):3–23.

Özcan, E., Bykov, Y., Birben, M., and Burke, E. K. (2009). Examination timetabling using late acceptance hyper-heuristics. In IEEE Congress on Evolutionary Computation, pp. 997–1004.

Pillay, N. (2013). A survey of school timetabling research. Annals of Operations Research, pp. 1–33.

Post, G., Ahmadi, S., Daskalaki, S., Kingston, J. H., Kyngas, J., Nurmi, C., and Ranson, D. (2012). An XML format for benchmarks in high school timetabling. Annals of Operations Research, 194(1):385–397.

Post, G., Di Gaspero, L., Kingston, J. H., McCollum, B., and Schaerf, A. (2013). The third international timetabling competition. Annals of Operations Research, pp. 1–7.

Raghavjee, R., and Pillay, N. (2008). An application of genetic algorithms to the school timetabling problem. In 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, pp. 193–199.

Raghavjee, R., and Pillay, N. (2012). A comparison of genetic algorithms and genetic programming in solving the school timetabling problem. In Fourth World Congress on Nature and Biologically Inspired Computing, pp. 98–103.

Smith, K. A., Abramson, D., and Duke, D. (2003). Hopfield neural networks for timetabling: Formulations, methods, and comparative results. Computers and Industrial Engineering, 44(2):283–305.

Sørensen, M., Kristiansen, S., and Stidsen, T. R. (2012). International timetabling competition 2011: An adaptive large neighborhood search algorithm. In Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling, pp. 489–492.

Tassopoulos, I. X., and Beligiannis, G. N. (2012). A hybrid particle swarm optimization based algorithm for high school timetabling problems. Applied Soft Computing, 12(11):3472–3489.

Valouxis, C., and Housos, E. (2003). Constraint programming approach for school timetabling. Computers and Operations Research, 30(10):1555–1572.

Wilke, P., Gröbner, M., and Oster, N. (2002). A hybrid genetic algorithm for school timetabling. In B.McKay and J.Slaney (Eds.), AI 2002: Advances in Artificial Intelligence, volume 2557 of Lecture Notes in Computer Science, pp. 455–464.

Wilke, P., and Killer, H. (2010). Walk down jump up algorithm: A new hybrid algorithm for timetabling problems. In Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling, pp. 440–446.

Wolpert, D. H., and Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1:67–82.

Wright, M. B. (1996). School timetabling using heuristic search. Journal of the Operational Research Society, 47(3):347–357.

Zhang, D., Liu, Y., M’Hallah, R., and Leung, S. C. H. (2010). A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems. European Journal of Operational Research, 203(3):550–558.