一种面向教学的排课冲突检测算法
2015-12-15朱维军王迤冉
朱维军，王迤冉
(1.郑州大学 信息工程学院，河南 郑州 450001; 2.周口师范学院 计算机与科学技术学院，河南 周口 466001)
一种面向教学的排课冲突检测算法
朱维军1，王迤冉2
(1.郑州大学 信息工程学院，河南 郑州 450001; 2.周口师范学院 计算机与科学技术学院，河南 周口 466001)
摘要：排课算法可在大规模空间上对排课元素实施自动编排.然而，目前未见报道有关针对已排好的课表实施正确性检测的通用全自动方法.为此，给出课表所需满足约束条件的形式化描述；在此基础上，分别给出3个子算法以检测3种约束条件；顺序调用这些子算法，即可得到一种面向教学实践的排课冲突检测算法.检测实验证实了新方法的有效性.
关键词：排课系统；算法；冲突检测；课程表
0引言
利用计算机进行自动排课可以大幅提高排课效率，并增强课表的合理性.排课算法为排课系统提供核心引擎，因而对算法的研究是提升排课效率及确保正确性的关键.目前为止已发展成熟并被广泛使用的排课算法有：遗传算法[1]、贪心算法[2-3]、回溯算法[4]等.这些算法各有其优势与不足，基于这些算法的系统也在实际的高校排课中发挥了重要作用.
然而，所谓通用的高校排课系统并不能满足不同教学单位的个性化需求，因此，用户单位的二次开发在所难免.不幸的是，二次开发后的系统并不能自动确保课表的正确性，也就是说，课表需要满足的硬约束条件不再必然被满足.如果此问题不能被有效解决，在实践中甚至有可能发生大面积教学事故.为此，用户单位需要一套与排课系统无关的独立检测系统，来检测课表中是否存在冲突.
一系列工作针对此问题开展研究.文献[5]指出了上述问题的具体几个方面，然而，未给出检测算法.文献[6]给出了带有冲突检测的排课系统，其冲突检测算法只针对软约束条件，并不对课表是否满足硬约束条件进行检测.文献[7]使用占位数组设计排课算法，冲突检测为设计课表提供依据，却并没有针对通用排课算法给出通用的冲突检测方法.文献[8]给出了对课表进行冲突检测的算法，这个算法发挥功能与排课算法无关，然而，却是在一定的限制下，在通用环境下算法并不可用.
为此，本文提出一种冲突检测算法，可以对任何排课算法排出的课表进行冲突检测.
1课表必须满足的硬条件及其形式化描述
1.1自然语言描述[8]
一份正确有效的课表，必须避免排课元素的冲突，其中，排课元素包括：时间、教室、教师、班级、课程.课表必须同时满足如下3个硬条件：
(1)教室不冲突：同一时间，不能在同一教室安排两门不同课程；
(2)教师不冲突：同一时间，不能让同一教师为两个不同班级上课；
(3)班级不冲突：同一时间，不能为同一班级安排两门不同课程.
1.2形式语言描述
定义1课表是一个5维向量A(T,R,P,C,L)，其中，t∈T是离散时间片，r∈R是教室，p∈P是教师，c∈C是班级，l∈L是课程，如果在时间片t，教师p在教室r给班级c上课程l，则A(t,r,p,c,l)=1，否则A(t,r,p,c,l)=0.
定义2“教室不冲突”条件可被定义为
∀t∀r∀p1∀c1∀l1∀p2∀c2∀l2(((A(t,r,p1,c1,l1)=1)∧(A(t,r,p2,c2,l2)=1))→(l1=l2)).
定义3“教师不冲突”条件可被定义为
∀t∀p∀r1∀c1∀l1∀r2∀c2∀l2(((A(t,r1,p,c1,l1)=1)∧(A(t,r2,p,c2,l2)=1))→(c1=c2)).
定义4“班级不冲突”条件可被定义为
∀t∀c∀p1∀r1∀l1∀p2∀r2∀l2(((A(t,r1,p1,c,l1)=1)∧(A(t,r2,p2,c,l2)=1))→(l1=l2)).
2冲突检测算法
有了第1节给出的形式化描述，即可给出对3个条件的检测方法，分别如2.1节、2.2节、2.3节所示.依次调用这些方法，即可得到课表冲突检测算法，如2.4节所示.
2.1教室冲突检测子算法
Procedure ROOM
Input: 排好的课表即5维向量A(T,R,P,C,L)
Output: 有关是否存在教室冲突的检测结果
Begin
{ifA(t,r,p,c,l)=1, thenco(l):=true}
}
}
if ∃i∃j(i≠j)∧co(i)∧co(j),then//若被安排两门课
{return((t,r,i,j)&“教室有冲突”);flag:=1} //报告冲突位置
}
}
End
2.2教师冲突检测子算法
Procedure PROFESSOR
Input: 排好的课表即5维向量A(T,R,P,C,L)
Output: 有关是否存在教师冲突的检测结果
Begin
{ifA(t,r,p,c,l)=1, thenco(c):=true}
}
}
if ∃i∃j(i≠j)∧co(i)∧co(j), then//若被安排两班级
{return ((t,p,i,j)&“教师有冲突”);flag:=1} //报告冲突位置
}
}
End
2.3班级冲突检测子算法
Procedure CLASS
Input: 排好的课表即5维向量A(T,R,P,C,L)
Output: 有关是否存在班级冲突的检测结果
Begin
{ifA(t,r,p,c,l)=1, thenco(l):=true}
}
}
if ∃i∃j(i≠j)∧co(i)∧co(j),then//若被安排两门课
{return((t,c,i,j)&”班级有冲突”);flag:=1}//报告冲突位置
}
}
End
2.4冲突检测算法
Procedure DETECTION
Input: 排好的课表即5维向量A(T,R,P,C,L)
Output: 有关课表是否存在冲突的检测结果
Begin
flag:=0;//当存在冲突时，flag被置为1
ROOM;
PROFESSOR;
CLASS;
ifflag=0 then return (“课表无冲突”), else return(“课表有冲突”)
End
3算法复杂度分析
4结论
本文的主要成果是算法DETECTION，它是一种可以全自动地检测给定的课表是否满足教室无冲突、教师无冲突、班级无冲突等约束条件的通用方法.笔者使用来自多家教学单位提供的模拟课表共计50份作为样本，一部分课表由人工编排，另一部分由半人工编排，其余的则分别由多种算法全自动编排，不同的课表及采用的排课方法符合不同教学单位的不同个性化需求.针对这些样本，实施了一系列实验性检测.新算法在两小时内发现了8处编排冲突；作为对照，5名实验人员用了一周时间仅仅发现了2处冲突.结果表明，新算法可高效地发现各类课表中的冲突现象.
参考文献
[1]许秀林，胡克瑾.基于约束满足和遗传算法的排课算法[J].计算机工程，2010，36(14)：281-284.
[2]王伟，余利华.基于贪心法和禁忌搜索的实用高校排课系统[J].计算机应用，2007，27(11)：2 873-2 876.
[3]梁立，陈玉华，徐敏.基于贪心法的排课算法[J].云南师范大学学报：自然科学版，2005，25(3)：9-12.
[4]吴志斌，陈淑珍.回溯算法与计算机智能排课[J].计算机工程，1999，25(3)：79-80.
[5]黄玉波.高校排课流程及冲突检测分析[J].软件导刊，2010，9(2)：16-17.
[6]高武奇，康凤举，钟联炯.基于冲突检测算法的二级排课系统[J].西安工业大学学报，2008，28(5)：506-510.
[7]张海涛，李俊杰，严伟榆，等.基于学分制的排课冲突检测优化算法研究[J].电子设计工程，2013，21(15)：8-10.
[8]肖刚.排课冲突检测的设计及实现[J].软件导刊，2011，10(5)：5-7.
An Instruction-oriented Algorithm for Detecting
Collisions in Class Schedule
ZHU Wei-jun1， WANG Yi-ran2
(1.SchoolofInformationEngineering,ZhengzhouUniversity,Zhengzhou450001,China;
2.SchoolofComputerScienceandTechnology,ZhoukouNormalUniversity,Zhoukou460001,China)
Abstract:The existing course arrangement algorithms can deal with time, rooms, teachers, classes and courses in large scale. Up to now, no method is given to check whether a class schedule is effective automatically, or not. To address this problem, we formulize the constraint conditions. On the basis of it, three sub-algorithms are formulated to check these conditions. By calling the sub-algorithms one by one, we obtain an algorithm for detecting collisions in a class schedule. The experimental results demonstrate the new method is effective.
Key words:course arrangement systems; algorithm; collision detection; class schedule
中图分类号：TP311.1；G473.4
文献标识码：A
文章编号：1007-0834(2015)02-0030-04
doi：10.3969/j.issn.1007-0834.2015.02.008
作者简介：朱维军(1976—)，男，河南郑州人，郑州大学信息工程学院副教授，博士、博士后，主要研究方向：教育技术、信息安全.
基金项目：河南省高等学校青年骨干教师资助计划项目(2014GGJS-001)
收稿日期：2015-02-28
