论文部分内容阅读
【摘要】随着高校规模的扩大，排课问题变得越来越复杂。很多高校仍然采用手工排课为主、计算机排课为辅的排课方式。本文采用遗传算法对高校排课问题进行分析，解决采用手工排课为主的排课方式出现的教师或教室等资源冲突的现象。
【关键词】遗传算法排课问题分析
遗传算法是近些年发展起来的一种崭新的全局优化算法，它借助了生物遗传学的观点，基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法。通过自然选择、交叉、变异等作用机制，实现各个个体的适应性的提高。高校课表编排工作的主要思想是：读取开课计划一落实教学任务一统计可用资源一课表的编排。具体来说就是教务处在每学期开始前读取各个专业的开课计划；并将读取的开课计划落实教师、教室类型等；统计全校在对应学期的可利用的教学资源(教师、教室等)；对确定开设的课程，根据不同的专业，以班级为单位编制下学期的班级、教师、教室以及课程的课表。
一、排课问题要素分析
(一)课程
每门课程都有自己的编号、名称以及承担单位。课程本身包含的属性会在很大程度上影响该门课程的排课结果。
学时数：根据教学计划，每门课程都有指定的学时数，可以用整个学期或者规定的时间段完成课程的总学时数，要为课程安排相应的时间片。
可拆性：上课时间的最小单位是学时，一般来说，每一个时间片对应两个学时(称为一个讲次)，但是多数课程的周学时数多于两个学时，这样就必须将课程拆成两个或者多个讲次。
时间要求：有些课程对时间有特殊的要求，例如体育课尽量不安排在1、2节课。有些课程不能安排到晚上等等。
地点要求：一般来说，上课地点分为很多类型，如多媒体教室、一般教室、语音室、机房、专用实训室等。
起止周数：根据课程的需要，很多高校把某些课程集中在某几周或者由于特殊原因不规则的安排到一个学期中。因此必须要为课程定义起止周数。只要满足周数不冲突的课程即可安排在一个时间段内。
(二)教师
教师是安排课程的必要资源之一。在排课的过程中。教师应该服从相应的时间安排。当然也可以根据实际情况对授课时间提出的要求。
所授课程：每个教师都可以讲授多门课程，但同一名教师在同一时间段内只能讲授一门课程。
时间要求：教师由于个人因素或者职务因素等对授课时间提出要求，例如，有些教师希望在一周的某个时间不能上课，有些教师希望在具体某天上课。还有教师希望课程安排尽量紧凑等等。
(三)班级
班级就是指行政班级。合班上课的情况我们称之为教学班，教学班不能认为是一个新的班级。
开设课程：在一个学期内每个班级都会开设多门课程，但同一个班级在同一时间段内只能上一门课程。
班級人数：在正常情况下，某个班级开设某门课程即是班级的全体学生都学习这门课程。在安排教室的时候必须考虑到教室容量数一定要大于或者等于班级人数。
时间要求：有时根据教学计划，某些班级对课程的编排时间也有着特殊要求，如可能在中间几周出去实习，这段时间就不能排课，还有些如体育课等后面最好不排课等等。
(四)教室
教室类型：包括普通教室、多媒体教室、机房、语音室和实训室等，一般来说，一个教室在同一时间内只能被一门课程所使用。对于一些特殊课程，例如体育课因为不需要固定的教室，可以同时安排多门课程。
教室容量：指一间教室所能容纳的最多人数，上课人数不能超过教室容量。
教室位置：包括校区、教学楼、楼层等，影响班级学生和教师在不同课程之间的移动距离。
(五)时间
上课时间在对应学年、学期一般是按周来计算的，按照学校规定从第1周至第N周。当然根据实际情况，也可以是学期中的任意连续或不连续周。
二、排课问题的约束分析
排课就是将教学任务在时间和地点上按照不同的约束条件进行的排列组合。从手工排课可以看出，排课需要考虑学校方方面面的约束条件。在排课过程中，主要任务就是将班级、教室、课程、教师等几部分资源进行最优化组合配置。
排课问题的约束条件很多，但大体上可以分为三种：
(一)基本硬约束(基本的约束条件)：
1、一个班级不能在同一时间内上两门不同的课程。
2、一个教师不能在同一时间内上两门不同的课程。
3、一个教室不能在同一时间内上两门不同的课程。
(二)硬约束(排课所必须遵循的原则)：
1、学校本身的规定产生相关的约束。
2、课程的学时在周和星期上分配有一定的规律。
3、上课按最小单位一节计算，课表周数、天数、节数可以自行定制。
4、教室容量必须大于上课班级人数。
5、某些课程、教师、班级、教室的属性可以提前设置。
6、每门课程都有相对应的教室类型。
(三)软约束(不影响结果的约束条件)：
1、每个上课时间段都具有一定的优度。
2、教师尽量不安排连续上课。
3、班级在一周内的课表尽量分布均匀。
4、教师对上课时间或地点具有一定的满意度。
5、职业院校实训课程比较多，根据需要进行上课时间和地点的约束。
对于上述三种约束条件的满足程度可以是逐渐降低的。资源的约束必须满足才可以进行课表的编排，编排的过程中必须杜绝任何硬冲突的约束，尽量提高软冲突约束的满意度，以获得最优解。
【关键词】遗传算法排课问题分析
遗传算法是近些年发展起来的一种崭新的全局优化算法，它借助了生物遗传学的观点，基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法。通过自然选择、交叉、变异等作用机制，实现各个个体的适应性的提高。高校课表编排工作的主要思想是：读取开课计划一落实教学任务一统计可用资源一课表的编排。具体来说就是教务处在每学期开始前读取各个专业的开课计划；并将读取的开课计划落实教师、教室类型等；统计全校在对应学期的可利用的教学资源(教师、教室等)；对确定开设的课程，根据不同的专业，以班级为单位编制下学期的班级、教师、教室以及课程的课表。
一、排课问题要素分析
(一)课程
每门课程都有自己的编号、名称以及承担单位。课程本身包含的属性会在很大程度上影响该门课程的排课结果。
学时数：根据教学计划，每门课程都有指定的学时数，可以用整个学期或者规定的时间段完成课程的总学时数，要为课程安排相应的时间片。
可拆性：上课时间的最小单位是学时，一般来说，每一个时间片对应两个学时(称为一个讲次)，但是多数课程的周学时数多于两个学时，这样就必须将课程拆成两个或者多个讲次。
时间要求：有些课程对时间有特殊的要求，例如体育课尽量不安排在1、2节课。有些课程不能安排到晚上等等。
地点要求：一般来说，上课地点分为很多类型，如多媒体教室、一般教室、语音室、机房、专用实训室等。
起止周数：根据课程的需要，很多高校把某些课程集中在某几周或者由于特殊原因不规则的安排到一个学期中。因此必须要为课程定义起止周数。只要满足周数不冲突的课程即可安排在一个时间段内。
(二)教师
教师是安排课程的必要资源之一。在排课的过程中。教师应该服从相应的时间安排。当然也可以根据实际情况对授课时间提出的要求。
所授课程：每个教师都可以讲授多门课程，但同一名教师在同一时间段内只能讲授一门课程。
时间要求：教师由于个人因素或者职务因素等对授课时间提出要求，例如，有些教师希望在一周的某个时间不能上课，有些教师希望在具体某天上课。还有教师希望课程安排尽量紧凑等等。
(三)班级
班级就是指行政班级。合班上课的情况我们称之为教学班，教学班不能认为是一个新的班级。
开设课程：在一个学期内每个班级都会开设多门课程，但同一个班级在同一时间段内只能上一门课程。
班級人数：在正常情况下，某个班级开设某门课程即是班级的全体学生都学习这门课程。在安排教室的时候必须考虑到教室容量数一定要大于或者等于班级人数。
时间要求：有时根据教学计划，某些班级对课程的编排时间也有着特殊要求，如可能在中间几周出去实习，这段时间就不能排课，还有些如体育课等后面最好不排课等等。
(四)教室
教室类型：包括普通教室、多媒体教室、机房、语音室和实训室等，一般来说，一个教室在同一时间内只能被一门课程所使用。对于一些特殊课程，例如体育课因为不需要固定的教室，可以同时安排多门课程。
教室容量：指一间教室所能容纳的最多人数，上课人数不能超过教室容量。
教室位置：包括校区、教学楼、楼层等，影响班级学生和教师在不同课程之间的移动距离。
(五)时间
上课时间在对应学年、学期一般是按周来计算的，按照学校规定从第1周至第N周。当然根据实际情况，也可以是学期中的任意连续或不连续周。
二、排课问题的约束分析
排课就是将教学任务在时间和地点上按照不同的约束条件进行的排列组合。从手工排课可以看出，排课需要考虑学校方方面面的约束条件。在排课过程中，主要任务就是将班级、教室、课程、教师等几部分资源进行最优化组合配置。
排课问题的约束条件很多，但大体上可以分为三种：
(一)基本硬约束(基本的约束条件)：
1、一个班级不能在同一时间内上两门不同的课程。
2、一个教师不能在同一时间内上两门不同的课程。
3、一个教室不能在同一时间内上两门不同的课程。
(二)硬约束(排课所必须遵循的原则)：
1、学校本身的规定产生相关的约束。
2、课程的学时在周和星期上分配有一定的规律。
3、上课按最小单位一节计算，课表周数、天数、节数可以自行定制。
4、教室容量必须大于上课班级人数。
5、某些课程、教师、班级、教室的属性可以提前设置。
6、每门课程都有相对应的教室类型。
(三)软约束(不影响结果的约束条件)：
1、每个上课时间段都具有一定的优度。
2、教师尽量不安排连续上课。
3、班级在一周内的课表尽量分布均匀。
4、教师对上课时间或地点具有一定的满意度。
5、职业院校实训课程比较多，根据需要进行上课时间和地点的约束。
对于上述三种约束条件的满足程度可以是逐渐降低的。资源的约束必须满足才可以进行课表的编排，编排的过程中必须杜绝任何硬冲突的约束，尽量提高软冲突约束的满意度，以获得最优解。