论文部分内容阅读
作者简介：姚建波（1972.2-），男 ，贵州大学计算机学院在职硕士研究生，遵义职业技术学院计算机系副主任,高级讲师，研究方向：计算机教育和遗传算法。
【摘要】 排课一直是教务管理中一个最重要也是最难做好的工作，因为涉及所有的师生员工，有很多硬约束，也有很多软约束，前者是必须满足的，但后是提高师生员工教学和学习积极性的关键，设计一个好的排课系统是解决此问题的最好办法，但一个好的软件中最重要的是有一套好的算法。
【关键词】 排课系统；算法；约束
【中图分类号】：G633.67【文献标识码】：B 【文章编号】：1009-9646(2008)04-0146-02
每个学期对学校教学任务进行合理安排是教务处的重要任务。其中排课是最为关键的环节，排课的依据是教学计划的编制。教务处必须在新学期开学前收集各个学院下学期的开课信息，统计下学期全校可用的教学资源，进而与各学院协调交互，确定各学院的时间组织形式和各门课程的开课与否，最后根据不同的专业背景，以班级为单位编制下学期的开课任务书。开课任务书应该包括全校每个班级的开课计划表，而开课计划表中的每个开课计划都应该包含校区、班级、教师、课程、课程类型、开课院系、人数、所需教学资源类型及数量、每周课时的情况、有特殊要求时的上课方式以及教师期望时间等。课表的编排根据上述条件进行，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题（Timetable Problem，简称TTP）。
课表的编排遵循“先难后易”的原则，逐个对开课计划进行安排。先安排特殊的开课计划，再安排一般的开课计划，但不管怎样，如下一些硬约束原则是必须要遵循的：
①在同一时间同一学生不能在两个地点上课；
②在同一时间同一教师不能给两个地点的学生上课；
③被安排的教室必须满足该课程所需的教学资源；
④在同一时间同一教室不能安排两门不同课程；
⑤教室座位数应大于等于听该次课程的学生人数；
⑥实验课、实训课、实习课等课程要根院系要求进行安排；
⑦选修课的安排应尽量不占基础课、专业基础课和专业课的时间。等等
除此之外，一般还有以下多个软约束条件：
①一个班级的上课时间尽量分布均匀；
②对于校区设置的课表的各个时段上存在一定的偏好；
③尽量满足教师上课时间的个人要求；
④教师、学生在不同校区上课时间要相对稳定；
⑤尽量满足教师在不同校区上课的喜好。等等
计算机排课，它是把排课问题化为计算领域的有约束的时空组合优化问题进行求解的。它对课表上的时间进行了分片和编号处理，使分成的每个时间片和每个教室空间组合，构建了一个个大小不等的时空组合块，并根据求解规则，对每个开课计划进行时空组合块分配，而且分配的组合(安排方案)，必须在目标空间中表现出良好的人为满意度。这些人为满意度往往不仅多个，而且是模糊的。
20世纪50年代末，国外就有人开始研究课程编排问题。经研究用来解决排课问题的方法有：模拟乎工排课法、图论方法、模拟退火法等。1976年, S Even在论文，Cooper等人，证明了课表问题属于NP完全类。就其实质而言，排课问题是一个有约束的、非线性的、模糊多目标优化的、难解的、时空组合的数学问题。即在满足各种已知的约束条件的情况下找到一组较优的时空组合，同时在具体实践上它受到教学组织形式、客观物质条件和求解目标等多种因素的相互影响，使这一问题在实际解决时呈现出受具体条件制约的特点。
S Even的论证正式确立了排课问题的学术地位，把人对课表编排复杂性的认识提高到了理论的高度。从20世纪80年代国内外就有很多专家学者用遗传算法对排课问进行研究。
遗传算法是由美国的J•Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力。它是现代有关智能计算中的关键技术之一。
无论解决哪一个问题，在明确问题的实质后，就要找出具体的解决方案，即相应的算法表示。排课问题也不例外，下面就排课问题中的主要的求解算法作具体的讨论。
1教师资源算法
为方便讨论，本文采用了以下的假设： 在老师授课时加入强制约束，一个教师只授一门课，而课程也只由一个老师教授。课程与老师之间是一对一关系。如果要考虑一个老师教授多门课程的问题，我们可以假设当第 i 位老师教授 x 门课时，可以“虚 拟”增加 x-1 个老师，每个“虚拟”老师都各任一门课程，但是这些虚 拟老师要求不可同时上一门课。在系统中为了简化系统的实现并没有实 现该约束条件，强制建立教师与课程之间的一对一的关系。
2 教室资源算法
本文将“教室可用”放入强制约束，教室根据设备情况和容量分为不同的等级系數，并采用“系数最小”优先算法，假设将设备情况系数设为：L1，L2，L3，……，Ln。教室容量系数设为：D1，D2，D3，……，Dn。则所有教室就一张由Li和Mj组成的资源表，对此资源表实行动态管理，每一个班级在排课时按“最小资源”和“最小容量”原则占用教室，以便把大容量、条件好的教室留给大班和一些临时学术报告等会议用。
3课程安排算法
课程安排算法是使所有课程得课次计划都得以时间安排的过程，它是课程安排或者遗传算法中种群初始化的必不可少的一个过程，它的部分过程也将在遗传算法的后续遗传算子操作过程中得到重用。课程安排算法流程如图3-4所示，下面通过几个嵌套循环加以说明。
最外层循环是遍历己排序开课任务数组(排序是基于排课难度的降序排列)的过程。此过程主要是定位开课任务Li，并判断此开课任务是否在排课前已预先安排完毕。若没有预先安排，则转至开课任务安排。首先是定位上课的校区以及其时间管理器，然后再日模板和节模板的有限组合中搜索可用时间，此搜索过程主要有三个嵌套循环：
3.1 日模板遍历：在上课校区的时间管理器中按课次数量(Daycnt)找到某类日模板链表，随机选择此链表中的一个结点pDTemp，并记下此结点为pftrst ；在pDTemp日模板下遍历L的课次计划Pi；判断在pDTemp日模板下，Li所有的课次计划弓是否都已经安排成功。若成功转下一个开课任务，否则pDTemp← pDTemp→pNextDayLib(到达链尾之后自动回到链头)；判断pfirst = pDTemp，若成立转冲突消除算法，否则转②。
遍历L的课次计划Pij；
j←0
求取slotcnt j
遍历slotcnt j类型的节模板，若成功找到节模板，则j ←j+1，转④;否则跳出循环pDTemp←pDTemp→pNextDayLib。
判断吞的课次计划是否全部安排完毕，若完毕结束循环转下一个开课任务，否则转②。
3.2 节模板遍历：在上课校区的时间管理器中按结束(slotcnt)找到某类节模板链表，随机选择此链表中的一个结点pSTemp，并记下此结点为pHead ；判断在pDTemp和pSTemp下，课次计划Pij是否安排成功。若成功转Pij=+1，否则pSTemp←pSTemp→ pNextSlotLib(到达链尾之后自动回到链头);判断pHead = pSTemp，若成立结束循环转pDTemp←pDTemp→pNextDayLib，否则转②。
值得注意的是，以上所用的日模板和节模板必须是对应于入的上课校区内所有的，它们的类别定位是基于L和p,v的计划的指定计。
对于多目标的排课问题，算法的设计是最为关键的，本文在综合分析排课的相的关因素后，提出了排课问题的几个主要算法，并用此对排课软件进行设计与开发，取得良好的效果。
收稿日期：2008-5-01
【摘要】 排课一直是教务管理中一个最重要也是最难做好的工作，因为涉及所有的师生员工，有很多硬约束，也有很多软约束，前者是必须满足的，但后是提高师生员工教学和学习积极性的关键，设计一个好的排课系统是解决此问题的最好办法，但一个好的软件中最重要的是有一套好的算法。
【关键词】 排课系统；算法；约束
【中图分类号】：G633.67【文献标识码】：B 【文章编号】：1009-9646(2008)04-0146-02
每个学期对学校教学任务进行合理安排是教务处的重要任务。其中排课是最为关键的环节，排课的依据是教学计划的编制。教务处必须在新学期开学前收集各个学院下学期的开课信息，统计下学期全校可用的教学资源，进而与各学院协调交互，确定各学院的时间组织形式和各门课程的开课与否，最后根据不同的专业背景，以班级为单位编制下学期的开课任务书。开课任务书应该包括全校每个班级的开课计划表，而开课计划表中的每个开课计划都应该包含校区、班级、教师、课程、课程类型、开课院系、人数、所需教学资源类型及数量、每周课时的情况、有特殊要求时的上课方式以及教师期望时间等。课表的编排根据上述条件进行，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题（Timetable Problem，简称TTP）。
课表的编排遵循“先难后易”的原则，逐个对开课计划进行安排。先安排特殊的开课计划，再安排一般的开课计划，但不管怎样，如下一些硬约束原则是必须要遵循的：
①在同一时间同一学生不能在两个地点上课；
②在同一时间同一教师不能给两个地点的学生上课；
③被安排的教室必须满足该课程所需的教学资源；
④在同一时间同一教室不能安排两门不同课程；
⑤教室座位数应大于等于听该次课程的学生人数；
⑥实验课、实训课、实习课等课程要根院系要求进行安排；
⑦选修课的安排应尽量不占基础课、专业基础课和专业课的时间。等等
除此之外，一般还有以下多个软约束条件：
①一个班级的上课时间尽量分布均匀；
②对于校区设置的课表的各个时段上存在一定的偏好；
③尽量满足教师上课时间的个人要求；
④教师、学生在不同校区上课时间要相对稳定；
⑤尽量满足教师在不同校区上课的喜好。等等
计算机排课，它是把排课问题化为计算领域的有约束的时空组合优化问题进行求解的。它对课表上的时间进行了分片和编号处理，使分成的每个时间片和每个教室空间组合，构建了一个个大小不等的时空组合块，并根据求解规则，对每个开课计划进行时空组合块分配，而且分配的组合(安排方案)，必须在目标空间中表现出良好的人为满意度。这些人为满意度往往不仅多个，而且是模糊的。
20世纪50年代末，国外就有人开始研究课程编排问题。经研究用来解决排课问题的方法有：模拟乎工排课法、图论方法、模拟退火法等。1976年, S Even在论文，Cooper等人，证明了课表问题属于NP完全类。就其实质而言，排课问题是一个有约束的、非线性的、模糊多目标优化的、难解的、时空组合的数学问题。即在满足各种已知的约束条件的情况下找到一组较优的时空组合，同时在具体实践上它受到教学组织形式、客观物质条件和求解目标等多种因素的相互影响，使这一问题在实际解决时呈现出受具体条件制约的特点。
S Even的论证正式确立了排课问题的学术地位，把人对课表编排复杂性的认识提高到了理论的高度。从20世纪80年代国内外就有很多专家学者用遗传算法对排课问进行研究。
遗传算法是由美国的J•Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力。它是现代有关智能计算中的关键技术之一。
无论解决哪一个问题，在明确问题的实质后，就要找出具体的解决方案，即相应的算法表示。排课问题也不例外，下面就排课问题中的主要的求解算法作具体的讨论。
1教师资源算法
为方便讨论，本文采用了以下的假设： 在老师授课时加入强制约束，一个教师只授一门课，而课程也只由一个老师教授。课程与老师之间是一对一关系。如果要考虑一个老师教授多门课程的问题，我们可以假设当第 i 位老师教授 x 门课时，可以“虚 拟”增加 x-1 个老师，每个“虚拟”老师都各任一门课程，但是这些虚 拟老师要求不可同时上一门课。在系统中为了简化系统的实现并没有实 现该约束条件，强制建立教师与课程之间的一对一的关系。
2 教室资源算法
本文将“教室可用”放入强制约束，教室根据设备情况和容量分为不同的等级系數，并采用“系数最小”优先算法，假设将设备情况系数设为：L1，L2，L3，……，Ln。教室容量系数设为：D1，D2，D3，……，Dn。则所有教室就一张由Li和Mj组成的资源表，对此资源表实行动态管理，每一个班级在排课时按“最小资源”和“最小容量”原则占用教室，以便把大容量、条件好的教室留给大班和一些临时学术报告等会议用。
3课程安排算法
课程安排算法是使所有课程得课次计划都得以时间安排的过程，它是课程安排或者遗传算法中种群初始化的必不可少的一个过程，它的部分过程也将在遗传算法的后续遗传算子操作过程中得到重用。课程安排算法流程如图3-4所示，下面通过几个嵌套循环加以说明。
最外层循环是遍历己排序开课任务数组(排序是基于排课难度的降序排列)的过程。此过程主要是定位开课任务Li，并判断此开课任务是否在排课前已预先安排完毕。若没有预先安排，则转至开课任务安排。首先是定位上课的校区以及其时间管理器，然后再日模板和节模板的有限组合中搜索可用时间，此搜索过程主要有三个嵌套循环：
3.1 日模板遍历：在上课校区的时间管理器中按课次数量(Daycnt)找到某类日模板链表，随机选择此链表中的一个结点pDTemp，并记下此结点为pftrst ；在pDTemp日模板下遍历L的课次计划Pi；判断在pDTemp日模板下，Li所有的课次计划弓是否都已经安排成功。若成功转下一个开课任务，否则pDTemp← pDTemp→pNextDayLib(到达链尾之后自动回到链头)；判断pfirst = pDTemp，若成立转冲突消除算法，否则转②。
遍历L的课次计划Pij；
j←0
求取slotcnt j
遍历slotcnt j类型的节模板，若成功找到节模板，则j ←j+1，转④;否则跳出循环pDTemp←pDTemp→pNextDayLib。
判断吞的课次计划是否全部安排完毕，若完毕结束循环转下一个开课任务，否则转②。
3.2 节模板遍历：在上课校区的时间管理器中按结束(slotcnt)找到某类节模板链表，随机选择此链表中的一个结点pSTemp，并记下此结点为pHead ；判断在pDTemp和pSTemp下，课次计划Pij是否安排成功。若成功转Pij=+1，否则pSTemp←pSTemp→ pNextSlotLib(到达链尾之后自动回到链头);判断pHead = pSTemp，若成立结束循环转pDTemp←pDTemp→pNextDayLib，否则转②。
值得注意的是，以上所用的日模板和节模板必须是对应于入的上课校区内所有的，它们的类别定位是基于L和p,v的计划的指定计。
对于多目标的排课问题，算法的设计是最为关键的，本文在综合分析排课的相的关因素后，提出了排课问题的几个主要算法，并用此对排课软件进行设计与开发，取得良好的效果。
收稿日期：2008-5-01