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

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

作　　者：徐向阳 刘文伟 傅蝶[3] 徐刚[1] 金澈清[1] 王祥丰 王江涛[1] XU Xiangyang;LIU Wenwei;FU Die;XU Gang;JIN Cheqing;WANG Xiangfeng;WANG Jiangtao(Software Engineering Institute,East China Normal University,Shanghai 200062,China;East China Model High School,Shanghai 200040,China;College of Teacher Education,East China Normal University,Shanghai 200062,China)

机构地区：[1]华东师范大学软件工程学院,上海200062 [2]华东模范中学,上海200040 [3]华东师范大学教师教育学院,上海200062

出　　处：《华东师范大学学报（自然科学版）》2020年第4期108-123,共16页Journal of East China Normal University(Natural Science)

基　　金：国家自然科学基金广东联合基金重点支持项目(U1811264);上海市自然科学基金(19ZR1414200)。

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]