关键词: 新高考, 时序约束, 行政班分班, 教学班分班, 变邻域搜索

Abstract: 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 choosing courses freely, the implementation of the “optional class system” teaching model is becoming increasingly popular. The timetabling problem under the comprehensive reform of the new college entrance examination in China can be divided into two stages:Class planning and course scheduling. Among them, class planning is the basis and prerequisite of the problem of course scheduling. On the one hand, a good classification plan can reduce the use of teaching-related scarce resources and the number of walking students, increase class stability, reduces the management difficulty of the teaching model with “optional class system”. More importantly, the optimized class placement plan can greatly reduce the conflicts caused by students attending classes at the same time. It is the basis and prerequisite for producing a legal and high-quality course timetabling, and can greatly reduce the difficulty and complexity of course scheduling.
Aiming at a series of problems in class planning, firstly, this paper summarizes the various class classification modes of administrative class under the new college entrance examination, including “priority-fixed-three”mode and “fixed-two-choose-one” mode, and establishes the general mathematical model of this problem. Secondly, this paper summarizes the problem of teaching class division planning under the new college entrance examination.In order to meet the needs of all students in subject selection, it is necessary to set up a sufficient number of teaching classes, and in order to maximize the use of class hours, it is necessary to evenly distribute teaching classes to each class. Since the number of subjects students choose is 3, the best way is to have 3 courses in each class as a teaching class. In order to avoid the absence of a legitimate course scheduling scheme due to the conflict of students' class time, the school generally sets three fixed time periods (each student can find all courses matching his chosen subjects in these three time periods) for students to carry out unified class teaching. Therefore, this problem is defined as a teaching class division planning problem considering timing constraints. The corresponding MIP model under this system is established, which also fully considers the constraints of classroom resources and teacher resources.
CPLEX is used to solve the model, and it performs well on small examples. Aiming at the large-scale calculation example of teaching class division planning problem, this paper proposes a variable neighborhood search (VNS) algorithm to solve it.The algorithm uses Flip Class, Swap Two Class, Exchange Class and Exchange Combination to select the best move from the current neighborhood in the way of traversing the neighborhood. After obtaining the intermediate solution and the final solution, it is necessary to optimize the solution on the basis of a single student (the subject selection combination is the unit in the neighborhood search) without changing the subject offered by the class, so as to balance the number of students in each class as much as possible. Finally, the rationality and validity of the model are verified by the actual case of senior three students in a middle school in Guangzhou and the result analysis of a random example.
On the basis of the research in this paper, the future can be further considered on the basis of the matching of students' learning level and class level, the division planning of administrative classes and teaching classes, and whether the circulation between levels is allowed. In the process of dividing teaching classes, the best match between teachers and students is considered, that is, students are arranged to be taught in the class of their preferred teachers as much as possible.

Key words: new college entrance examination, time sequence constraints, administrative class classification, teaching class classification, variable neighborhood search algorithm