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

Abstract

As the first attempt, this paper proposes a model for the Chinese high school timetabling problems (CHSTPs) under the new curriculum innovation which was launched in 2014 by the Chinese government. According to the new curriculum innovation, students in high school can choose subjects that they are interested in instead of being forced to select one of the two study directions, namely, Science and Liberal Arts. Meanwhile, they also need to attend compulsory subjects as traditions. CHSTPs are student-oriented and involve more student constraints that make them more complex than the typical “Class-Teacher model”, in which the element “Teacher” is the primary constraint. In this paper, we first describe in detail the mathematical model of CHSTPs and then design a new two-part representation for the candidate solution. Based on the new representation, we adopt a two-phase simulated annealing (SA) algorithm to solve CHSTPs. A total number of 45 synthetic instances with different amounts of classes, teachers, and levels of student constraints are generated and used to illustrate the characteristics of the CHSTP model and the effectiveness of the designed representation and algorithm. Finally,we apply the proposed model, the designed two-part representation and the two-phase SA on10 real high schools.

Keywords

timetabling / Chinese high school timetablingproblem / simulated annealing / two-part representation

References

[1] 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

[2] Pillay N. A survey of school timetabling research. Annals of Operations Research, 2014, 218(1): 261–293

[3] Al-Yakoob S M, Sherali H D. Mathematical models and algorithms for a high school timetabling problem. Computers & Operations Research, 2015, 61: 56–68

[4] Kwok L F, Kong S C, Kam Y Y. Timetabling in Hong Kong secondary schools. Computers & Education, 1997, 28(3): 173–183

[5] 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

[6] 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

[7] 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

[8] 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

[9] 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

[10] Katsaragakis I V, Tassopoulos I X, Beligiannis G N. A comparative study of modern heuristics on the school timetabling problem. Algorithms, 2015, 8(3): 723–742

[11] 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

[12] 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

[13] Raghavjee R, Pillay N. Evolving solutions to the school timetabling problem. In: Proceedings of World Congress on Nature & Biologically Inspired Computing. 2009, 1524–1527

[14] Raghavjee R, Pillay N. A genetic algorithm selection perturbative hyperheuristic for solving the school timetabling problem. ORiON, 2015, 31(1): 39–60

[15] 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

[16] 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

[17] 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

[18] 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

[19] Merlot L. Techniques for academic timetabling. PhD Thesis, University of Melbourne, Australia, 2005

[20] 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

[21] Willemen R J R. School Timetable Construction: Algorithms and Complexity. Eindhoven: Technische Universiteit Eindhoven, 2002

[22] 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

[23] 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

[24] 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

[25] 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

[26] 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

[27] 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

[28] Birbas T, Daskalaki S, Housos E. Timetabling for Greek high schools. Journal of the Operational Research Society, 1997, 48(12): 1191–1200

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

[30] 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

[31] 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

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

[33] 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

[34] Colorni A, Dorigo M, Maniezzo V. Metaheuristics for high school timetabling. Computational Optimization and Applications, 1998, 9(3): 275–298

[35] 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

[36] 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

[37] 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

[38] 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

[39] 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

[40] 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

[41] 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

[42] 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

[43] Post G, Ahmadi S, Geertsema F. Cyclic transfers in school timetabling. OR Spectrum, 2012, 34(1): 133–154

[44] Hartog J. Timetabling on dutch high schools. PhD Thesis, The Netherland: Technische Universiteit Delft, 2007

[45] Bufé M, Fischer T, Gubbels H, Häcker 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 ofWorkshops on Applications of Evolutionary Computation. 2001, 431–440

[46] 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

[47] 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

[48] Löhnertz M. A timetabling system for the German gymnasium. In: Proceedings of International Conference on the Practice and Theory of Automated Timetabling. 2002

[49] Marte M. Models and algorithms for school timetabling–a constraintprogramming approach. Dissertation, Ludwig-Maximilians-Universitat Munchen, 2002

[50] Wood J, Whitaker D. Student centred school timetabling. Journal of the Operational Research Society, 1998, 49(11): 1146–1152

[51] 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

[52] 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

[53] 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

[54] 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

[55] Fonseca G H G, Santos H G. Variable neighborhood search based algorithms for high school timetabling. Computers & Operations Research, 2014, 52: 203–208

[56] 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

[57] Kristiansen S, Sørensen M, Stidsen T R. Integer programming for the generalized high school timetabling problem. Journal of Scheduling, 2015, 18(4): 377–392

[58] 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

[59] Fonseca G H G, Santos H G, Carrano E G. Integrating matheuristics and metaheuristics for timetabling. Computers & Operations Research, 2016, 74: 108–117

[60] 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

[61] 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

[62] 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

[63] 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

[64] 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

[65] Jackson W G, Özcan E, John R I. Move acceptance in local search metaheuristics for cross-domain search. Expert Systems with Applications, 2018, 109: 131–151

RIGHTS & PERMISSIONS

Higher Education Press