论文部分内容阅读
摘要：由于民办高校办学层次较多课程设置的灵活性比较强等特点给教务工作带来很大的工作量，此时现行的手工排课的缺点就越来越突出。利用计算机进行排课能够快速地得到满足约束条件的可行结果，具有时间短人力省和质量高的优点，不但能使教务人员从繁杂的排课任务中解脱出来，而且对于教学的发展也起到非常重要的作用。本文主要介绍现在比较常用的几种排课算法。
关键词：民办高校 排课 算法研究
当前或者之前的一段时间里，大多数民办高校采用的是手动排课的方式进行课程安排，但是这种手动排课的方式只是适用于很小的教学集体，当学校学生基数比较大教师比较多的时候手动排课显得非常不合适，运作效率非常低。利用计算机进行排课具有时间短人力省和质量高的优点，不但能使教务人员从繁杂的排课任务中解脱出来，而且对于教学的发展也起到非常重要的作用。下面介绍几种常用的排课算法：
一、基于优先级的排课算法
从数学上讲，排课问题是一个在时间、教师、学生和教室四维空间，以教学计划和各种特殊要求为约束条件的组合规划问题。其实质就是解决各因素之间的冲突。在设计算法时，为了降低课程调度的算法复杂性，主要采用了化整为零的思想及优先级算法。
（一）排课的预处理
等价类的划分：将具有共同听课对象的任务划分在同一等价类中，在每个等价类之间只存在地点上的冲突，而没有时间上的冲突。然后按照的大小，从大到小进行处理。等价类的划分可以先按年级分，然后再按系别分。
教室分类：为了合理使用教室，我们采用了教室分类的办法，以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的教室现象。
（二）时间预处理
1.构造时间模式库
时间模式是根据教务人员的经验，为各种周学时数不同的课程指定的一种时间组合方式.例如，一门课程的周学时数为4，那么它的时间组合方式可以有：“11”，“41”；表示该课程一周上两次，分别为周一的12节和周四的12节L同时，为了达到较好的上课效果，也要对这些时间模式进行分级。
2.时间数组
为了表示班级、教师、教室的可排课时间，分别为他们建立一维数组。例如，某位教师的初始可排课时间数组为（123456 123456 123456 123456 123456）。其中共有五组数据，分别表示一周中的五天；而一组数据共有6个字符“1、2、3、4、5、6”分别表示一天中的六个时间单元。当为某位教师分配时间后，相应的那位字符就置为0L例如，某位教师的可排课时间数组为（020456 103456 003456 120456 023456），则表示这位教师在周一的12节和56节，周二的34节，周三的12节和34节，周四的56节，周五的12 节已经安排了课程，如果要再安排课程的话，就应该安排在非0的时间单元L对于班级和教室也可以进行同样的处理，分别标出可排课时间。
（三）每一子类的排课处理
在对每个子类的排课处理中，我们结合了分治法、贪婪法、回溯法三者的思想。首先，根据分治法的思想把整个排课过程分成时间分配和教室分配两个阶段。然后，依据贪婪法的算法思想，在时间分配时，总是在尚未分配的时间单元中选择上课效果最好的单元。而在时间分配发生死锁时，会向上回溯搜索到发生冲突的最近一个记录，然后对它进行重排以解决冲突。
（四）查找适当的时间模式
找到可排课时间后，就应根据课程的周学时数在时间模式库中匹配适当的时间模式。完成以上工作后，就确定了课程的上课时间和地点。如果在处理中发生死锁，则可根据回溯法的思想向上回溯搜索到发生冲突的最近一个记录，然后对它进行重排以解决死锁，如果仍不能解决死锁问题，则可以将该课程信息输出到冲突列表中。
（五）人工干预的处理
本算法所设计的人工干预过程有：等价类划分中参数的设置，教室类型的设置，时间模式库的设置，优先级函数中参数的设置。用户可以根据自己的具体要求对这些参数和库进行设置。另外，对于计算机排出的课程表，用户也可以通过人机交互进行适当调整，从而得到用户满意的课程表。
二、冲突检测算法
此算法对班级及教室划分等价类，对学校资源进行了合理的利用，以课程为中心，进行搜索匹配，取最先匹配的值；具有占有空间少，运算速度快的特点。
三、遗传算法
遗传算法是一种随机的全局搜索和优化算法。它从一个种群（Population）开始的，该群种可能是问题的一个可能潜在解集。而一个群种是由经过一系列基因（Gene）编码（Coding）的一定数目的个体（Individual）组成。每个个体可以看作带有某些特征的染色体实体（Chromosome）。生物学中，染色体是多个基因的集合，是遗传物质的主要载体，决定其内部表现。实质上在内部，染色体是某种基因组合，比如染色体中控制皮肤头发颜色这一特征的基因经过组合，就决定了生物个体的皮肤是白色的还是黑色的。因此在工作之初，需要把实体表现出来的信息特征抽象为一些位串来表示，实现外部特征和位串的映射，并且为了简化采用二进制编码。产生了初始种群之后，将“适者生存，优胜劣汰”的生物进化原理应用到实际问题的解决中。
四、PSO算法
PSO算法是基于群体的，根据对环境的适应度将群体中的个体移到好区域。将每个个体看作是具有唯一速度在多维搜索空间中飞行的没有体积的粒子，每个个体的速度由它飞行的经验和同伴的飞行经验来动态调整。进一步分析出用来结束迭代过程的条件。
粒子群优化算法PSO（Particle Swarm Optimization）是由Kennedy和Eberhart通过对鸟群、鱼群和人类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法与遗传算法类似，它也是基于群体迭代。变异算子，群体在解空间中追随最优粒子进行搜索。PSO的优势在于简单且容易实现，同时又有深刻的智能背景，既适合科学研究，又适合工程应用。鉴于PSO的发展历史尚短，它在理论基础与应用推广上都还存在一些问题，有待解决。当前PSO算法存在的问题，如：收敛速度慢、求解多峰函数优化问题时易陷入局部极小以及早熟收敛的缺点，提出了一种新的基于专业化分工与协作的寻优策略，以期对PSO算法做出改进。
粒子群优化算法是一种基于群体迭代的进化算法，以往的PSO改进方法使PSO算法的性能得到了提高，但是没能充分发挥粒子群的群体优势，我们希望就是在现有方法的基础上，充分利用粒子群的群体优势， 使之较好地适应复杂的实际环境。
参考文献
[1]李赫男.粒子群优化算法综述[J].现代计算机，2009，301（2）：22-27.
[2]陈冬亮.排课的数学模型和算法在教务管理系统中的应用研究.电脑知识与技术，2006，（6）.
[3]陈洁.学校教务部门排课问题的数学模型及算法.1999，（3）：53-56.
[4]张忠.课程表问题中的应用[J].华南金融电脑.2007（06）.
（作者单位：1青岛科技大学；2青岛黄海学院）
关键词：民办高校 排课 算法研究
当前或者之前的一段时间里，大多数民办高校采用的是手动排课的方式进行课程安排，但是这种手动排课的方式只是适用于很小的教学集体，当学校学生基数比较大教师比较多的时候手动排课显得非常不合适，运作效率非常低。利用计算机进行排课具有时间短人力省和质量高的优点，不但能使教务人员从繁杂的排课任务中解脱出来，而且对于教学的发展也起到非常重要的作用。下面介绍几种常用的排课算法：
一、基于优先级的排课算法
从数学上讲，排课问题是一个在时间、教师、学生和教室四维空间，以教学计划和各种特殊要求为约束条件的组合规划问题。其实质就是解决各因素之间的冲突。在设计算法时，为了降低课程调度的算法复杂性，主要采用了化整为零的思想及优先级算法。
（一）排课的预处理
等价类的划分：将具有共同听课对象的任务划分在同一等价类中，在每个等价类之间只存在地点上的冲突，而没有时间上的冲突。然后按照的大小，从大到小进行处理。等价类的划分可以先按年级分，然后再按系别分。
教室分类：为了合理使用教室，我们采用了教室分类的办法，以便尽可能在课程编排过程中避免上课人数少的课程盲目强占容量大的教室现象。
（二）时间预处理
1.构造时间模式库
时间模式是根据教务人员的经验，为各种周学时数不同的课程指定的一种时间组合方式.例如，一门课程的周学时数为4，那么它的时间组合方式可以有：“11”，“41”；表示该课程一周上两次，分别为周一的12节和周四的12节L同时，为了达到较好的上课效果，也要对这些时间模式进行分级。
2.时间数组
为了表示班级、教师、教室的可排课时间，分别为他们建立一维数组。例如，某位教师的初始可排课时间数组为（123456 123456 123456 123456 123456）。其中共有五组数据，分别表示一周中的五天；而一组数据共有6个字符“1、2、3、4、5、6”分别表示一天中的六个时间单元。当为某位教师分配时间后，相应的那位字符就置为0L例如，某位教师的可排课时间数组为（020456 103456 003456 120456 023456），则表示这位教师在周一的12节和56节，周二的34节，周三的12节和34节，周四的56节，周五的12 节已经安排了课程，如果要再安排课程的话，就应该安排在非0的时间单元L对于班级和教室也可以进行同样的处理，分别标出可排课时间。
（三）每一子类的排课处理
在对每个子类的排课处理中，我们结合了分治法、贪婪法、回溯法三者的思想。首先，根据分治法的思想把整个排课过程分成时间分配和教室分配两个阶段。然后，依据贪婪法的算法思想，在时间分配时，总是在尚未分配的时间单元中选择上课效果最好的单元。而在时间分配发生死锁时，会向上回溯搜索到发生冲突的最近一个记录，然后对它进行重排以解决冲突。
（四）查找适当的时间模式
找到可排课时间后，就应根据课程的周学时数在时间模式库中匹配适当的时间模式。完成以上工作后，就确定了课程的上课时间和地点。如果在处理中发生死锁，则可根据回溯法的思想向上回溯搜索到发生冲突的最近一个记录，然后对它进行重排以解决死锁，如果仍不能解决死锁问题，则可以将该课程信息输出到冲突列表中。
（五）人工干预的处理
本算法所设计的人工干预过程有：等价类划分中参数的设置，教室类型的设置，时间模式库的设置，优先级函数中参数的设置。用户可以根据自己的具体要求对这些参数和库进行设置。另外，对于计算机排出的课程表，用户也可以通过人机交互进行适当调整，从而得到用户满意的课程表。
二、冲突检测算法
此算法对班级及教室划分等价类，对学校资源进行了合理的利用，以课程为中心，进行搜索匹配，取最先匹配的值；具有占有空间少，运算速度快的特点。
三、遗传算法
遗传算法是一种随机的全局搜索和优化算法。它从一个种群（Population）开始的，该群种可能是问题的一个可能潜在解集。而一个群种是由经过一系列基因（Gene）编码（Coding）的一定数目的个体（Individual）组成。每个个体可以看作带有某些特征的染色体实体（Chromosome）。生物学中，染色体是多个基因的集合，是遗传物质的主要载体，决定其内部表现。实质上在内部，染色体是某种基因组合，比如染色体中控制皮肤头发颜色这一特征的基因经过组合，就决定了生物个体的皮肤是白色的还是黑色的。因此在工作之初，需要把实体表现出来的信息特征抽象为一些位串来表示，实现外部特征和位串的映射，并且为了简化采用二进制编码。产生了初始种群之后，将“适者生存，优胜劣汰”的生物进化原理应用到实际问题的解决中。
四、PSO算法
PSO算法是基于群体的，根据对环境的适应度将群体中的个体移到好区域。将每个个体看作是具有唯一速度在多维搜索空间中飞行的没有体积的粒子，每个个体的速度由它飞行的经验和同伴的飞行经验来动态调整。进一步分析出用来结束迭代过程的条件。
粒子群优化算法PSO（Particle Swarm Optimization）是由Kennedy和Eberhart通过对鸟群、鱼群和人类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法与遗传算法类似，它也是基于群体迭代。变异算子，群体在解空间中追随最优粒子进行搜索。PSO的优势在于简单且容易实现，同时又有深刻的智能背景，既适合科学研究，又适合工程应用。鉴于PSO的发展历史尚短，它在理论基础与应用推广上都还存在一些问题，有待解决。当前PSO算法存在的问题，如：收敛速度慢、求解多峰函数优化问题时易陷入局部极小以及早熟收敛的缺点，提出了一种新的基于专业化分工与协作的寻优策略，以期对PSO算法做出改进。
粒子群优化算法是一种基于群体迭代的进化算法，以往的PSO改进方法使PSO算法的性能得到了提高，但是没能充分发挥粒子群的群体优势，我们希望就是在现有方法的基础上，充分利用粒子群的群体优势， 使之较好地适应复杂的实际环境。
参考文献
[1]李赫男.粒子群优化算法综述[J].现代计算机，2009，301（2）：22-27.
[2]陈冬亮.排课的数学模型和算法在教务管理系统中的应用研究.电脑知识与技术，2006，（6）.
[3]陈洁.学校教务部门排课问题的数学模型及算法.1999，（3）：53-56.
[4]张忠.课程表问题中的应用[J].华南金融电脑.2007（06）.
（作者单位：1青岛科技大学；2青岛黄海学院）