中小学辅助排课系统的设计与实现

中小学辅助排课系统的设计与实现贺荣摘要：编排课表是中小学教学管理中一项重要而又复杂的工作。它通过合理地安排时间、教师、课程、班级四大要素之间的关系，使全校各个班级一周内的每节课，都有合适的教师及课程与之对应。针对我校自身的校务情况，在研究过当前一些优秀的排课算法的基础上，我研究出一套基本可行的排课程序。它可先根据教务人员输入的约束条件进行设置，通过逐步筛选细化，将特定的课自动安排在最合适的时间段中安排到最优级的班级中。如果自动排课尚有不成功的地方，会在课表显示区将该课程以红色显示进行警告。通过这种直观的辅助手段，教务人员再配合进一步手动调整，最终调整出满意的课表。关键词：排课系统自动手动辅助一、排课系统的开发背景随着教育事业的不断发展，学校对教师课程安排的复杂度不断增加，如何将一个学校各个学科每天的课程安排与教室资源的分配合理化是摆在每一个教务工作人员面前的一个难题。传统的人工排课方式不仅工作繁琐，工作量大，而且还很容易出现错误。因此，计算机软件技术应用于学校的课程安排是发展的必然。充分发挥计算机自身的优势，将大量复杂的判断与运算交给计算机做，是真正意义上的人脑的“减负”。教师设置好学校基本情况及排课要求，让计算机自动排出课程表，适度调课后的课表就能满意地应用于新的学期。早在上世纪60年代末，Grotlieb.C.C教授就对课程表问题进行了形式化描述[1]。排课表这样的时间表问题(TTP:Time-Table-Problem),是典型的组合优化和不确定性的调度问题[2,3],并且已被证明是NP完全问题，有其自身固有的数学模型，即课表问题存在解，并且能找到解[4]。排课表问题的难度在于:它是一个多元受限的问题(受限于课程、时间、班级、教师、教室排课五要素),如果必须满足所有的约束条件(而这些条件通常是相互矛盾的),则极有可能找不到完整解[5];这也是为什么迄今为止还几乎没有完全自动生成课表系统的软件应用于实际，因为多数的排课效果好的软件还需后期手动辅助排课进行完善，而那些完全自动生成的排课软件，通常会以降低约束条件的满足程度为代价（比如不能均匀分布课程、主副科安排时间段不很合理等）。目前,解决课表问题的方法有:模拟手工排课法[6,7],图论方法,拉格朗日松弛法,二次分配型法等多种方法[8,9]。在以往的教学管理中，课表编排在许多学校只能通过人工或人工模拟的方式生成。但是，伴随着各类学科范围的不断扩大，各学科科目逐渐增多，以至于众多的教师和学生、庞大的课时、复杂的班级信息令学校的教务安排人员无法高效、合理地制定出相应的排课计划。这就促使我们的教务安排人员必须采用一些辅助的手段来帮助自己。因此，计算机辅助排课成了现代排课的需要，相应的排课算法成了人们探讨的主要问题。目前常见的排课算法有贪心算法、遗传算法、回溯算法等[10]。研究并使用一种好的算法不仅可以缩短排课时间，提高排课效率，更可以让使用者得心应手，提高教学效果。二、排课系统开发目的及意义排课问题的实质是为教师、学生的教学活动合理安排时间上和空间上的资源，以保证教学活动有秩序有计划地进行。排课工作在教务工作中处于十分重要地位。用一个计算机自动排课系统来完全代替手工排课，是每个排课程序开发者的设计初衷，但随着研究的不断深入，好多开发者都会发现一个棘手的问题：由于排课众多的约束条件和超大的求解规模，使一个完全的自动排课系统的生成可能性变得很小。因此，在约束多、数量大的前提下，通过人工干涉达到合理的排课效果是很重要的。开发“中小学辅助排课系统”旨在当前中小学教学模式下，提高排课效率，优化排课结果，探求算法的改进，既能首先使用自动排课替代以往的手工排课，又能在后期使用辅助手动排课进一步调整细化，使排课结果更为理想。本设计借鉴当前成功的排课经验并结合本校的实际情况，探究出一种优化资源分配的自动排课，及后期利用手动处理优化排课结果的算法。主要有四个方面：首先是将教师信息按权值高低进行优先级排序。排课时总的原则是主科教师及课时量多的教师优先进行排课，但为了保证教师的排课均匀，设置变量turned代表轮流次数，每位教师排课后turned增加1，然后取下一位教师的排课信息，成功排课后该教师的turned变量也增加1，这样当所有教师排了一遍课程以后，再按教师优先级的排序结果重新来下一轮次，可以保障教师排课的均匀。第二：得到该教师所带课程及班级信息后，将教师课表、班级课表、约束条件设置表、星期区间表进行“与”操作，判断出该节课是否适合安排课程。这里主要体现在经过上述四大条件的“与”操作之后，适合安排该课的课节是一周里面最优的时间段。第三：为保证排课结果均匀而预先设置好“星期区间”。有的课程一周2节，有的课程一周8节，如何将这些课程在一周内均匀地安排，是中小学排课中一个很关键的问题。本文首先设定好一个“星期约束”表，将周课时从1节到8节分别进行星期区间的合理设定，当排到某课程特定的课节时，可以从区间表中找到它对应的星期区间，以达到排课结果的均匀；最后：在自动排课无法达到理想状态，即排课产生冲突的时候，为用户提供手动辅助排课，以达到进一步优化排课结果的效果。冲突检测主要通过5个集合来完成，分别为课程A，教师B，班级C，约束D，时段E。其中时段E即为基础数据模块中“周课节设置”后形成的时间区间。如一周上课5天，一天6节课。从课程A中提取一门需要安排的课，按时段取用规则从时段E中提取一个时间片，在这个时间片进行各种冲突检测，即对教师B、班级C和约束D进行检测，一旦冲突，则跳过此次排课结果，再进行其它尝试。自动排课和手动调整均适用此冲突检测规则。三、排课准则及排课算法（一）排课系统的准则一个排课系统成功与否，主要取决于排课结果是否符合以下准则：1．是否满足“约束条件”，也称为“硬条件”这是判断一个排课系统的生成结果是否成功的标志。本文之所以把约束条件称为“硬条件”，是因为它是排课系统必须遵循的条件，如果违背了这些条件形成结果，那么结果将视为无效。打个比方：全校的语文组要在每个周二的上午集体教研，那么之前设置的约束条件——周二的上午不能安排语文课，则是硬性的必先执行的约束条件，排课时必须做到遵守这一点，否则就会影响教学安排，违背了排课系统的设计初衷。中小学的排课系统不同于高校，它没有教室因素这一要求，即每个班级固定为某个教室，其常见的约束条件如下所列：（1）教师不能冲突：一名教师不能同时带多个班的课程，合班课除外；教师先前做好的约定不能被违背，比如张老师要求周一上午第4节不予安排课。（2）班级不能冲突：同一时间段一个班级不能同时由多位教师上课，如初一1班周一第2节，同时由语文张老师和数学李老师上课是不合理的；班级的约束条件不能被违背，如全校周一下午第2节固定设置为班会。2．是否满足“优化条件”，也可称为“软条件”优化条件，又称软条件，是在排课过程中可以满足同时又可以不完全满足的约束条件，是在满足硬约束条件的基础上能尽量要求满足的约束条件，软约束条件可以根据不同的教学情况有所差异。有时可以通过调节软约束条件的满足程度而改变排课的效果，可以将一定要满足的软约束条件转换为“硬约束条件”。常见的优化条件如下所列：（1）同一班级的某门课程，一周内上课的时间尽量均匀分散安排。（2）主科安排在主要时间段，一般为上午，副科安排在次要时间段。（3）教师课程安排合理：任课多的教师一周的工作量要合理分布。（4）占用公共资源的的课程如微机、体育，以及学时多的课程优先进行处理。优化条件是判断一个排课系统的生成结果是否成功的标志。也就是说，一个排课程序，如果能实现所有的“约束条件”，也就是硬条件，那么说它是合格的，但未必代表它就是成功的。只有同时满足了“优化条件”，也就是软约束条件，才能说它是一款成功的排课系统。（二）优化排课算法的实现设计排课系统算法有一定的复杂性，因为它涉及到教师、班级、时间、课程四大信息对象，如果是高校的话，还会涉及到“教室”第五个因素。算法的目标是为满足学校教学需求而合理分配资源，其关键核心问题即在于：解决冲突。试想，一个学校几十个班级、十几门课程、百十名教师、几十个时间段……将这么多的因素交叉在一起形成一系列完全没有冲突的课表，绝不可能是随便一个简单的算法能够实现得了的。虽然目前已经出现了许多用不同算法设计的自动排课系统，但它们或多或少存在着不足；或因适用范围太广而导致操作复杂，需要手工录入的排课信息量太大；或因排课算法不合理导致排课时间过长，有的甚至导致死机；还有的排课速度很快，结果却差如人意，只是满足了一定的硬性约束条件，而优化条件却满足的很少，导致排课效果一般。而且大多数是针对大专院校需求开发设计的，很难适用于义务阶段的中小学校的特殊的教学安排。因此，本文在分析了当前中小学课程，并了解了一些学校现有排课方法后，整理出了一套针对本校排课使用的的算法，它能比较有效处理各种复杂的冲突，而且能自动呈现排课结果，之后还可以根据用户自己的需求进一步手工调整，该算法基本能满足中小学校的排课要求。1．构造时间模式库时间模式是根据教务人员的经验，为各种周学时数不同的课程指定的一种时间组合方式。例如，一门课程的周学时数为4，那么它的时间组合方式可以有:“11”，“22”“32”，“41”;表示该课程一周上4次，分别为周一的第1节、周二的第2节、周三的第2节和周四的第1节，同时，为了达到较好的上课效果，也要对这些时间模式进行分级。如下所示：时间模式举例周一周二周三周四周五第1节1121314151第2节1222324252……第6节1626364656第7节1727374757其中，前一位数字表示星期，将周一至周五用数字1～5表示，后一位数字表示上课节次，第1-8节分别用数字1～8表示。例如数字“42”表示周四的第2节，数字“56”表示周五的第六节。这样，对于每种周学时数，可以将所有合理的时间组合形式存入模式库中，以便进行时间处理时可以用时间模式库中的各种模式进行匹配。2．建立时间数组（1）建立班级教师空闲时间表为了表示班级、教师的可排课时间，分别为他们建立一维数组，因为中小学班级固定，所以不考虑教室的可排课时间，例如：某位教师的初始可排课时间数组为(11111111111111111111111111111111111)。其中共有五组数据，分别表示一周中的五天；而一组数据共有7个字符，分别表示一天中的七个时间单元，初始置为1时，表示该教师一周中的每一时间段均为空闲无课时间。当为某位教师分配时间后，相应的那位字符就置为0，例如，某位教师的可排课时间数组为(01011111011101001111111011110110111)，则表示这位教师在周一的第1、3节，周二的2、6节，周三的1、2节，周四的第3节，周五的第1、4节已经安排了课程，如果要再安排课程的话，就应该在值为1的时间单元中筛选。对于班级也可以进行同样的处理，分别标出班级可排课时间。例如，某班级的可排课时间数组为(00011111011101001111111011110111101)，则表示这个班级在周一的第1、2、3节，周二的2、6节，周三的1、2节，周四的第3节，周五的第1、6节已经安排了课程，如果要再安排课程的话，就应该在非0的时间单元中筛选。将教师可排时间与班级可排时间作“&”与操作之后，即可以得出教师班级空闲时间表。例如将上述两数组进行与操作之后，可以得到如下数组：(00011111011101001111111011110110101)，即再安排课时，该班级的周一第123节课、周二的第2、6节课、周三的1、2节课、周四的第3节课、周五的1、4、6节课均已有安排，需要在其它的时间段进行选择和安排。（2）建立星期区间表为了实现排课的均匀，本文将星期按区间进行分配，举个例子，如果当前处理的课是一周2节的音乐课，并且当前排的是本周的第2次音乐课，则要从数据库中找到对应的course_count=2、turned=1时对应的星期约束条件数组（11111111111111111100000000000000000）来进行排课，这其实是教务工作人员前