论文部分内容阅读
摘 要：随着技工院校的课程改革，编排课程表这项工作变得越来越复杂。如果还采用人工排课的话，不仅费时费力，还容易出现冲突、错漏等问题。为了有效地解决排课表问题，本文采用回溯算法来解决复杂的排课表问题，先创建优先级，再根据优先级从高到低的进行依次编排课程。最终生成课表。回溯法方便简单，易于软件实现。
关键词：回溯算法 自动排课 应用软件
中图分类号：G71 文献标识码：A 文章编号：1673-9795（2013）09（b）-0133-02
技工院校的课表安排是一项复杂又叫人头痛的工作，具体表现在以下几个方面：（1）老师、学生、场地三者要保持协调统一；（2）个别专业实行模块化教学，即在一定周期内上完一门课，接下来的周期再上另一门课，对授课场地造成极大浪费；（3）同一个老师专业跨度大，同时任教不同专业，甚至跨系部，如公共类课程；（4）招生规模的不稳定性使得教学设备数量无法完全满足学生需求。
基于以上复杂多变的情况，要想人工调整课表是极困难的。现在已有很多种自动排课系统，但大多不适合技工院校的自动排课系统。其主要原因是：现在一些比较成功的自动排课系统适合中小学的课程安排。技工院校的课程多采用一体化教学模式，却没有一个科学的、合理的算法解决这个排课问题。笔者在2012年采用了回溯算法制作了一个自动排课系统，通过遍历搜索确定优先级，然后将课程进行合理的排列，从而避免发生冲突和矛盾，经过三个学期的运行，该系统的可行性强，易操作，在教学实践中发挥了重要作用。
1 排课基本原则
如何排出科学、合理和实用的课程表呢？必须从实际出发，笔者根据本校的课程安排实际情况，制定了下列规则：（1）同一教师不能在同一时间节点安排两个或以上授课任务；（2）同一场地不能在同一时间节点安排两个或以上授课任务；（3）小班教室或实训室不能在同一时间节点安排两名或以上教师授课；（4）教场的工位数要大于等于上课的人数；（5）教室的类型要与课程的类型一致。如，机房课与上机课、舞蹈室与舞蹈课等；（6）尽量安排实训课4节连上，这符合多数一体化教学的要求；（7）尽量将文化理论课的教学安排在上午，而将实训课，体育课等课程安排在第3节到第6节之间；（8）尽量避免教师的连续工作，即不能让一个教师在一天或连续几天内完成多个教学工作；（9）在某个特定的时间段不要安排教学任务，以便教师和学生都能够利用这个时间进行一些教学工作以外的活动；（10）可根据特殊要求，对特殊的教师安排特定的时间；（11）避免同一班级的同一门理论课连续出现。
2 基于回溯算法自动排课的核心思想
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找最优解的方法，就称作“回溯法”。
2.1 确定优先级
回溯算法在很多自动课表系统上应用较多，回溯算法是排课系统寻找最优解的有效算法。根据课程安排的要求先确定优先级，优先级的确定要根据专业课的安排优先于非专业课、参与班级较多的课程优先调度、阶段课程周次靠前的优先于周次靠后的、需四节连上的一体化课程优先于两节连上的课程、对时间有特殊要求的课程先调度、对教室有特殊要求的课程优先调度。根据以上原则，设计了一个优先级函数为：
G（x）=C1×J（x）+C2×W（x）+C3×S（x）+C4×T（x）+C5×L（x）+C6×P（x）
其中G（x）表示优先级函数；J（x）表示课程的级别；W（x）表示该课程开始于第几周；S（x）表示该课程的参与班级数；T（x）表示教师承担课程的任务量；L（x）表示需特殊安排的教师；P（x）表示教室的级别；C1，C2，C3，C4为可调整的参数，由G（x）可知，课程级别越高，课程开始周数越靠前，参与班越多，教师任务越重，有特殊要求的课程的优先级超高，这样按优先级进行降序排序，优先级高的优先处理。函数说明见表1。
2.2 核心算法流程
确定好优先级数据后，就可按回溯算法进行排课表了。在排课表过程中，首先从课程数据表中取出优先级别高的课程，再从教室信息表中查找合适的教室，然后添加数据到课程表中，并将总课节数减2或减4。如遇到固定时间的课程，领导的课程应先安排。同時还要考虑教室的利用率，即上课人数与教室资源的比值，比值越大越好，最大值为1。
基本查找思路如下，流程图如图1所示：（1）根据G（X）函数，创建优先级，并按降序，转向（2）；（2）按照优先级从大到小进行排课，如都排完，转向（12）；否则，转向（3）；（3）取出需要安排的课程数据，并将课节数赋给变量S，转向（4）；（4）根据课程性质判断是否为专业课，如果是，转向（5）；否则，并转向（7）；（5）判断是否是一体化课程，如果是，转向（6），否则，转向（7）；（6）判断当前课节数是否大于等于4，如果是将变量N赋值4，转向（8）；否则，转向（7）；（7）将变量N赋值为2，转向（8）；（8）课程是否对教室有特殊要求，如果是，转向（9）；否则，转向（10）；（9）安排特殊教室，转向（11）；（10）安排普通教室，转向（11）；（11）S=S-N，判断S是否等于0，如果是，转向（2）；否则，转向（4）；（12）所有课程安排结束。
要求1：（9）、（10）是指教室所容纳的学生人数≥班级学生总人数。命令如下：
Select@studentSum=班级人数from班级信息表where班级编号in（select班级编号form课程信息表where课程编号=@courseID）/*@courseID为当前课程编号*/
Select教室编号from教室信息表where 容纳人数>=@studentSum
要求2：自动排课系统不仅是上面12步就可完成的，还需考虑其他情况，减少排课的冲突。如4节连上的课程无合适教室（或实训室）安排，则可按2节连上的形式分两次安排；无需教室的课程，先找下午安排，如下午都已安排了课程，再安排上午上课。
3 数据库的设计
数据库的设计根据内容的需求而定，主要包含5个信息表，分别为：课程信息表、课程安排表、教师信息表、班级信息表、教室信息表。对于数据表的设计及主要字段如表2。
4 系统的实现
该系统已在我校计算机教学部进行了初步测试，效果良好。使用为Visual C#和SQL2005实现。为应对不可预料的突发情况或教师个人特殊情况的出现，系统中还加入了手动排课功能，对课程表进行局部调整。系统运行情况截图如图2所示。
5 结语
自动排课系统采用了回溯算法，极大地减少了冲突死锁的概率，从而减少了人工干预的次数与时间，提高了排课效率。但全自动排课还有不如人意的地方，比如当教室比较紧张时，会出现个别课程安排不合理，需手动调整等情况，我将继续研究，改进算法，制作出更完善的排课系统。
参考文献
[1] 彭复明.基于矩阵优化的机房自动排课算法[J].中国制造业信息化，2009（11）：52-54.
[2] 王帮海，李振坤.基于贪婪算法的自动排课表系统的研究与实现[J].计算机工程与设计，2008，29（18）：4843-4846.
[3] 陆峰，李新.自动排课系统算法的设计与实现[J].微机发展，2005，15（11）：60-63.
[4] 张健.基于图论的高校排课系统实现[J].重庆师范大学学报，2005（1）：35-38.
关键词：回溯算法 自动排课 应用软件
中图分类号：G71 文献标识码：A 文章编号：1673-9795（2013）09（b）-0133-02
技工院校的课表安排是一项复杂又叫人头痛的工作，具体表现在以下几个方面：（1）老师、学生、场地三者要保持协调统一；（2）个别专业实行模块化教学，即在一定周期内上完一门课，接下来的周期再上另一门课，对授课场地造成极大浪费；（3）同一个老师专业跨度大，同时任教不同专业，甚至跨系部，如公共类课程；（4）招生规模的不稳定性使得教学设备数量无法完全满足学生需求。
基于以上复杂多变的情况，要想人工调整课表是极困难的。现在已有很多种自动排课系统，但大多不适合技工院校的自动排课系统。其主要原因是：现在一些比较成功的自动排课系统适合中小学的课程安排。技工院校的课程多采用一体化教学模式，却没有一个科学的、合理的算法解决这个排课问题。笔者在2012年采用了回溯算法制作了一个自动排课系统，通过遍历搜索确定优先级，然后将课程进行合理的排列，从而避免发生冲突和矛盾，经过三个学期的运行，该系统的可行性强，易操作，在教学实践中发挥了重要作用。
1 排课基本原则
如何排出科学、合理和实用的课程表呢？必须从实际出发，笔者根据本校的课程安排实际情况，制定了下列规则：（1）同一教师不能在同一时间节点安排两个或以上授课任务；（2）同一场地不能在同一时间节点安排两个或以上授课任务；（3）小班教室或实训室不能在同一时间节点安排两名或以上教师授课；（4）教场的工位数要大于等于上课的人数；（5）教室的类型要与课程的类型一致。如，机房课与上机课、舞蹈室与舞蹈课等；（6）尽量安排实训课4节连上，这符合多数一体化教学的要求；（7）尽量将文化理论课的教学安排在上午，而将实训课，体育课等课程安排在第3节到第6节之间；（8）尽量避免教师的连续工作，即不能让一个教师在一天或连续几天内完成多个教学工作；（9）在某个特定的时间段不要安排教学任务，以便教师和学生都能够利用这个时间进行一些教学工作以外的活动；（10）可根据特殊要求，对特殊的教师安排特定的时间；（11）避免同一班级的同一门理论课连续出现。
2 基于回溯算法自动排课的核心思想
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找最优解的方法，就称作“回溯法”。
2.1 确定优先级
回溯算法在很多自动课表系统上应用较多，回溯算法是排课系统寻找最优解的有效算法。根据课程安排的要求先确定优先级，优先级的确定要根据专业课的安排优先于非专业课、参与班级较多的课程优先调度、阶段课程周次靠前的优先于周次靠后的、需四节连上的一体化课程优先于两节连上的课程、对时间有特殊要求的课程先调度、对教室有特殊要求的课程优先调度。根据以上原则，设计了一个优先级函数为：
G（x）=C1×J（x）+C2×W（x）+C3×S（x）+C4×T（x）+C5×L（x）+C6×P（x）
其中G（x）表示优先级函数；J（x）表示课程的级别；W（x）表示该课程开始于第几周；S（x）表示该课程的参与班级数；T（x）表示教师承担课程的任务量；L（x）表示需特殊安排的教师；P（x）表示教室的级别；C1，C2，C3，C4为可调整的参数，由G（x）可知，课程级别越高，课程开始周数越靠前，参与班越多，教师任务越重，有特殊要求的课程的优先级超高，这样按优先级进行降序排序，优先级高的优先处理。函数说明见表1。
2.2 核心算法流程
确定好优先级数据后，就可按回溯算法进行排课表了。在排课表过程中，首先从课程数据表中取出优先级别高的课程，再从教室信息表中查找合适的教室，然后添加数据到课程表中，并将总课节数减2或减4。如遇到固定时间的课程，领导的课程应先安排。同時还要考虑教室的利用率，即上课人数与教室资源的比值，比值越大越好，最大值为1。
基本查找思路如下，流程图如图1所示：（1）根据G（X）函数，创建优先级，并按降序，转向（2）；（2）按照优先级从大到小进行排课，如都排完，转向（12）；否则，转向（3）；（3）取出需要安排的课程数据，并将课节数赋给变量S，转向（4）；（4）根据课程性质判断是否为专业课，如果是，转向（5）；否则，并转向（7）；（5）判断是否是一体化课程，如果是，转向（6），否则，转向（7）；（6）判断当前课节数是否大于等于4，如果是将变量N赋值4，转向（8）；否则，转向（7）；（7）将变量N赋值为2，转向（8）；（8）课程是否对教室有特殊要求，如果是，转向（9）；否则，转向（10）；（9）安排特殊教室，转向（11）；（10）安排普通教室，转向（11）；（11）S=S-N，判断S是否等于0，如果是，转向（2）；否则，转向（4）；（12）所有课程安排结束。
要求1：（9）、（10）是指教室所容纳的学生人数≥班级学生总人数。命令如下：
Select@studentSum=班级人数from班级信息表where班级编号in（select班级编号form课程信息表where课程编号=@courseID）/*@courseID为当前课程编号*/
Select教室编号from教室信息表where 容纳人数>=@studentSum
要求2：自动排课系统不仅是上面12步就可完成的，还需考虑其他情况，减少排课的冲突。如4节连上的课程无合适教室（或实训室）安排，则可按2节连上的形式分两次安排；无需教室的课程，先找下午安排，如下午都已安排了课程，再安排上午上课。
3 数据库的设计
数据库的设计根据内容的需求而定，主要包含5个信息表，分别为：课程信息表、课程安排表、教师信息表、班级信息表、教室信息表。对于数据表的设计及主要字段如表2。
4 系统的实现
该系统已在我校计算机教学部进行了初步测试，效果良好。使用为Visual C#和SQL2005实现。为应对不可预料的突发情况或教师个人特殊情况的出现，系统中还加入了手动排课功能，对课程表进行局部调整。系统运行情况截图如图2所示。
5 结语
自动排课系统采用了回溯算法，极大地减少了冲突死锁的概率，从而减少了人工干预的次数与时间，提高了排课效率。但全自动排课还有不如人意的地方，比如当教室比较紧张时，会出现个别课程安排不合理，需手动调整等情况，我将继续研究，改进算法，制作出更完善的排课系统。
参考文献
[1] 彭复明.基于矩阵优化的机房自动排课算法[J].中国制造业信息化，2009（11）：52-54.
[2] 王帮海，李振坤.基于贪婪算法的自动排课表系统的研究与实现[J].计算机工程与设计，2008，29（18）：4843-4846.
[3] 陆峰，李新.自动排课系统算法的设计与实现[J].微机发展，2005，15（11）：60-63.
[4] 张健.基于图论的高校排课系统实现[J].重庆师范大学学报，2005（1）：35-38.