Research On The Modeling And Algorithm Design For Solving Class Division And Timetabling Problems Under The New College Entrance Examination Reform

Since the launch of the new college entrance examination reform in China in 2014,29 provinces have published their reform plans in five batches.The reform involves the cancellation of the classification of arts and sciences and the adoption of a “3+3” or “3+1+2”model,in which Chinese,mathematics,and English are compulsory subjects,and physics,chemistry,and biology,as well as politics,history,and geography,are elective subjects.To safeguard students’ right to choose courses freely,the implementation of the “optional class system” teaching model is becoming increasingly popular.Implementing the “optional class system” requires completing two stages: class division planning and scheduling.Among them,class division planning is a prerequisite and foundation for scheduling.A good class division plan can greatly reduce the use of scarce teaching resources,reduce the difficulty of managing the “optional class system”,and greatly reduce time conflicts caused by students’ elective classes.This is a prerequisite for producing legitimate and high-quality scheduling plans.This article analyzes the problems encountered by schools in the process of implementing the optional class system in three different stages: administrative class division,teaching class division,and timetable arrangement.The problems are modeled,and variable neighborhood search algorithms,tabu search algorithms,and probability learning algorithms are respectively designed for solutions.The main research work and innovations of this article can be summarized as follows:Firstly,this article summarizes various class division modes under the new college entrance examination and establishes mixed-integer programming(MIP)models based on assignment and flow for “prioritizing-fixed-three” mode and “fixed-two-choose-one” mode.Experiments show that the flow-based MIP model has a higher solving efficiency.For largescale examples,a neighborhood decomposition-driven improving variable neighborhood search(NDIVNS)algorithm is designed,which accelerates the search process by marking potential neighborhoods.In addition,the efficiency of the model for the “fixed-two-chooseone” mode is related to the example structure.Secondly,this article summarizes the problem of teaching class division planning under the new college entrance examination,designs an optional class scheme considering time constraints,and establishes a corresponding MIP model that fully considers school classroom and teacher resources.A double evaluation method-based improving variable neighborhood search(DEMIVNS)algorithm is designed for medium to large-scale examples,which explores the search space better by considering infeasible solutions,and experimental results verify the algorithm’s efficiency.Thirdly,this article studies the problem of class scheduling under the new college entrance examination,establishes an MIP model considering constraints such as concurrent groups and lesson plan consistency,and designs a two-phase tabu search algorithm based on class period guidance(TPTSCPG)for solution.The lesson time distribution mechanism can generate higher-quality initial solutions,and the phased search can focus the algorithm on improving the satisfaction of soft constraints.The performance of the proposed algorithm is verified by testing on 15 real-world examples.Finally,this article improves the algorithm proposed in the previous chapter,introduces a probability learning based on graph coloring model(PLGCM)framework for optional class scheduling problem,and designs a fast neighborhood search operator based on Kempe chains according to the problem characteristics.Testing on the same 15 examples confirms the efficiency of the proposed algorithm.In addition,to verify the universality of the algorithm,the traditional timetabling problem is solved.Experimental results show that the proposed algorithm can improve 10 of the most well-known solutions out of 34 examples.In summary,this article presents an in-depth study of a series of problems under the new college entrance examination reform,using a combination of theoretical and applied research,and is dedicated to applying the designed algorithm to practice.The optional class scheduling system developed based on part of this study is currently being used in dozens of high schools in China for practical class scheduling activities.