摘要
我国新高考综合改革下的排课问题,可以分为分班规划和走班排课两个阶段,其中,分班规划问题是走班排课问题的基础和前提,良好的分班规划方案,一方面可以减少教学相关紧缺资源使用量,减少走班人数,增加班级稳定性,降低“走班制”教学模式的管理难度,更重要的是,优化的分班方案可以极大的减少因学生同时上课带来的冲突,是产生合法和优质排课方案的基础和前提,可以大幅度降低排课的难度和复杂度。本文第一次提出了行政班分班和教学班分班规划问题的数学模型,同时可以利用CPLEX对模型进行求解,在一些小型算例上表现良好。针对教学班分班问题,本文又提出了一种变邻域搜索算法来求解,并通过实际案例和随机算例的结果分析,验证了模型的合理性和有效性。
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.
作者
孙哲
王翀
吴庆华
SUN Zhe;WANG Chong;WU Qinghua(School of Management,Huazhong University of Science and Technology,Wuhan 430074,China)
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2023年第9期93-100,共8页
Operations Research and Management Science
基金
国家自然科学基金资助项目(72122006)。
关键词
新高考
时序约束
行政班分班
教学班分班
变邻域搜索
new college entrance examination
time sequence constraints
administrative class classification
teaching class classification
variable neighborhood search algorithm
