华东师范大学学报（自然科学版） ›› 2020, Vol. 2020 ›› Issue (4): 108-123.doi: 10.3969/j.issn.1000-5641.201921008

• 计算机科学 • 上一篇    下一篇

改进遗传算法求解新高考背景下的排课问题

徐向阳1, 刘文伟2, 傅蝶3, 徐刚1, 金澈清1, 王祥丰1, 王江涛1   

  1. 1. 华东师范大学 软件工程学院, 上海 200062;
    2. 华东模范中学, 上海 200040;
    3. 华东师范大学 教师教育学院, 上海 200062
  • 收稿日期:2019-08-01 发布日期:2020-07-20
  • 通讯作者: 王江涛,男,副教授,研究方向为嵌入式计算机、智能传感器与云计算、智能制造与工业互联网.E-mail:jtwang@sei.ecnu.edu.cn E-mail:jtwang@sei.ecnu.edu.cn
  • 基金资助:
    国家自然科学基金广东联合基金重点支持项目(U1811264); 上海市自然科学基金(19ZR1414200)

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

XU Xiangyang1, LIU Wenwei2, FU Die3, XU Gang1, JIN Cheqing1, WANG Xiangfeng1, WANG Jiangtao1   

  1. 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:2019-08-01 Published:2020-07-20

RichHTML

166

PDF

270

摘要： 我国提出新高考改革政策后, 越来越多地区和高中开始采用走班制教学模式. 相对于传统的行政班教学模式, 走班制教学模式使排课问题的约束条件进一步增多, 学校教育资源匮乏的现象进一步凸显. 传统的排课算法不适于求解走班制教学模式下的排课问题, 而纯粹的手动编排课表不仅费时费力, 排出的课表还可能存在大量冲突, 难以保证课表的可行性和合理性. 根据走班制教学模式的特点，设计了一种获取优质可行解的方法: 首先针对走班课程提出了一种自动生成教学班组合的方法; 然后运用改进的遗传算法高效合理地求解排课问题. 实验结果表明, 该算法可获得优质的课表安排, 并且已经加入到实际应用中.

关键词: 走班制, 遗传算法, 排课问题, 排课算法, 组合优化

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.

Key words: mobile teaching system, genetic algorithm, course scheduling problem, curriculum arrangement algorithm, combinatorial optimization

中图分类号: