中小学辅助排课系统的设计与实现剖析.doc

中小学辅助排课系统的设计与实现 贺 荣 摘要：编排课表是中小学教学管理中一项重要而又复杂的工作。它通过合理地安排时间、教师、课程、班级四大要素之间的关系，使全校各个班级一周内的每节课，都有合适的教师及课程与之对应。 针对我校自身的校务情况，在研究过当前一些优秀的排课算法的基础上，我研究出一套基本可行的排课程序。它可先根据教务人员输入的约束条件进行设置，通过逐步筛选细化，将特定的课自动安排在最合适的时间段中安排到最优级的班级中。如果自动排课尚有不成功的地方，会在课表显示区将该课程以红色显示进行警告。通过这种直观的辅助手段，教务人员再配合进一步手动调整，最终调整出满意的课表。 关键词：排课系统 自动 手动 辅助 一、排课系统的开发背景 随着教育事业的不断发展，学校对教师课程安排的复杂度不断增加，如何将一个学校各个学科每天的课程安排与教室资源的分配合理化是摆在每一个教务工作人员面前的一个难题。传统的人工排课方式不仅工作繁琐，工作量大，而且还很容易出现错误。因此，计算机软件技术应用于学校的课程安排是发展的必然。充分发挥计算机自身的优势，将大量复杂的判断与运算交给计算机做，是真正意义上的人脑的“减负”。教师设置好学校基本情况及排课要求，让计算机自动排出课程表，适度调课后的课表就能满意地应用于新的学期。 早在上世纪60年代末，Grotlieb.C.C教授就对课程表问题进行了形式化描述[1]。排课表这样的时间表问题(TTP: T ime-Table-P rob lem ) , 是典型的组合优化和不确定性的调度问题[ 2, 3 ] , 并且已被证明是NP完全问题，有其自身固有的数学模型，即课表问题存在解，并且能找到解[4]。排课表问题的难度在于:它是一个多元受限的问题(受限于课程、时间、班级、教师、教室排课五要素) , 如果必须满足所有的约束条件(而这些条件通常是相互矛盾的) , 则极有可能找不到完整解[ 5 ]; 这也是为什么迄今为止还几乎没有完全自动生成课表系统的软件应用于实际，因为多数的排课效果好的软件还需后期手动辅助排课进行完善，而那些完全自动生成的排课软件，通常会以降低约束条件的满足程度为代价（比如不能均匀分布课程、主副科安排时间段不很合理等）。 目前, 解决课表问题的方法有: 模拟手工排课法[ 6,7 ] , 图论方法, 拉格朗日松弛法, 二次分配型法等多种方法[ 8, 9 ]。在以往的教学管理中，课表编排在许多学校只能通过人工或人工模拟的方式生成。但是，伴随着各类学科范围的不断扩大，各学科科目逐渐增多，以至于众多的教师和学生、庞大的课时、复杂的班级信息令学校的教务安排人员无法高效、合理地制定出相应的排课计划。这就促使我们的教务安排人员必须采用一些辅助的手段来帮助自己。因此，计算机辅助排课成了现代排课的需要，相应的排课算法成了人们探讨的主要问题。目前常见的排课算法有贪心算法、遗传算法、回溯算法等[10]。研究并使用一种好的算法不仅可以缩短排课时间，提高排课效率，更可以让使用者得心应手，提高教学效果。 二、排课系统开发目的及意义 排课问题实质是为师、学生的教学活动合理安排时间上和空间上的资源，以保证教学活动有秩序有计划地进行。排课工作在教务工作中处于十分重要地位。由于超大的求解规模借鉴成功经验并结合校的实际情况是在排课过程中可以满足又可以不完全满足的约束条件，是在满足硬约束条件的基础上能尽量要求满足的约束条件，软约束条件不同的教学情况有所差异可以通过调节软约束条件的满足程度而改变排课的效果，可以将一定要满足的软约束条件转换为“硬约束条件”。 表T_COURSE_WHERE，前台课程控件对应字体显示为红色（clRed），代表这些课节适合安排主科。下午第2节及以后时间段不适合安排主科，后台将对应的权值“2”写入数据库约束表T_COURSE_WHERE，前台课程控件对应字体选用蓝色（clBlue）进行设置。 课程约束条件设置示意图如图1所示。 说明：实际操作中，课表中的课程用红色代表适合，粉色代表正常，蓝色代表不适合。 周一 周二 周三 周四 周五 上午1 2 3 4 下午1 2 3 周一 周二 周三 周四 周五 上午1 2 3 4 下午1 2 3 图1 课程约束条件设置示意图 还以音乐课为例，音乐课属于副科，其最好的安排时间段为每天上午最后一节和下午，所以其对应的约束条件区间为（0001111 0001111 0001111 0001111 0001111）。 在拿到一门课程时，首先从库里