新中考中的排课问题

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

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

CLC Number:

O221.7

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.

Figures/Tables 9

References 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	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

课程代码	课程名称	学时	会考科目	学时	总学时	报名人数
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

Timetabling for new middle school entrance examination

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 12

Related Articles 15

Recommended Articles

Metrics

Comments

地理中考	人数	政治中考	人数	历史中考	人数
地中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

政治会考	人数	历史会考	人数	物理会考	人数	化学会考	人数
政会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]	HUANG Zhipeng, LI Xingquan, ZHU Wenxing. Optimization models and algorithms for placement of very large scale integrated circuits [J]. Operations Research Transactions, 2021, 25(3): 15-36.
[2]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[3]	SUN Cong, ZHANG Ya. A brief review on gradient method [J]. Operations Research Transactions, 2021, 25(3): 119-132.
[4]	JIANG Bo, ZHU Xihua. Robust portfolio selection based on cross-sectional regression and Fama-Macbeth estimator [J]. Operations Research Transactions, 2021, 25(3): 133-146.
[5]	LIU Zhiping. Some advances in gene regulatory network inference [J]. Operations Research Transactions, 2021, 25(3): 173-182.
[6]	Fusheng BAI, Dan FENG, Ke ZHANG. Combined response surface method with adaptive sampling for expensive black-box global optimization [J]. Operations Research Transactions, 2021, 25(2): 1-14.
[7]	Yuyang ZHOU, Huizhen ZHANG, Liang MA. An improved immune algorithm for solving hierarchical and progressive location problem of emergency medical facilities [J]. Operations Research Transactions, 2021, 25(2): 15-34.
[8]	Xiaohui QIAN, Xiangmei WANG. A scaled incremental gradient method [J]. Operations Research Transactions, 2021, 25(2): 81-92.
[9]	Wenyi WANG, Ying GAO, Fuping LIU. The equivalent representation of co-radiant sets and its application in multi-objective optimization problems [J]. Operations Research Transactions, 2021, 25(2): 135-143.
[10]	Yindong SHEN, Zhuang QIAN, Yuanyuan LI. A survey on driver scheduling in public transportation [J]. Operations Research Transactions, 2021, 25(1): 1-16.
[11]	Hongwu LI, Min XIE, Rong ZHANG. A proximal gradient method for nonsmooth convex optimization problems [J]. Operations Research Transactions, 2021, 25(1): 61-72.
[12]	Jiali CHEN, Ying ZHANG, Shenggang WANG, Xiaoying XIE. A new filled function and its application in data fitting problems [J]. Operations Research Transactions, 2021, 25(1): 81-88.
[13]	Deqiang QU, Youlin SHANG, Yue ZHAN, Dan WU. A new parameterless filled function for global optimization problems [J]. Operations Research Transactions, 2021, 25(1): 89-95.
[14]	ZHAO Chen, LUO Ziyan, XIU Naihua. Some advances in theory and algorithms for sparse optimization [J]. Operations Research Transactions, 2020, 24(4): 1-24.
[15]	LI Jun, CHEN Jiawei, DENG Guangju. Optimality conditions of generalized convex interval valued optimization problems [J]. Operations Research Transactions, 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