基于克隆原理的排课算法研究

王莲娟　李星华

摘  要：高校排课问题是数学和计算机领域的一个经典问题，如何将教室、教师、课程、班级、时间段等要素进行合理的安排，是排课算法需要重点研究和解决的问题。文章对排课问题的功能需求分析、数据库设计、算法设计等几个部分进行了阐述，提出了基于克隆原理的排课算法，通过时间单元对象的引入与时间段的合理划分并与其他对象进行绑定实现对其他对象的克隆，可以把四维空间的问题进行转化，从而简化问题的复杂度，使复杂的排课问题得到解决。

关键词：克隆原理;排课;时间单元

中图分类号：TP301.6      文献标识码：A 文章编号：2096-4706（2020）02-0018-03

Abstract：Course scheduling is a classic problem in the field of mathematics and computer science. The major issue that the course scheduling algorithm studies and aims to solve are how to arrange reasonably and scientifically the many factors including classrooms，teachers，courses，classes and time frame，etc. Through the elaboration of the functional needs analysis of course scheduling issues，design of database and algorithm，the author manages to propose the course scheduling algorithm based on clone principles. Through importing the object of time unit and dividing time frame reasonably and binding with other objects，the clone of these objects can be turned into reality，so that the problems in four-dimensional space can be converted and the complexity of the problems can be simplified，by which the complicated problem of course scheduling will be solved.

Keywords：clone theory;course scheduling;time unit

0  引  言

排课工作一直是各个学校教务处在教学管理中的重要工作之一，随着招生规模的持续扩大，广大高职院校的专业体系也变得越来越丰富和完善，这就为排课工作带来了巨大的压力。[1]在计算机技术出现之前，统筹安排各班级上课的时间需要人工来完成，在编排过程中花费大量的时间和精力，然而结果并不能令人满意，经常会出现教师上课冲突的情况。随着计算机技术的不断发展，开发一个智能排课系统，让计算机来代替人工排课成为可能。

智能排课系统开发主要包括服务器的建立和网页的开发两个方面。该系统能够实现上课时间的安排、教室的安排，课程的安排、教师授课的安排，以及它们之间的不冲突和资源的高效利用等功能;切合学院教学需要，降低了排课管理工作的工作量，提高了工作效率，同时课程安排完成后，可迅速生成课表情况信息，为教学工作提供更多的方便。排课系统中最核心的技术就是排课算法，科学的排课算法能更好地利用各种资源，使课程安排更为合理，提高工作效率。

1  功能需求分析

我院现有在校生3893人，教学班127个，多媒体教室133间，所有教室均安装有多媒体教学设备，如高性能计算机、高清投影设备、无线麦克风、公放设备等，可以满足所有班级日常教学的需求。按照目前的教学资源配置情况，每个班级可以固定一间教室授课，也可以采用流动教室形式授课。

排课问题主要综合考虑的要素有教室、課程、教师、班级和时间段，将五个要素进行合理的组合，使资源配置最优化，得到最优的排课方案。排课算法重点要解决各种要素之间的冲突问题：同一时间段一个班级只能选择一门课程;同一时刻同一个教室只能上一门课程;同一时刻一个教师只能上一门课程;给班级安排的教室必须可以容纳所有上该课程的学生;必须要有特定的教室提供给特定课程使用;尽可能满足大多数人相邻两节课上课地点近;体育课后尽量不要安排课程;[2]所有课程以2课时为一个单元进行编排;周三下午和周五下午不排课;所有课程从第一周上到最后一周。

正式排课之前需要设置开课计划，主要任务是设置班级、课程、教师的对应关系，为排课做好前期的准备工作。

2  数据库设计

2.1  E-R模型

本排课算法中主要涉及的实体对象有学生、教师、教室、班级、课程、时间单元等。学生实体模型如图1所示，教师实体模型如图2所示，班级实体模型如图3所示，课程实体模型如图4所示，教室实体模型如图5所示，时间单元实体模型如图6所示，各实体联系如图7所示。

2.2  数据表设计

根据E-R模型进行数据库设计，需要在数据库中构建如下数据表：

学生表（学号，姓名，性别，身份证号，系，专业，班级……）

教师表（工号，姓名，性别，身份证号，部门，职称……）

班级表（代码，名称，所在系，专业，人数，辅导员，教室）

课程表（代码，名称，开设系，课时，学分，性质）

时间单元表（代码，时间段）

排课表（班级代码，课程代码，教师工号，上课时间单元，课程学时标识）

3  算法设计

3.1  基于克隆原理的排课算法规则

（1）教师和学生都不能发生课时冲突，即没有教师要同时给两个（或两个以上的）班上课，也没有一个班要同时上两门（或两门以上）不同的课程;（2）所有课程以2课时为一个单元进行编排;（3）时间单元共分成20个，每周一至周五每天4个单元，每个单元包含2个课时，对20个单元依次编号，1-20号;（4）周三和周五下午不排课，即11-12、19-20时间单元不排课;（5）每天的课程尽可能安排在前3个单元，即1-3、5-7、9-10、13-15、17-18时间单元优先排课;（6）所有课程从第一周上到最后一周;（7）所有教室均为统一规格的多媒体教室。

3.2  设置开课计划

设置开课计划的主要任务是设置班级、课程、教师的对应关系，存入排课表中。每2个课时为一个单元进行编排，如果一个教师给一个班级上的是4个课时的课程，则在排课表中出现2条记录，通过增加一个课程学时标识字段来区分（1表示这门课的1-2课时，2表示这门课的3-4课时，依此类推）。

3.3  基于克隆原理的排课算法设计

长期以来，人们在研究该如何排课这个问题时，选择使用过许多不同的算法，如遗传算法、模拟退火算法、回溯搜索算法、图论算法等。[3]通过对现有排课算法的研究和学习，为了简化算法，本算法在研究过程中按照班级固定教室的规则进行排课，可将教室作为班级的属性。排课过程中先统一进行编排，对于个别课程有特殊要求的进行人工微调。

排课过程中以班级对象为基础，遍历所有的班级对象，对每个班级的所有课程进行编排，在编排每一门课程时需要判断是否可以正常编排到对应的时间单元上（主要判断所排时间单元对应的教师是否可以正常排课——每个教师分配到不同的时间单元，就相当于变成了多个教师克隆，当一个教师对应的时间单元已经被安排，则相当于这个教师克隆被占用，则后面再给这个教师排课时就不能再使用这个教师克隆。这里可以称为克隆原理，同样适用于教室和时间单元相结合，一个教室分配到不同的时间单元，就相当于多个教室克隆）。如果前面一个单元不能正常安排该门课程，则将该门课程往后面一个单元进行编排，直至把當前课程安排到一个时间单元上为止。安排完一门课程之后进行下一门课程的编排，直至所有课程编排结束为止。

这里的克隆原理又可以理解为时间转实体原理，即将包含有时间的四维空间问题中的时间维度进行转化，把时间维度分解成若干个时间单元和教师、教室对象进行绑定，相当于克隆出来多个教师和教室对象，从而简化问题复杂度，达到实现排课算法的可行性的目的。

4  结  论

本文所阐述的基于克隆原理的排课算法是针对班级固定教室进行的研究，可以完成基本的排课功能，由于我院教学资源充足，按照固定教室的形式设置算法，可以满足我院日常排课的要求。但在实际排课过程中，很多学校的教学资源有限，采取固定教室的形式排课，无法满足日常教学的需求。为了算法能够得到进一步推广，更好地利用现有的教学资源，需要把所有教室轮换起来，每个班级都没有固定教室，下一步将会针对这个问题对算法进一步优化，使排课算法更科学合理。

参考文献：

[1] 梁利亭.遗传算法在高职院校排课问题中的研究与应用 [J].湖北开放职业学院学报，2019，32（1）：76-78.

[2] 邵舒佳，赵盈，杜战其.基于遗传算法的高校排课分析 [J].科技创新与生产力，2015（11）：42-43+46.

[3] 李昕怡，苏振华.基于边着色理论的排课问题的应用 [J].怀化学院学报，2018，37（5）：33-36.

作者简介：王莲娟（1987.11-），女，汉族，北京人，教务学籍管理科副科长，本科，研究方向：算法、计算机应用;李星华（1979.08-），男，蒙古族，辽宁朝阳人，学生科科长，副研究员，研究生，研究方向：算法、数据库、教育管理。