Mathematical model and simulated annealing algorithm for Chinese high school timetabling problems under the new curriculum innovation

Kristiansen S, Stidsen T R. A comprehensive study of educational timetabling-a survey Department of Management Engineering, Technical University of Denmark, DTU Management Engineering Report, Denmark, 2013 Pillay N. A survey of school timetabling research. Annals of Operations Research, 2014, 218(1): 261–293 Al-Yakoob S M, Sherali H D. Mathematical models and algorithms for a high school timetabling problem. Computers & Operations Research, 2015, 61: 56–68 Kwok L F, Kong S C, Kam Y Y. Timetabling in Hong Kong secondary schools. Computers & Education, 1997, 28(3): 173–183 Santos H G, Ochi L S, Souza M J F. An efficient tabu search heuristic for the school timetabling problem. In: Proceedings of International Workshop on Experimental and Efficient Algorithms. 2004, 468–481 Santos H G, Ochi L S, Souza M J F. A tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem. Journal of Experimental Algorithmics, 2005, 10: 2–9 Beligiannis G N, Moschopoulos C N, Kaperonis G P, Likothanassis S D. Applying evolutionary computation to the school timetabling problem: the Greek case. Computers & Operations Research, 2008, 35(4): 1265–1280 Beligiannis G N, Moschopoulos C, Likothanassis S D. A genetic algorithm approach to school timetabling. Journal of the Operational Research Society, 2009, 60(1): 23–42 Zhang D, Liu Y, M’Hallah R, Leung S C H. A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems. European Journal of Operational Research, 2010, 203(3): 550–558 Katsaragakis IV, Tassopoulos I X, Beligiannis G N. A comparative study of modern heuristics on the school timetabling problem. Algorithms, 2015, 8(3): 723–742 Skoullis V I, Tassopoulos I X, Beligiannis G N. Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm. Applied Soft Computing, 2017, 52: 277–289 Raghavjee R, Pillay N. An informed genetic algorithm for the high school timetabling problem. In: Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists. 2010, 408–412 Raghavjee R, Pillay N. Evolving solutions to the school timetabling problem. In: Proceedings of World Congress on Nature & Biologically Inspired Computing. 2009, 1524–1527 Raghavjee R, Pillay N. A genetic algorithm selection perturbative hyper-heuristic for solving the school timetabling problem. ORiON, 2015, 31(1): 39–60 Cerdeira-Pena A, Carpente L, Farina A, Seco D. New approaches for the school timetabling problem. In: Proceedings of the 7th Mexican International Conference on Artificial Intelligence. 2008, 261–267 Odeniyi O A, Omidiora E O, Olabiyisi S O, Aluko J O. Development of a modified simulated annealing to school timetabling problem. International Journal of Applied Information Systems, 2015, 8(1): 16–24 Boland N, Hughes B D, Merlot L T G, Stuckey P J. New integer linear programming approaches for course timetabling. Computers & Operations Research, 2008, 35(7): 2209–2233 Kingston J H. A tiling algorithm for high school timetabling. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2004, 208–225 Merlot L. Techniques for academic timetabling. PhD Thesis, University of Melbourne, Australia, 2005 Ribeiro F G, Lorena L A N. A constructive evolutionary approach to school timetabling. In: Proceedings of Workshops on Applications of Evolutionary Computation. 2001, 130–139 Willemen R J R. School Timetable Construction: Algorithms and Complexity. Eindhoven: Technische Universiteit Eindhoven, 2002 Bello G S, Rangel M C, Boeres M C S. An approach for the class/teacher timetabling problem using graph coloring. In: Proceedings of the International Conference on the Practice and Theory of Automated Timetabling. 2008 Moura A V, Scaraficci R A. A GRASP strategy for a more constrained school timetabling problem. International Journal of Operational Research, 2010, 7(2): 152–170 Santos H G, Uchoa E, Ochi L S, Maculan N. Strong bounds with cut and column generation for class-teacher timetabling. Annals of Operations Research, 2012, 194(1): 399–412 Brito S S, Fonseca G H G, Toffolo T A M, Santos H G, Souza M J F. A SA-VNS approach for the high school timetabling problem. Electronic Notes in Discrete Mathematics, 2012, 39: 169–176 Lach G, Lübbecke M E. Curriculum based course timetabling: new solutions to Udine benchmark instances. Annals of Operations Research, 2012, 194(1): 255–272 Sørensen M, Dahms F H W. A two-stage decomposition of high school timetabling applied to cases in Denmark. Computers & Operations Research, 2014, 43: 36–49 Birbas T, Daskalaki S, Housos E. Timetabling for Greek high schools. Journal of the Operational Research Society, 1997, 48(12): 1191–1200 Valouxis C, Housos E. Constraint programming approach for school timetabling. Computers & Operations Research, 2003, 30(10): 1555–1572 Papoutsis K, Valouxis C, Housos E. A column generation approach for the timetabling problem of Greek high schools. Journal of the Operational Research Society, 2003, 54(3): 230–238 Moschopoulos C N, Alexakos C E, Dosi C, Beligiannis G N, Likothanassis S D. A user-friendly evolutionary tool for high-school timetabling. Tools and Applications with Artificial Intelligence, 2009, 166: 149–162 Birbas T, Daskalaki S, Housos E. School timetabling for quality student and teacher schedules. Journal of Scheduling, 2009, 12(2): 177–197 Valouxis C, Gogos C, Alefragis P, Housos E. Decomposing the high school timetable problem. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2012, 29–31 Colorni A, Dorigo M, Maniezzo V. Metaheuristics for high school timetabling. Computational Optimization and Applications, 1998, 9(3): 275–298 Schaerf A. Local search techniques for large high school timetabling problems. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 1999, 29(4): 368–377 Avella P, D’Auria B, Salerno S, Vasil’ev I. A computational study of local search algorithms for Italian high-school timetabling. Journal of Heuristics, 2007, 13(6): 543–556 Fernandes C, Caldeira J P, Melicio F, Rosa A. High school weekly timetabling by evolutionary algorithms. In: Proceedings of the ACM Symposium on Applied Computing. 1999, 344–350 Melício F, Calderia J P, Rosa A. THOR: a tool for school timetabling. In: Proceedings of International Conference on the Practice and Teaching of Automated Timetabling. 2006, 532–535 Alvarez-Valdés R, Parreño F, Tamarit J M. A tabu search algorithm for assigning teachers to courses. Top, 2002, 10(2): 239–259 Nurmi K, Kyngas J. A framework for school timetabling problem. In: Proceedings of the 3rd Multidisciplinary International Scheduling Conference: Theory and Applications. 2007, 386–393 Post G F, Ruizenaar H W A, Post G, Ruizenaar H. Clusterschemes in Dutch secondary schools. Department of Applied Mathematics, University of Twente, The Netherlands, 2004 De H P, Landman R, Post G, Ruizenaar H. A case study for timetabling in a Dutch secondary school. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2006, 267–279 Post G, Ahmadi S, Geertsema F. Cyclic transfers in school timetabling. OR Spectrum, 2012, 34(1): 133–154 Hartog J. Timetabling on dutch high schools. PhD Thesis, The Netherland: Technische Universiteit Delft, 2007 Bufé M, Fischer T, Gubbels H, Hacker C, Hasprich O, Scheibel C, Weicker K, Weicker N, Wenig M, Wolfangel C. Automated solution of a highly constrained school timetabling problem-preliminary results. In: Proceedings of Workshops on Applications of Evolutionary Computation. 2001, 431–440 Wilke P, Gröbner M, Oster N. A hybrid genetic algorithm for school timetabling. In: Proceedings of Australian Joint Conference on Artificial Intelligence. 2002, 455–464 Jacobsen F, Bortfeldt A, Gehring H. Timetabling at German secondary schools: tabu search versus constraint programming. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2006, 439–442 Löhnertz M. A timetabling system for the German gymnasium. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2002 Marte M. Models and algorithms for school timetabling-a constraint-programming approach. Dissertation, Ludwig-Maximilians-Universitat Munchen, 2002 Wood J, Whitaker D. Student centred school timetabling. Journal of the Operational Research Society, 1998, 49(11): 1146–1152 Wilke P, Ostler J. Solving the school time tabling problem using tabu search, simulated annealing, genetic and branch & bound algorithms. In: Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling. 2008, 3–6 Wilke P, Killer H. Comparison of algorithms solving school and course time tabling problems using the erlangen advanced time tabling system (EATTS). In: Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling. 2010, 427–439 Paper C, Shambour M K, Khader A T, Ozcan E. A two stage approach for high school timetabling. In: Proceedings of International Conference on Neural Information Processing. 2013, 66–73 Fonseca G H G, Santos H G, Toffolo T Â M, Brito S S, Souza M J F. GOAL solver: a hybrid local search based solver for high school timetabling. Annals of Operations Research, 2016, 239(1): 77–97 Fonseca G H G, Santos H G. Variable neighborhood search based algorithms for high school timetabling. Computers & Operations Research, 2014, 52: 203–208 Fonseca G H G, Santos H G, Carrano E G. Late acceptance hill-climbing for high school timetabling. Journal of Scheduling, 2016, 19(4): 453–465 Kristiansen S, Sørensen M, Stidsen TR. Integer programming for the generalized high school timetabling problem. Journal of Scheduling, 2015, 18(4): 377–392 Post G, Kingston J H, Ahmadi S, Daskalaki S, Gogos C, Kyngas J, Nurmi C, Musliu N, Pillay N, Santos H, Schaerf A. XHSTT: an XML archive for high school timetabling problems in different countries. Annals of Operations Research, 2014, 218(1): 295–301 Fonseca G H G, Santos H G, Carrano E G. Integrating matheuristics and metaheuristics for timetabling. Computers & Operations Research, 2016, 74: 108–117 Fonseca G H G, Santos H G, Carrano E G, Stidsen T J R. Integer programming techniques for educational timetabling. European Journal of Operational Research, 2017, 262(1): 28–39 Burke E K, Kendall G, Misir M, Özcan E. A study of simulated annealing hyper-heuristics. In: Proceedings of the International Conference on the Practice and Theory of Automated Timetabling. 2008 Burke E K, Kendall G, Misir M, Özcan E. Monte carlo hyper-heuristics for examination timetabling. Annals of Operations Research, 2012, 196(1): 73–90 Bai R, Blazewicz J, Burke E K, Kendall G, McCollum B. A simulated annealing hyper-heuristic methodology for flexible decision support. 4OR: A Quarterly Journal of Operations Research, 2012, 10(1): 43–66 Chiarandini M, Birattari M, Socha K, Rossi-Doria O. An effective hybrid algorithm for university course timetabling. Journal of Scheduling, 2006, 9(5): 403–432 Jackson W G, Özcan E, John R I. Move acceptance in local search meta-heuristics for cross-domain search. Expert Systems with Applications, 2018, 109: 131–151