Abstract:

Along with the New Reform of College Entrance Examination（or Gao Kao）, course timetabling in high school must consider the course selection of students. The potential conflicts of time slots from students increase the difficulty of acquiring available timetables as well as satisfying sophisticated demands. A multi-phase optimization algorithm is proposed to solve Chinese high school timetabling problems with “optional class system”. The optimization highlights the process of class period distribution rather than time slots assignment, which means the periods of each curriculum in each class and each day are decided. In addition to meeting the constraints of without time slots, three major optimization objectives, “period evenly distribution”, “teaching plan synchronization”and “period distribution consistency”, are employed. According to features of the problem, three timetable modification operators are designed to improve the optimization capability of the newly designed hill-climbing algorithm in the phase of education class period distribution. Tested on three experimental data sets with different complicity and scale, the multi-phase optimization algorithm obtains an available timetable with more than 85% probability. On synthetic data set and middle scale real-case data set, better results are found in objectives compared with large scale real-case data set. The teaching plan synchronization violation of the whole timetable mainly comes from administrative class timetables. It is also observed that the setting of period distribution consistency can guide the optimization of other objectives.

Key words: New Reform of College Entrance Examination, timetabling problem, multi-phase optimization, teaching plan synchronization, hill-climbing algorithm

摘要：

伴随新高考改革，高中排课过程需要考虑学生的科目选择。潜在的学生上课时间冲突提高了排出可行课表的难度，排课过程中对课表的复杂要求也更难得到满足。针对这些挑战提出一种多阶段优化算法解决高中“走班制”教学课程时间表优化问题。优化侧重点从课表时段分配转为天课时分配，即对每个课程班每天的课时数目进行决策。除需要满足课时不冲突的约束条件外，主要优化目标为“课时分布均匀”“教案平齐”“同时上课”。根据问题特点设计了三种课表变换算子用于在教学班天课时分配阶段提升新设计的爬山算法的寻优能力。在三组不同难度和规模的实验数据上，多阶段优化算法以高于85%的概率排出可行课表。相较大规模真实案例，人工生成案例和中规模真实案例在目标函数上得到较为理想的优化。整体课表的教案平齐违反主要源于行政班课表。发现同时上课的设置具有指导其他目标函数优化的能力。

关键词: 新高考改革, 排课问题, 多阶段优化, 教案平齐, 爬山算法