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

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