开放教育排课问题约束分析与数学建模

钱海军 郭泽睿

摘 要：高等教育教学管理信息化是高校提高竞争力的关键因素。开放教育作为一种成人性质的高等教育类型，教育资源的非均衡配置限制了开放教育的发展。高校排课问题是一个多目标、多约束的资源与时空组合优化问题。排课问题的求解能够实现教育资源优化配置。本文基于开放教育的特点与教育资源的需求情况，以排课问题为切入点，分析排课问题的各种约束条件，利用数学方法构造求解排课问题的数学模型，为后续智能排课系统的设计与开发提供算法基础。

关键词：教学管理信息化；开放教育；多约束；数学模型；智能排课系统

中图分类号：TP301.6 文献标识码：A

Abstract：Informationization of higher education teaching management is the critical factor to improve the competitiveness of colleges and universities.Open education，as a type of the adult higher education，is restricted by the unbalanced allocation of educational resources.Course arrangement is a combination-optimization problem of multi-constraint and multi-objective resources and space distribution.The solution to course arrangement can optimize the allocation of educational resources.Based on the features of open education and the requirements of educational resources，the paper takes course arrangement as the breakthrough point to analyze the constraints of course arrangement and construct the mathematical model of course arrangement，which provides some algorithm foundation for the design and development of the intelligent course arrangement system.

Keywords：teaching management information；open education；multi-constraint；mathematical model；the intelligent course

arrangement system

1 引言（Introduction）

随着高等教育体制改革的不断深化，高校信息化建设成为提升教育教学水平、提高管理效率、保证教学质量、全面增强学校综合竞争力的关键因素。“十三五”规划发展期间，同属于国家高等教育序列的开放大学正在逐步进行结构调整和教学模式的转型与优化。培养目标、专业设置、课程设置等方面的重新定位，教育教学资源的优化配置，为开放教育教学管理提出了更高的要求。随着教学模式的改革、学生人数的日益扩大、开设专业的不断创新、开设课程的不断增多，教师教室资源的相对减少等因素，严重制约了开放教育的发展。尤其对于排课工作，传统的手工排课由于上述制约因素无法编制有效地课表，一方面造成人力和物力的极大浪费，工作效率不高，保密性较差，文件数据维护、更新难度大，教学资源没有发到最优化配置。另一方面，手工编制的课表会因为人为的错误而扰乱正常的教学秩序。因此，有效解决具有开放教育特征的排课问题[1]，编制科学的课程表是提高开放教育教学管理水平的关键。

2 问题描述（Problem description）

实际上排课管理工作可以归结为基于时空组合的教学资源分配问题[2，3]。排课问题是一个复杂难解的非线性、多约束、模糊多目标优化的数学问题，且已经被证明是一种NP完全问题[4]。高校作为一个教学实施的整体，编排课程表需要考虑全校性的、多方面的因素，包括教师、教室、课程、班级、时间等对象，也就是说在满足一系列的约束性条件的前提下，使得学校教学资源能够得到最优化配置。

开放教育是以学生为中心，运用现代通信技术与各种多媒体进行远程教育和面授相结合，并实行学分制的教育类型。学生对课程的选择、媒体的适用具有一定的自主性。在学习方式、学习进度、学习地点、学习时间等方面，可由学生根据自身的情况自主决定；学生基本来自在职人群，学生修读完本专业规定的毕业学分，颁发国家承认的本、专科学历证书。基于这些特征，开放教育的课程均安排在周一至周五的晚上，周末的白天与晚上。由于开放教育强调学生的自主性学习，面授课程时间通常仅为课程总学时的1/3—1/2，面授课时较少，学生的工学矛盾较突出。

排课的最终目的是合理安排教师、教室、时间等教学资源。开放教育的特殊性要求排课应在满足各种教学资源需求的基础上，编制可行性较高的课程表，尽量减少各种资源之间的冲突[5]，实现资源的优化组合[6]，缓解学生的工学矛盾，帮助开放教育学生的有效性自主学习。

3 问题描述（Problem analysis）

开放教育属于成人高等教育性质，学生的学习以自主学习方式为主，具备多元化的特征。学校需要为学生提供相对完备的学习支持服务。因此，开放教育的排课问题复杂性高，考虑的因素较多。

3.1 排课因素分析

要编制出较为科学合理的课程表，则需要从整体的角度进行综合分析，系统地考虑影响排课的各种教学因素。本研究主要从几个因素进行分析。

（1）教学任务分析

开放教育的教学仍然延续原电大系统三级分工协作的现代远程开放教育教学和教学管理机制。学校每学期开放教育的教学任务以国家开放大学与省开放大学的专业规则为核心文件，结合学校自身的教学资源配置情况，分别落实每个专业本学期开设的课程。

（2）授课时间分析

开放教育属于成人继续学历教育的国家高等教育序列。排课过程中需要关注的时间因素包括：节次、上课时间段、教学周、天数。由于开放教育自身的特征，其上课的时间段、天数、节次与普通高校的安排有较大的区别。为了有效缓解成人继续教育的工学矛盾，减少学生接受面授课的次数，开放教育授课时间一般为业余时间，把每个班级的课程主要安排在周末的白天，及平时的晚上，详见表1。

一般来讲，为了有效利用资源，开放教育设置15个教学周。部分课程如果与国家法定节假日冲突，则按照相关教学管理的要求，该课程当周的教学顺延一周。

（3）教师分析

开放教育的教学特点决定了教师类型具有多样性。学校以专任教师、兼任教师两部分来构建开放教育师资队伍。其中。兼任教师的师资来源主要由外聘（校外）教师和校内双肩挑教师（承担行政管理与教学的双重工作任务）组成。按照学校相关制度要求，双肩挑教师所承担教学任务周学时不能超过6学时/周，专任教师基本工作量为144学时/学期，周学时8学时/学期。

（4）课程分析

课程是最基本的排课单元，具有课程编号、教学班级、教室类型、周学时、任课教师、起止周等属性。开放教育的课程设置具有明显的成人教育特征，各专业所开设的课程均由开放教育专业规则进行整体描述和设计。在开放教育专业规则中，课程从课程类型、课程性质、课程模块三个维度进行定义和描述，详见表2。

表2 开放教育课程属性划分

Tab.2 Attribute division of open education curriculum

定义和描述维度 划分类别

课程类型 统设课、自设课、省开课

课程性质 必修课、选修课

课程模块 公共基础课、专业基础课、专业课、通识课、专业拓展课、综合实践

其中，统设课是由国家开放大学开设的课程，这些课程由国家开放大学管理，实行统一课程名称、统一教学大纲、统一教材、统一考试和统一评分标准。省开课由省开放大学管理，在全省电大系统内实行“五统一”，参加省电大统一命题考试。自设课则由市级电大管理，自选教材，自行命题考试。对于相同名称的课程，由于其归属类型的不同，课程编码也不相同，比如《基础会计》，会计、工商管理专科是统设课，课程编码是2003，而在旅游管理专业，属于省开课，课程编码是5857。

“以学生为中心”的开放教育采取多元化的现代教学手段为学生提供自主性学习的全方位学习支持服务。学校根据开放教育的学生的特点，课程的教学环节设置较灵活，形式多样。所有课程均设置唯一的课程编码与课程名程。通常每门课程聘请一位授课教师。开放教育实行春、秋两季的本科与专科同时招生的机制。在这种招生制度下，每学期开设的课程数量较大，尤其是公共课程在每个学期都会开设。为了能够优化教学资源配置，提高教学质量，公共课程的排课一般都采取合班教学，有些高校也称为大班教学。一门课程可能会有面授辅导、实验实训、小组协作、小组讨论等多种教学环节的设置。课程学时分配上，主要包括135学时、90学时、45学时、21学时（精讲课）等类型。为了给学生提供较完备的学习支持服务，各教学任务安排的教室尽量固定，尤其是对于英语语音、计算机应用基础、计算机类课程、会计电算化等实践环节较多，实践能力要求较高的课程来讲，需要尽量固定教室与教室的类型，这样学生与教师能够逐渐熟悉和适应教学环境与教学设备。

（5）教室分析

教室具有教室类型和容纳人数等属性。学校的教室类型分为普通多媒体教室、多媒体机房、专业实训室、听力语音室和多功能阶梯教室。每间教室都具有唯一的教室编号。阶梯教室适合安排公共基础课，如中国特色社会主义理论概论、管理学原理、政治经济学、大学英语等课程。其他类型的课程在某一个教学时段内仅安排一门课程，根据班级人数的多少可能会出现合班教学的情况。

3.2 数学描述

学校排课问题的解决与优化取决于学校教学资源的合理配置。主要涉及教师、班级、课程、教室和上课时间段等五个要素。假设学校有M位教师、N个班级、S门课程、P个教室与Q个上课时间段。根据排课问题五个要素的特点，本研究以集合的列举法方式表示这五个要素，则排课问题的数学模型描述为：

专业人才培养方案（或称为教学计划）是学校教育教学工作的核心文件。由专职教学管理人员通过对人才培养方案的全面理解与深度分析后，编制学校学期开课计划，确定该学期专业或班级所对应的课程和授课教师。根据开课计划，排课所涉及的班级、课程、教师三个核心因素被唯一确定。借助

数学工具，可以定义一个三元组，即E=

Professors>，其中Stugroups、Courses、Professors分别表示班级、课程、教师三个集合。从这个意义上讲，学校排课问题就被转化成为该三元组E搜索到一个合适的“教室与教学时间段”配对的问题。

“教室与教学时间段”的优化组合问题可以通过教室集合Classrooms与教学时间段集合Times的乘积得以解决。在数学中，利用笛卡儿积描述集合的乘积，则集合Classrooms与集合Times的笛卡儿积表示为：

CT=Classrooms×Times={（R1，T1），（R1，T2），…，（R1，TQ），

（R2，T1），（R2，T2），…，（R2，TQ），…，（Rp，T1），（Rp，T2），…，

（Rp，TQ）}

4 约束条件分析（Constraint condition analysis）

对于排课这种组合规划问题，需要通过设置合理的约束条件来实现最优解[7]。根据对排课问题的分析，可以将约束条件分为硬约束和软约束[8]。硬约束条件是衡量排课方案可行性的标准，即课程表是否能够切合实际的执行；软约束条件则是描述排课方案质量优劣和满意度高低[9]。在一定的约束范围内，排课方案满足软约束条件的数量越多，编制的课程表满意度与合理性就越高，课程表最优化程度也越高。

4.1 硬约束条件分析与建模

通过对开放教育教学过程与教学资源分析，本研究提出以下几个硬约束条件：

（1）HConstraint1：在同一教学时间段内，同一个班级不能开设一门以上的课程；对于任意教学时间段，∈Times，

（4）HConstraint4：班级的学生人数应小于等于上课教室可容纳的人数；对于任何一间能够上课的教室，则。

（5）HConstraint5：课程必须满足对教室类型的需求。学校现有教室：多媒体机房、多媒体教室、计算机网络实训室、会计电算化实训室、ERP沙盘演练实训室。

4.2 软约束条件分析与建模

排课问题的软约束条件的优化目标是实现能够较科学、较合理的排课规则，增强教学效果，提升教学水平和质量。满足软约束条件是衡量排课问题优化的关键，通过对教学任务、授课时间、教师、课程和教室等方面进行分析与整理，可以得出多个目标条件。从学校实际的情况出发，主要关注以下几个软约束条件。

（1）SConstraint1：上课时间段与教学效果有直接的关系。在课程编排过程中应尽量将较重要的课程安排在课堂教学效果较好的上课时间段。基于开放教育教学的特征，将一个教学周划分为11个时间段，详见表1。开放教育学生接受面授教学的时间段具有一定的规律性，本文通过对某个学期学生周到课率数据进行收集、统计和处理，得到如表3所示的开放教育学期平均到课率。

从表3数据可以看出，除了周末的完整时间段之外，学生到校接受面授教学比较集中的时间段从高到低进行排序：星期一、星期四、星期二、星期三、星期五。为了提高教学质量，可以认为学生较集中的时间段安排较重要的课程。

假设用表示授课时间段的优先级，其中，，表示安排星期一；，表示安排星期四；，表示安排星期二；，表示安排星期三；，表示安排星期五；星期六和星期天的全天时间段按照课程特点整体安排。

假设表示课程在整个专业规则中的重要程度，可以用课程的权重来描述。其中，“1”表示通识课，“2”表示专业拓展课，“3”表示综合实践、“4”表示专业课，“5”表示专业基础课，“6”表示公共基础课。则约束条件优化目标为：

（2）SConstraint2：根据学期教学的执行计划，尽量满足部分教师提出的上课时间与教室属性的要求。教师按照职称的级别分为高级（教授、副教授、研究员、副研究员、高级实验师）、中级（讲师、工程师、实验师）、初级（助教）等三个级别。

假设职称的级别系数为，值分别是1，2，3；同时假设教师在规定时间段上课的意愿程度系数为，其中“2”表示愿意，“1”表示可以接受，“0”表示不愿意；则约束条件优化目标为：

（3）SConstraint3：根据开放教育的学生特点，针对多学时课程（≥45学时，周学时≥6），授课时间应尽量保证间隔一天以上，这样可以有效保证面授教学的学习效果。假设一门课程的授课时间间隔为i天的教学效果系数为，设定1，2，3，4，5天的系数值分别为1，4，5，3，2，为课程的权重，则约束条件优化目标为：

（4）SConstraint4：同一课表中班级的课程密度尽量均匀。由于开放教育教学时间的限制，本约束仅考虑班级的周课时分配的合理性，即应避免某个班级某一周课程较多而另外一周课程较少的情况。某个班级的周课时分布均匀程度为：

其中，ed班级GN在第d周上课的课时数，则约束条件优化目标为：

其中，N表示全校班级的总数。

（5）SConstraint5：教室利用率最大化，即根据班级学生的人数分配教室。假设某个班级人数为xN与教室可容纳的学生人数为yS之间的比值，比值越大，教室利用率越高，最大值为1，则约束条件优化目标为：

5 结论（Conclusion）

本文基于开放教育的特征与排课工作的特点，以整体的角度考虑教学资源的分配问题。通过对排课关键因素的综合分析，提出问题并建立数学模型，解决开放教育教学资源优化配置问题，实现了排课问题的数学描述，为后续采用人工智能算法开发和设计排课系统提供理论基础。

参考文献（References）

[1] Adewumi A O，Sawyerr B A，Montaz A M.A Heuristic Solution to the University Timetabling Problem[J].Engineering Computations，2009，26（8）：972-984.

[2] Pillay N，Banzhaf W.A Study of Heuristic Combinations for Hyper-heuristic Systems for the Uncapacitated Examination Timetabling Problem[J].European Journal of Operational Research，2009，197（2）：482-491.

[3] S.Yang and S.N.Jat.Genetic Algorithms and Local Search Strategies for University Course Timetabling[J].IEEE Transactions on Systems，Man，and Cybernetics，Part C：Applications and Reviews，2011，1（41）：93-106.

[4] Shi Juan.Research on Application of IGA （Immune Genetic Algorithm） to the Solution of Course-timetabling Problem[C].Proceedings of 2009 4th International Conference on Computer Science and Education，Nanning，China，2009：1105-1109.

[5] 徐锦国.基于遗传算法的排课系统研究[D].西安：西安石油大学，2010.

[6] 苏明杰，陈建勋.基于线性规划模型的高校排课系统[J].微计算机信息，2011，27（8）：197-200.

[7] Abuhamdah A，Ayob M.Multi-neighborhood Particle Collision Algorithm for Solving Course Timetabling Problems[C].Proceedings of the 2nd Conference on Data Mining and Optimization，2009：21-27.

[8] 张学平，朱颢东，吴洪丽.基于三维免疫遗传算法的高校排课问题研究[J].计算机工程与应用，2012，48（5）：217-220.

[9] 朱颢东，李红婵.采用十进制最佳个体置换遗传算法求解高校排课问题[J].计算机工程与科学，2011，33（6）：186-190.

作者简介：

钱海军（1979-），男，硕士生，副教授.研究领域：系统理论，

数据挖掘.

郭泽睿（1998-），男，本科生.研究领域：应用数学.