An improved genetic algorithm to solve the course scheduling problem in the context of new college entrance examinations

XU Xiangyang; LIU Wenwei; FU Die; XU Gang; JIN Cheqing; WANG Xiangfeng; WANG Jiangtao

doi:10.3969/j.issn.1000-5641.201921008

Issue 4

Jul. 2020

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2020 > (4): 108-123

XU Xiangyang, LIU Wenwei, FU Die, XU Gang, JIN Cheqing, WANG Xiangfeng, WANG Jiangtao. An improved genetic algorithm to solve the course scheduling problem in the context of new college entrance examinations[J]. Journal of East China Normal University (Natural Sciences), 2020, (4): 108-123. doi: 10.3969/j.issn.1000-5641.201921008

Citation:

XU Xiangyang, LIU Wenwei, FU Die, XU Gang, JIN Cheqing, WANG Xiangfeng, WANG Jiangtao. An improved genetic algorithm to solve the course scheduling problem in the context of new college entrance examinations[J]. Journal of East China Normal University (Natural Sciences), 2020, (4): 108-123. doi: 10.3969/j.issn.1000-5641.201921008

Citation:

XU Xiangyang, LIU Wenwei, FU Die, XU Gang, JIN Cheqing, WANG Xiangfeng, WANG Jiangtao. An improved genetic algorithm to solve the course scheduling problem in the context of new college entrance examinations[J]. Journal of East China Normal University (Natural Sciences), 2020, (4): 108-123. doi: 10.3969/j.issn.1000-5641.201921008

PDF( 1470 KB)

An improved genetic algorithm to solve the course scheduling problem in the context of new college entrance examinations

doi: 10.3969/j.issn.1000-5641.201921008

1.
Software Engineering Institute, East China Normal University, Shanghai　200062, China
2.
East China Model High School, Shanghai　200040, China
3.
College of Teacher Education, East China Normal University, Shanghai　200062, China

Received Date: 2019-08-01
Available Online: 2020-07-20
Publish Date: 2020-07-20

Abstract

Abstract

After the new policy for college entrance examination reform was put forward in China, an increasing number of regions and senior high schools began to adopt the mobile teaching system. Compared with traditional teaching schedules, which use an executive class, this pattern further increased the challenges of scheduling, and the lack of school education resources has become more prominent. The traditional algorithm for curriculum arrangement is not suitable for solving the scheduling problem that exists with the mobile teaching system. Pure manual scheduling is not only time-consuming and laborious, but there may also be unforeseen conflicts; it is difficult to guarantee the feasibility and rationality of a curriculum. Given the characteristics of a mobile teaching system pattern, this paper presents a method for obtaining high-quality feasible solutions to deal with course scheduling. First, a method for automatically generating combinations of mobile teaching classes is proposed. Second, the improved genetic algorithm is used to solve the scheduling problem efficiently and reasonably. Experiments show that the proposed algorithm can achieve a high-quality curriculum, and the method has been applied in practical applications.
- mobile teaching system,
- genetic algorithm,
- course scheduling problem,
- curriculum arrangement algorithm,
- combinatorial optimization

FullText(HTML)

References(19)

References

[1]	夏永庚, 朱琴. 走班制背景下高中班主任德育工作的挑战与应对 [J]. 现代基础教育研究, 2019, 33(1): 215-220.
[2]	GOTLIEB C C. The construction of class-teacher timetables [J]. Communications of the ACM, 1962, 5(6): 73-77.
[3]	EVEN S, ITAI A, SHAMIR A. On the complexity of time table and multi-commodity flow problems [C]//16th Annual Symposium on Foundations of Computer Science (SFCS 1975). IEEE, 1975: 184-193. DOI: 10.1109/SFCS.1975.21.
[4]	张艳红, 王玲玲, 腾东兴. 基于空间模型和遗传算法的高校排课系统 [J]. 计算机系统应用, 2015, 24(9): 49-55. DOI: 10.3969/j.issn.1003-3254.2015.09.008.
[5]	袁俊毅. 基于遗传算法的高校教务排课系统设计与实现 [D]. 长沙: 湖南大学, 2017.
[6]	姜婧, 白似雪. 遗传算法的改进及其在排课问题中的应用 [J]. 南昌大学学报(理科版), 2018, 42(4): 388-392.
[7]	唐环, 高健. 在中学排课问题中实用的模拟退火算法应用 [J]. 计算机系统应用, 2017, 26(10): 225-230.
[8]	THEPPHAKORN T, PONGCHAROEN P, HICKS C. An ant colony based timetabling tool [J]. International Journal of Production Economics, 2014, 149: 131-144. DOI: 10.1016/j.ijpe.2013.04.026.
[9]	张媛, 祁兰. 基于禁忌搜索的排课系统的设计 [J]. 电子设计工程, 2016, 24(22): 71-73.
[10]	FONG C W, ASMUNI H, LAM W S, et al. A novel hybrid swarm based approach for curriculum based course timetabling problem [C]//2014 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2014: 544-550.
[11]	王卫红, 李文琼. 基于改进遗传算法的高中走班制排课算法 [J]. 浙江工业大学学报, 2016, 44(6): 601-607, 670. DOI: 10.3969/j.issn.1006-4303.2016.06.002.
[12]	陈璐, 王秀. 改进遗传算法求解走班制下的排课问题 [J]. 计算机工程与应用, 2019, 55(6): 218-224.
[13]	马辉辉. 走班制的实施与注意问题 [J]. 教育与教学研究, 2016, 30(2): 99-103. DOI: 10.3969/j.issn.1674-6120.2016.02.019.
[14]	张贵军, 陈安, 胡俊. 基于蒙特卡洛遗传算法的排课问题研究 [J]. 实验技术与管理, 2019, 36(3): 170-174.
[15]	冯智莉, 易国洪, 李普山, 等. 并行化遗传算法研究综述 [J]. 计算机应用与软件, 2018, 35(11): 1-7, 80.
[16]	葛继科, 邱玉辉, 吴春明, 等. 遗传算法研究综述 [J]. 计算机应用研究, 2008, 10: 2911-2916. DOI: 10.3969/j.issn.1001-3695.2008.10.008.
[17]	王赞, 樊向宇, 邹雨果, 等. 一种基于遗传算法的多缺陷定位方法 [J]. 软件学报, 2016, 27(4): 879-900.
[18]	雷英杰, 张善文. MATLAB遗传算法工具箱及应用 [M]. 西安: 西安电子科技大学出版社, 2014.
[19]	董玉锁, 贺波, 尹迎, 等. 利用改进遗传算法破解排课难题 [J]. 中国教育技术装备, 2018(1): 16-19. DOI: 10.3969/j.issn.1671-489X.2018.01.016.