新中考中的排课问题

doi:10.15960/j.cnki.issn.1007-6093.2021.04.010

运筹学学报 ›› 2021, Vol. 25 ›› Issue (4): 111-119.doi: 10.15960/j.cnki.issn.1007-6093.2021.04.010

新中考中的排课问题

兰艳¹, 丁宁², 李嘉鑫³, 元文学²^,*(), 张明会⁴, 韩鑫³

1. 大连民族大学信息与通信工程学院, 辽宁大连 116600
2. 大连理工大学体育与健康学院盘锦分院, 辽宁盘锦 124221
3. 大连理工大学软件学院, 辽宁大连 116620
4. 大连东软信息学院, 辽宁大连 116023

收稿日期:2020-06-23 出版日期:2021-12-15 发布日期:2021-12-11
通讯作者: 元文学 E-mail:yuanwx@dlnu.edu.cn
作者简介:元文学, E-mail: yuanwx@dlnu.edu.cn
基金资助:
国家自然科学基金(11701062);辽宁省博士科研启动基金(2020-BS-076)

Timetabling for new middle school entrance examination

Yan LAN¹, Ning DING², Jiaxin LI³, Wenxue YUAN²^,*(), Minghui ZHANG⁴, Xin HAN³

1. School of Information and Communication Engineering, Dalian Minzu University, Dalian 116600, Liaoning, China
2. Panjin Branch, School of Physical Education and Health, Dalian University of Technology, Panjin 124221, Liaoning, China
3. Software School, Dalian University of Technology, Dalian 116620, Liaoning, China
4. Dalian Neusoft University of Information, Dalian 116023, Liaoning, China

Received:2020-06-23 Online:2021-12-15 Published:2021-12-11
Contact: Wenxue YUAN E-mail:yuanwx@dlnu.edu.cn

摘要/Abstract

摘要：

为提高初中学业水平和综合素质教育，近几年有些地方中考进行改革，要求学生进行学科选择。新中考课程分为选修和必修两大类。必修课程为语文、数学、英语，选修课程为其他六门课程，从中选出三项。把最后总成绩作为中考录取的标准。跟传统排课不同，这里排课要求每人一张课表，问题变得复杂困难。本文以北京某初三课程为例，研究了新中考的排课问题。一般情况下约束和变量是上百万级的，无法求解。本文利用整数规划建模，然后把该问题转化成多阶段问题，每个阶段给出小问题的解，这样使得问题的求解变得可行。最终的排课结果，仅比预期增加三位老师就可以实现新中考的排课问题。本文的求解过程给新中考排课带来了新的启发。

关键词: 整数规划, 排课, 优化

Abstract:

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

中图分类号:

O221.7

兰艳, 丁宁, 李嘉鑫, 元文学, 张明会, 韩鑫. 新中考中的排课问题[J]. 运筹学学报, 2021, 25(4): 111-119.

Yan LAN, Ning DING, Jiaxin LI, Wenxue YUAN, Minghui ZHANG, Xin HAN. Timetabling for new middle school entrance examination[J]. Operations Research Transactions, 2021, 25(4): 111-119.

图/表 9

表1

表2

表3

表4

表5

表6

表7

表8

表9

参考文献 12

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. doi: 10.3969/j.issn.1008-1739.2017.22.070
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. doi: 10.3969/j.issn.1001-182X.2018.01.042
8	林晶, 林恒青, 陈丹青. 基于图论算法的高校排课系统研究[J]. 福建工程学院学报, 2013, 11 (6): 608- 612. doi: 10.3969/j.issn.1672-4348.2013.06.020
9	陈本庆, 马永强, 何虎. 改进型回溯法在高校排课中的应用[J]. 成都信息工程学院学报, 2003, 18 (2): 150- 154. doi: 10.3969/j.issn.1671-1742.2003.02.010
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. doi: 10.1007/s10479-012-1078-5
12	唐环, 高健. 一种改进的蚁群算法求解中学排课问题[J]. 工业控制计算机, 2017, 30 (1): 97- 99.

课程代码	课程名称	学时	会考科目	学时	总学时	报名人数
101	物理、生化、历史	37	政治	1	38	96
102	物理、生化、地理	36	政治、历史	2	38	277
103	物理、生化、思品	37	历史	1	38	69
104	物理、历史、地理	32	化学、政治	4	36	33
105	物理、历史、思品	33	化学	3	36	14
106	物理、地理、思品	32	化学、历史	4	36	7
107	生化、历史、地理	34	物理、政治	4	38	3
108	生化、历史、思品	35	物理	3	38	6
109	生化、地理、思品	34	物理、历史	4	38	5

	周一	周二	周三	周四	周五
1	AAA	AAA	AAA	AAA	AAA
2	AAA	AAA	AAA	AAA	AAA
3	AAA	AAA	AAA	AAA	AAA
4		AAA	AAA	AAA	AAA
5	AAA	AAA
6			BBB
7			BBB
8			AAA

	周一	周二	周三	周四	周五
1
2
3
4	CCC
5	CCC	CCC	CCC	CCC	CCC
6
7
8	CCC	CCC	CCC	CCC	CCC

物理中考	人数	化学中考	人数	生物中考	人数
物中0班	38	化中0班	47	生中0班	50
物中1班	40	化中1班	50	生中1班	50
物中2班	38	化中2班	50	生中2班	49
物中3班	39	化中3班	31	生中3班	7
物中4班	41	化中4班	50	生中4班	50
物中5班	36	化中5班	22	生中5班	50
物中6班	38	化中6班	18	生中6班	42
物中7班	39	化中7班	50	生中7班	50
物中8班	46	化中8班	37	生中8班	50
物中9班	46	化中9班	50	生中9班	50
物中10班	47	化中10班	50	生中10班	7
物中11班	48

地理中考	人数	政治中考	人数	历史中考	人数
地中0班	50	政中0班	36	历中0班	41
地中1班	50	政中1班	16	历中1班	24
地中2班	49	政中2班	50	历中2班	37
地中3班	31			历中3班	50
地中4班	49
地中5班	46
地中6班	50

新中考中的排课问题

Timetabling for new middle school entrance examination

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 12

相关文章 15

编辑推荐

Metrics

本文评价

	101	102	103	104	105	106	107	108	109	总计
班级01	8	21	4	1	3	1	1	0	1	40
班级02	7	21	4	5	1	2	0	1	0	41
班级03	3	24	10	1	0	0	1	0	1	40
班级04	7	25	3	3	1	0	0	0	1	40
班级05	10	16	9	2	3	1	0	0	0	41
班级06	4	17	8	3	3	1	1	2	0	39
班级07	11	11	12	3	1	0	0	1	1	40
班级08	8	24	2	3	2	0	0	1	1	41
班级09	11	24	4	6	0	1	0	0	0	46
班级10	10	25	5	5	0	1	0	1	0	47
班级11	8	36	2	1	0	0	0	0	0	47
班级12	9	33	6	0	0	0	0	0	0	48
总计	96	277	69	33	14	7	3	6	5	510

政治会考	人数	历史会考	人数	物理会考	人数	化学会考	人数
政会0班	50	历会0班	16	物会0班	7	化会0班	35
政会1班	36	历会1班	50	物会1班	7	化会1班	20
政会2班	40	历会2班	50
政会3班	40	历会3班	49
政会4班	48	历会4班	49
政会5班	44	历会5班	50
政会6班	50	历会6班	44
政会7班	50	历会7班	50
政会8班	50

[1]	黄志鹏, 李兴权, 朱文兴. 超大规模集成电路布局的优化模型与算法[J]. 运筹学学报, 2021, 25(3): 15-36.
[2]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[3]	孙聪, 张亚. 梯度法简述[J]. 运筹学学报, 2021, 25(3): 119-132.
[4]	江波, 朱喜华. 基于横截面回归和Fama-MacBeth估计的鲁棒投资组合优化问题研究[J]. 运筹学学报, 2021, 25(3): 133-146.
[5]	刘治平. 基因调控网络推断研究进展[J]. 运筹学学报, 2021, 25(3): 173-182.
[6]	白富生, 冯丹, 张柯. 求解昂贵黑箱全局优化问题的自适应采样组合响应面方法[J]. 运筹学学报, 2021, 25(2): 1-14.
[7]	周宇阳, 张惠珍, 马良. 求解应急医疗设施分层递进式选址问题的改进免疫算法[J]. 运筹学学报, 2021, 25(2): 15-34.
[8]	钱晓慧, 王湘美. 一种单位化的增量梯度算法[J]. 运筹学学报, 2021, 25(2): 81-92.
[9]	汪文意, 高英, 刘芙萍. co-radiant集的等价表示及其在向量优化问题中的应用[J]. 运筹学学报, 2021, 25(2): 135-143.
[10]	沈吟东, 钱壮, 李媛媛. 公共交通驾驶员调度研究综述[J]. 运筹学学报, 2021, 25(1): 1-16.
[11]	李红武, 谢敏, 张榕. 一类非光滑凸优化问题的邻近梯度算法[J]. 运筹学学报, 2021, 25(1): 61-72.
[12]	陈佳利, 张莹, 王胜刚, 谢笑盈. 一个新的填充函数及其在数据拟合问题中的应用[J]. 运筹学学报, 2021, 25(1): 81-88.
[13]	屈德强, 尚有林, 詹悦, 吴丹. 全局优化问题的一个新的无参数填充函数[J]. 运筹学学报, 2021, 25(1): 89-95.
[14]	赵晨, 罗自炎, 修乃华. 稀疏优化理论与算法若干新进展[J]. 运筹学学报, 2020, 24(4): 1-24.
[15]	黎君, 陈加伟, 邓光菊. 广义凸区间值优化问题的最优性条件[J]. 运筹学学报, 2020, 24(4): 25-38.

	周一	周二	周三	周四	周五
1	数学2班	英语2班	数学2班	数学2班	数学2班
2	英语2班	英语2班	数学2班	英语2班	英语2班
3	体育2班	语文2班	体育2班	美术2班	语文2班
4	政中0班	数学2班	空闲	语文2班	语文2班
5	语文2班	体育2班	地理4班	政中0班	物会0班
6	生物10班	化中4班	化中4班	化中4班	化中4班
7	化中4班	物会0班	语文2班	物会0班	生物10班
8	空闲	历会2班	音乐2班	地理4班	政中0班

	周一	周二	周三	周四	周五
1	语文10班	语文1班		语文10班	语文1班
2					语文1班
3					语文10班
4				语文1班	语文10班
5	语文1班	语文10班
6			语文1班
7			语文10班
8