中小学辅助排课系统设计与实现.docx
《中小学辅助排课系统设计与实现.docx》由会员分享，可在线阅读，更多相关《中小学辅助排课系统设计与实现.docx（18页珍藏版）》请在冰点文库上搜索。
中小学辅助排课系统设计与实现
中小学辅助排课系统的设计与实现
贺荣
摘要：
编排课表是中小学教学管理中一项重要而又复杂的工作。
它通过合理地安排时间、教师、课程、班级四大要素之间的关系，使全校各个班级一周内的每节课，都有合适的教师及课程与之对应。
针对我校自身的校务情况，在研究过当前一些优秀的排课算法的基础上，我研究出一套基本可行的排课程序。
它可先根据教务人员输入的约束条件进行设置，通过逐步筛选细化，将特定的课自动安排在最合适的时间段中安排到最优级的班级中。
如果自动排课尚有不成功的地方，会在课表显示区将该课程以红色显示进行警告。
通过这种直观的辅助手段，教务人员再配合进一步手动调整，最终调整出满意的课表。
关键词：
排课系统自动手动辅助
一、排课系统的开发背景
随着教育事业的不断发展，学校对教师课程安排的复杂度不断增加，如何将一个学校各个学科每天的课程安排与教室资源的分配合理化是摆在每一个教务工作人员面前的一个难题。
传统的人工排课方式不仅工作繁琐，工作量大，而且还很容易出现错误。
因此，计算机软件技术应用于学校的课程安排是发展的必然。
充分发挥计算机自身的优势，将大量复杂的判断与运算交给计算机做，是真正意义上的人脑的“减负”。
教师设置好学校基本情况及排课要求，让计算机自动排出课程表，适度调课后的课表就能满意地应用于新的学期。
早在上世纪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）建立班级教师空闲时间表
为了表示班级、教师的可排课时间，分别为他们建立一维数组，因为中小学班级固定，所以不考虑教室的可排课时间，例如：
某位教师的初始可排课时间数组为（1111111 1111111 1111111 11111111111111）。
其中共有五组数据，分别表示一周中的五天；而一组数据共有7个字符，分别表示一天中的七个时间单元，初始置为1时，表示该教师一周中的每一时间段均为空闲无课时间。
当为某位教师分配时间后，相应的那位字符就置为0，例如，某位教师的可排课时间数组为（0101111 1011101 0011111 1101111 0110111），则表示这位教师在周一的第1、3节，周二的2、6节，周三的1、2节，周四的第3节，周五的第1、4节已经安排了课程，如果要再安排课程的话，就应该在值为1的时间单元中筛选。
对于班级也可以进行同样的处理，分别标出班级可排课时间。
例如，某班级的可排课时间数组为（0001111 1011101 0011111 1101111 0111101），则表示这个班级在周一的第1、2、3节，周二的2、6节，周三的1、2节，周四的第3节，周五的第1、6节已经安排了课程，如果要再安排课程的话，就应该在非0的时间单元中筛选。
将教师可排时间与班级可排时间作“&”与操作之后，即可以得出教师班级空闲时间表。
例如将上述两数组进行与操作之后，可以得到如下数组：
（0001111 1011101 0011111 1101111 0110101），即再安排课时，该班级的周一第123节课、周二的第2、6节课、周三的1、2节课、周四的第3节课、周五的1、4、6节课均已有安排，需要在其它的时间段进行选择和安排。
（2）建立星期区间表
为了实现排课的均匀，本文将星期按区间进行分配，举个例子，如果当前处理的课是一周2节的音乐课，并且当前排的是本周的第2次音乐课，则要从数据库中找到对应的course_count=2、turned=1时对应的星期约束条件数组（11111111111111111100000000000000000）来进行排课，这其实是教务工作人员前台进行约束设置后，在后台的一种对应体现，即本次排课只能从一周的上半周中进行选择，这样就可以进一步优化排课范围。
同样，如果现在要排音乐课的第2次课程时，将从数据库中找到对应字段的值course_count=2、turned=2来进行排课。
此时，对应的数组（00000000000000000111111111111111111），直接从下半周中进行筛选，不必浪费时间安排到不合理的时间段，过后再进行检查和修正。
（3）建立约束条件区间表
中小学排课有一个最大的特点就在于主副科课程的安排，语文、数学、英语作为主科一般安排在上午较好的时间段，音、体、美等副科安排在上午后面的时间段或下午。
是否能合理地安排好主副科，是一个中小学排课软件是否成功的重要体现，此处通过建立区间表的方法来体现该约束条件。
在自动排课之前，教务人员就会将每门课程的约束条件输入到程序中，在前台，用不同的颜色来为用户表示约束条件的设置，而在后台，对应了不同的数值来代表该条件。
比如主科可以设置每天上午前3节为适合，后台将对应的权值“0”写入数据库约束
表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课程约束条件设置示意图
还以音乐课为例，音乐课属于副科，其最好的安排时间段为每天上午最后一节和下午，所以其对应的约束条件区间为（00011110001111000111100011110001111）。
在拿到一门课程时，首先从库里找到这4张区间表，其中班级和教师空闲表合成后成为一张班级教师空闲表，然后将班级教师空闲时间表、星期区间表、约束条件区间表相与之后，即可得到排课可用时间表。
排课可用时间表的生成示意图如图2所示。
图2排课可用时间表的生成示意图
排课可用时间表与课程表的直观对应关系如图3所示。
说明：
表格中的部分代表该时段已安排课程。
周一
周二
周三
周四
周五
上午1
2
3
4
下午1
2
3
图3排课可用时间表直观图
3．建立tmies-week区间。
（这里将课程数course_count简称为times。
）
排课结果是否均匀是体现一个排课系统是否成功的重要指标，本文将不同的周课时数在五天内的分布进行了合理的安排，排课时，根据某门课程对应的times和turned两个参数寻找到对应的数据进行排课均匀的优化操作。
实际操作中，可以根据排课人员自己的实际要求来详细设定。
参见图4times-week区间图。
周一
周二
周三
周四
周五
8
1、2、3
4、5、6
7、8
7
1
2、3、4
5、6、7
6
1、2、3
4、5
6
5
1
2
3
4
5
4
1
2
3
4
3
1
2
3
2
1
2
1
1
图4times-week区间图
举两个例子予以说明：
周课时为5节的课程，为保证排课的均匀，安排课程时定为一天一节。
如times=5,turned=2时，表示周课时数为5，轮流次数为2，其排课区间为周二的全天，即（00000001111111000000000000000000000）。
周课时为8节的课程，将第1、2、3节放到周一、周二中进行安排；第4、5、6节放到周三、四中安排；第7、8节放到周五中安排。
如times=8，turned=4时，表示周课时数为8，轮流次数为4，就只能在周三、四中进行安插，其对应的区间为（00000000000000111111111111110000000）。
在整个自动排课过程中，算法的主要思想是：
首先将教师按所教课程的级别及课时数设定优先级，以保证主科教师及课时量大的教师能够得到优先排课的权利；之后，在时间分配时，总是在尚未分配的时间单元中选择上课效果最好的单元。
具体处理过程如下：
（1）设定优先级
以教师为主线，按照优先级进行排序。
*按主副科级别rank：
语数英：
3政物化：
2其它：
1
*按周课时数：
times
级别计算：
piror=rank*3+times
（2）查询可用时间单元的步骤
第1步：
初始化所有教师和所有班级的最大可安排时间数组为（11111111111111111111111111111111111）。
第2步：
从数据库中找出该教师所带课程对应的星期区间表，即time-week区间。
第3步：
查找该课程所对应的约束条件表。
第4步：
将前3步得到的4个区间表进行“与”操作，得到该教师所带课程可以安排的时间单元。
第5步：
依次处理教师时间数组和相关班级时间数组，将已成功安排的课对应的位置置为0，保存到各个对应的数据表中。
4．进行冲突检测
排课过程中的冲突是要根据实际情况进行消除的，一张不符合教务需求的课表是无效的课表。
冲突检测分以下几种情况：
（1）某特定的时间段的某门课程，对应教师是否已经排课；
（2）某特定的时间段，班级中是否已经排课；
（3）课程安排是否与约束条件相符合；
（4）某课程的周课时数是否已经全部安排完毕；
自动排课中，要全部使用上述4点冲突检测方法，最终结果是否冲突要以前台课程显示的不同颜色来表示，例如：
中小学语文课是主科，要求排课时最好排在上午的比较好的时间段中，可以通过“课程约束”模块，对本课对应课节分别设置“适合”、“正常”、“不适合”来做约束（将对应的值0、1、2分别保存到T_COURSE_WHERE表的F_COURSE_TYPE字段中，而0、1、2又对应不同的颜色值。
如果主科被安排在下午第2节，则视为与约束条件不符合，约束结果为“不适合”，对应值为2，调取相应的颜色模块返回前台进行显示，用户根据颜色就可以判断自动排课结果是否正常。
手动排课中，只使用到第1种和第4种冲突检测方法。
当用户手动进行课程安排的时候，首先判断该课程一周的课时数是否已经排满，如果排满则弹出对话框进行警告，并禁止本次手动安排。
其次还应判断该课程对应的授课教师，是否该时段在别的班级有课，如果有则弹出对话框进行警告，并禁止本次手动排课。
5．手动辅助处理
计算机自动排课也需要进行手动排课的辅助，以便可以使得能够根据自己的具体要求对排课算法中的一些参数进行设置和修正，并对计算机排出的课表进行调整，本算法所设计的人工干预过程有：
时间模式库的设置，约束条件的设置，自动排课后的结果调整，通过这些方法为用户呈现满意的课程表。
手动辅助处理的具体内容如下：
（1）一周上几天，一天几节课，用户可以根据自己的需求来设置时间模式库；
（2）语文适合安排在哪个时间段，体育适合安排在哪个时间段，用户可以自行设定相应的约束条件；
（3）自动排课后，针对冲突的或排课结果不理想的课程，系统提供手动排课。
排课时系统会将课程以不同颜色进行显示，方便用户对安排不合理的课程及时更改，同时系统会给用户列出该课程对应的周课时数及已排次数，提高用户手动排课的效率。
四、程序的实现
（一）基础数据设置
该模块的运行窗口，如图5所示。
图5基础数据设置窗体
（二）班级课程设置
这是设置某一班级具体开设哪些课程、每门课程的周课节数是多少的模块。
班级课程设置窗口如图6所示。
图6班级课程设置窗体
（三）教师课程设置
该模块可以设置每位教师任哪个班级的哪一门课。
将教师、班级、课程多种排课条件进行关联。
教师课程设置窗口如图7所示。
图7教师课程设置窗体
（四）课程约束设置
该模块主要实现对课程约束条件的设定。
中小学排课系统中，通常要把主科排在上午的时段，一些副科排在下午的时段，或者因为教研活动等原因，需要对课程进行合理的分配与安排。
该模块的设定可以对排课的优先顺序产生影响，也可以使最终的排课结果以对应颜色显示，使用户能够了解排课结果，并适当进行下一步修改。
如图8所示。
图8课程约束设置窗体
（五）自动排课算法模块
该模块的运行窗体，如图9所示。
图9自动排课运行窗体
（六）手动排课运行模块
该模块的运行窗体，如图10所示。
图10手动排课运行窗体
五、结束语
该设计是本人在分析目前大量成功的排课系统基础之上，结合自己在学校帮助教务主任排课的经验，通过研究与比较各算法领域中成功而科学的理论思想而探索出的一套排课算法。
该系统能够首先进行自动排课，而且之后可以利用颜色与权值相结合的简单易实现的方法，引导用户方便快捷地手工进行调整，直到排出满意的课表。
但本系统也有许多不完善之处，比如在设置约束条件的时候，不能够使用拖曳实现，只能用右键单击的方法做，不够人性化，使用起来不太方便。
另外本设计只能对课程进行约束条件的设置，缺乏对教师进行约束条件的相关设置，今后还需进一步的改进与提高。
参考文献：
[1]C.C.Gotlieb.Theconstructionofclass-teachertimetables.Informationprocess-ing.Proc.IFIPCongress62,1962
[2]TripathyA.Computeriseddecisionaidfortimetabling—acaseanalysis[J].DiscreteAppliedMathematics,1992,35（3）:
313-323.
[3]FerlandJA,FleurentC.SAPHIR Adecisionsup2portsystemforcoursescheduling[J].Interfaces,1994,24
（2）:
105-115.
[4]周建新.课表编排专家系统.计算机应用，2000,Vol.20,No.5,PP.76-7
[5]EvenS,ItaiA,ShamirA.SIAMJ[J].Comput,1976,5（4）:
升级会员 