运筹学学报 >
2021 , Vol. 25 >Issue 4: 111 - 119
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.04.010
新中考中的排课问题
收稿日期: 2020-06-23
网络出版日期: 2021-12-11
基金资助
国家自然科学基金(11701062);辽宁省博士科研启动基金(2020-BS-076)
Timetabling for new middle school entrance examination
Received date: 2020-06-23
Online published: 2021-12-11
为提高初中学业水平和综合素质教育,近几年有些地方中考进行改革,要求学生进行学科选择。新中考课程分为选修和必修两大类。必修课程为语文、数学、英语,选修课程为其他六门课程,从中选出三项。把最后总成绩作为中考录取的标准。跟传统排课不同,这里排课要求每人一张课表,问题变得复杂困难。本文以北京某初三课程为例,研究了新中考的排课问题。一般情况下约束和变量是上百万级的,无法求解。本文利用整数规划建模,然后把该问题转化成多阶段问题,每个阶段给出小问题的解,这样使得问题的求解变得可行。最终的排课结果,仅比预期增加三位老师就可以实现新中考的排课问题。本文的求解过程给新中考排课带来了新的启发。
兰艳, 丁宁, 李嘉鑫, 元文学, 张明会, 韩鑫 . 新中考中的排课问题[J]. 运筹学学报, 2021 , 25(4) : 111 -119 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.04.010
The course scheduling problem is a problem that all schools need to consider. Due to limitations of school resources such as teachers and classrooms, it is a challenge for all schools to organize course scheduling effectively. In recent years, high school entrance examination has been reformed to improve the level of secondary education and comprehensive quality education and students will choose subjects. The new senior high school entrance examination is divided into two major categories of electives and compulsory. Compulsory courses are Chinese, Math and English. Elective courses are six other courses, of which three are selected. The final total score will be as a college admission criteria. This scheduling problem is even more complicated and difficult. Using gurobi to optimize the course arrangement, taking the first three courses in Beijing as an example, the scheduling problem of new high school entrance examinations was investigated and studied. The final result of the course arrangement was also given. Three teachers were added as expected on the course scheduling problem.
Key words: integer programming; timetabling; optimization
| 1 | 中考网编辑. 2017年起初一新生将实行"新中考"[EB/OL]. (2018-02-23)[2020-06-20]. http://www.zhongkao.com/e/20160920/57e100b5cb059.shtml. |
| 2 | Gotlieb C C . The construction of class teacher time tables[J]. Communications of the ACM, 1962, 5 (6): 73- 77. |
| 3 | Cooper T B, Kingston J H. The complexity of timetable construction problems[C]//International Conference on the Practice and Theory of Automated Timetabling. Berlin: Springer, 1995: 281-295. |
| 4 | 刘宇, 宋国宇, 郑成焕, 等. 基于遗传算法的教室资源合理分配研究[J]. 计算机与网络, 2017, 43 (22): 71- 73. |
| 5 | Yousef A H, Salama C, Jad M Y, et al. A GPU based genetic algorithm solution for the timetabling problem[C]//2016 11th International Conference on Computer Engineering & Systems (ICCES). IEEE, 2016: 103-109. |
| 6 | Goh S L , Kendall G , Sabar N R . Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem[J]. Journal of the Operational Research Society, 2018, 6 (2): 1- 16. |
| 7 | 高健, 廖斌华, 高培. 基于改进模拟退火算法的中学排课问题[J]. 工业控制计算机, 2018, 31 (1): 101- 102. |
| 8 | 林晶, 林恒青, 陈丹青. 基于图论算法的高校排课系统研究[J]. 福建工程学院学报, 2013, 11 (6): 608- 612. |
| 9 | 陈本庆, 马永强, 何虎. 改进型回溯法在高校排课中的应用[J]. 成都信息工程学院学报, 2003, 18 (2): 150- 154. |
| 10 | Thepphakorn T , Pongcharoen P , Hicks C . An ant colony based timetabling tool[J]. International Journal of Production Economics, 2014, 14 (9): 131- 144. |
| 11 | Nothegger C , Mayer A , Chwatal A , et al. Solving the post enrolment course timetabling problem by ant colony optimization[J]. Annals of Operations Research, 2012, 194 (1): 325- 339. |
| 12 | 唐环, 高健. 一种改进的蚁群算法求解中学排课问题[J]. 工业控制计算机, 2017, 30 (1): 97- 99. |
/
| 〈 |
|
〉 |