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

作　　者：Xingxing HAO Jing LIU Yutong ZHANG Gustaph SANGA 

机构地区：[1]Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education,Xidian University,Xi’an 710071,China

出　　处：《Frontiers of Computer Science》2021年第1期167-177,共11页中国计算机科学前沿（英文版）

基　　金：This work was supported in part by the Outstanding Young Scholar Program of National Natural Science Foundation of China(NSFC)(Grant No.61522311);in part by the General Program of NSFC(Grant No.61773300);in part by the Key Program of Fundamental Research Project of Natural Science of Shaanxi Province,China(2017JZ017);in part by the Doctoral Students'Short-Term Study Abroad Scholarship Fund of Xidian University.

摘　　要：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 2011 by the Chine6e government.Aooording 10 the new our riculum 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 typi-cal"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 ilustrate 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.

关 键 词：TIMETABLING Chinese high school timetabling problem simulated annealing two-part representation 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]