一、问题的重述排课问题是高校制定教学计划、安排教学过程中的一项较为复杂的工作，在高校教务管理工作中处于重要地位。

高校在每学期末都要根据培养计划和教学资源作出下学期的教学安排, 这主要体现在对课表的编排上。

其中涉及的关键要素很多, 包括教师、班级、教室和授课时段等。

根据排课总体目标、约束条件、及优先级, 充分利用紧缺资源, 设计并实现高校课表安排系统。

我校所面临的问题主要有：第一，渭水校区有包括从大一至大三三个年级的学生，20个学院近700个班级，教学任务繁重，课表安排难度较大；第二，校区地处偏僻,距市区较远，老师上课需乘车来回奔波，如果课表安排不当，就会导致部分老师前往渭水乘车次数过多或在渭水逗留时间过长；第三，基于学生的学习规律与习惯，应根据课程的难度与重要性进行课程时段的安排，若安排不当，会导致学生的学习效果不佳；第四，为节省学校在校车往返方面的开支，安排课表时应尽量减少校车运行车次。

为此应根据教学计划和排课要求,综合考虑教师、课程、班级和授课时段等因素，协调合理的编排课表,制作一个系统模型，根据这个模型使老师、同学和学校尽可能满意，并且具有足够的可行性和可变动性。

让老师满意，即让每位老师一周前往渭水的乘车次数尽可能少，同时还要使每位老师在渭水逗留的时间尽可能少；让学生满意，即同一班级同一门课程在时间段上尽量间隔开来，另外相对重要的课程应尽量安排在较好的教学时段上；让学校满意，即节约学校开支，使每周派往渭水的车次尽可能少。

二、问题的分析课表安排的主要任务是把各学院的课程汇总, 然后根据教学计划或教学环节制订全校各班级的课表。

根据学校的实际情况和学校所面临的问题，可以将这类题归为以老师、学生和学校的满意情况为多目标的多约束的规划问题。

为了使课表的编排准确、合理、快速、高效, 充分利用学校资源，根据已知条件提出以下可行性要求：1、课程的优先级：将大学所有课程分为三类，1）公共必修课：多个学院开设的课程，课程重要且开设的班级数最多，这类课尽量安排在最好时段；2）专业必修课：少数学院或一个学院开设的课程，课程重要且开设的班级数较多，这类课尽量安排在较好时段；3）其他如专业选修课或公共选修课等：少数班级开设的课程，课程相对简单，可以任意安排时段授课。

2、课程时段的规定：将每天分为5个时段(上午两个,下午两个,晚上一个)，并规定为：1-2节课为第一时段，3-4节课为第二时段……依此类推。

根据学生的学习效果及课程难度与重要性，将课程时段按有利程度分为五个等级，即第一时段>第二时段>第三时段>第四时段>第五时段。

3、时间段的分配优先级：周一至周五的白天共20个时段用来安排公共必修课和专业必修课及部分选修课,每天晚上及周六、周日安排其他课程；先安排公共必修课表,在剩余的时间段安排各系专业课程，最后再安排选修课程；将相对重要的课程安排在较好时段。

4、时间段的有效性：1）同一班级同一门课的两次授课时间必须隔天，但相隔天数不宜超过两天；2）一个老师一天的两节课应连排, 即尽量安排在同一天上午或同一天下午, 为教师上课提供方便，同时也减少了派往渭水的车次5、应避免各种冲突:1）教室不冲突, 同一教室同一时间不能安排两门课程，人数不能超过教室的最大容量；2）学生不冲突, 同一班级学生不能在同一时间上两门或两门以上课程；3）课程不冲突, 同一班级同一课程不能同一时间在不同地点上课；4）教师不冲突, 同一教师不能同一时间在不同地点上课。

根据上述可行性要求，解决以下问题：问题一：要求建立排课表的数学模型，先确定公共基础课的课程数，并将这些课程数联系到教师和学生的满意程度，在优化满意程度的条件下，排出各个公共基础课的授课区域，指定老师在班级授课时间段的区域，并让老师在这个区域对不同的班级的授课时间段进行排布。

然后将专业课安插到未被占用的时间段上，最后是选修课。

同时课程的安排原则是尽可能选择在较好时段。

问题二：要求对渭水校区的课表进行重排，利用统计学知识，对学校所有班级进行抽样，随机抽取三个班级，并对这三个班级的课表重排，得到的课程与现有的课程进行比较。

问题三：利用加权综合评判法，对老师满意度、学生满意度和学校满意度进行加权综合评价。

其中老师满意度从老师的滞留时间和老师的乘车次数方面考虑，学生满意度以重要课程的安排的时间段好坏考虑，学校的满意度以校车的车次考虑。

问题四：从学生的学习效率和老师的教学效果等方面，对学校的软件设施、教学设施及运输设施等提出一些可行性建议。

三、符号说明CS：课程集合CSi：课程类别的编号；Cj：按优先级程度规定的课程编号；CR：时段集合；CRi：空闲时段集合；Rk：满足课程要求的空闲时段；0：否；1：是；T：间隔周期，单位：天；days：每周上课天数，单位：天；counts：周课时数；chapt：一次上课的节数；Tc：班级的受限一维数组；Tt：教师的受限一维数组；P：加权后的总满意度；Pt：老师的满意度；Ps：学生的满意度；Pu：学校的满意度。

四、模型的假设1.假设学校教室资源足够，不考虑教室资源对课程安排的约束；2.不考虑节日等因素对课程安排的影响；3.对于上课班级较多且任课老师较少的课程，每位老师可为几组班级授课，每组班级由若干个班级组成。

五、模型的建立与求解（一）问题一：建立排课表的模型，并研制出排课表的软件包。

利用对课程添加优先级属性，再根据优先级程度每个课程进行排课，即解决死锁问题。

同时也对时间段添加优先级属性，在每个课程排课的同时进行时间段的选择。

根据实际情况和所的资料综合分析实行对课程和时间段优先级的确定，并利用C++或FORTRAN软件对最优课程最优时间段的选择。

其步骤如下：1、系统模型的设计系统模型数据库是排课系统中的一个很重要的组成部分。

数据库中几个主要的表如下, 其中“*”号指出了各个表的主键:班级表(*班级号、专业号、入学时间、学制)；课程表(课程号、*课程名称、课程性质、授课要求、学时、选课人数、上课教室)；教师表(教师号、*教师名、所带课程、*所带班级数)；排课结果表(*课程名称、*上课时段、上课周次)。

2、模型的建立(1)教务处汇总开课计划时, 进行课程优先级分类。

分类的依据为课程的难度和重要性（公共必修课、专业必修课、专业选修课和公共选修课）分别为CS1, CS2,CS3，在对于这些类别根据该课程老师是否教授其他班课程和该课程课时的多少，将课程按优先级顺序分为C1,C2……Cj。

(2)判断课程集合CS中所有课程集合是否都安排完成, 若再没有待排课程则安排完毕, 否则根据顺序从CS 中选择一类课程,记作CSi。

(3)在CSi 中选择一门未排课程Cj,在时段集合CR中查找有空闲的时段CRi。

(4)从时段集合CRi中按序列获取一个时段Rk, 根据课程Cj的上课要求判断该时段是否可用并在可用时间段选取最好时间段。

(5)时段Rk 可用时, 课程Cj的班级和老师在时段Rk 的对应记录上未分配, 则可安排给课程Cj,更新相应数据库,转入(7)。

(6)发生上课时段冲突, 时段Rk 不可用时, 若时段Rk 是时段集合Cr i中最后一个, 则没有找到合适时段, 提示课程Cj安排失败, 转入(7) , 以便最后调整; 否则返回(4)。

(7)如果CSi中所有课程的教室安排完成, 返回(2)；否则返回(3) , 进行CSi+ 1 类课程的安排, 依次类推。

3、约束条件（1）为了降低排课的复杂性, 设计合理的排课顺序,设定教学任务的优先级。

教学任务i的优先级= 是否为公共课程或专业课程(0/1)+是否规定时段(0/1)+ 是否为必修课或基础课(0/1)。

这三个因素后括号的取值若为“是”, 取值为“1”, 否则为“0”; 表达式中的“+ ”是这三个因素的值连接。

如果排课优先级=“111”, 则表示: 公共课或专业课、规定了时段、必修课。

计算出所有教学任务的优先级后以降序排列, 然后按此顺序进行课程编排。

若两门课程的优先级相同，则对总学时较多的课程优先安排。

（2）为了使一门课的两次授课间隔合理, 规定了排课间隔周期。

每周上课天数days, 周课时数counts, 一次上课的节数chapt 等。

那么间隔周期T =[days/ (counts/ chap t)]-1。

如果一门课周课时数counts= 4, 为了使老师一次授课可以连排, 两节课代表一个上课时段, 上课节数chapt= 2, 一般每周上课6天, 则间隔周期T = 2, 即间隔2 天排下一次课(此类情况必要时也可间隔一天，如安排在周二和周四)。

必修课的间隔周期可按此法计算，选修课由于其学时和选课人数的不同可另作调整。

（3）、排课时不能使班级、教师、教室的时间相冲突，因前面已假设教室资源足够，可不考虑教室的影响，故此类约束条件用一个受限时间数组来表示, 为Tc、Tt。

分别为其建立一维数组, 数组元素个数为周上课天数days, 每个元素用“123456”的形式表示, 位数为每天上课的时段数, 取2节课为一个时段。

如某班级的受限一维数组Tc= (123456, 120000, 123456,003456, 123456, 103456)则表示该班级周二的下午和晚上、周四的上午、周六的上午3、4 节课时段空闲, 其余时段已排课或另有安排。

对于教师做同样的设置, 以便于检测空闲时段进行排课。

对某课程进行排课, 首先要检测教师、班级的受限时间数组，然后选择合适的时段进行排课, 如果交集为空, 则产生冲突, 做标记后返回重排。

另外, 对于某些高校完全实行学分制的情况, 排课时只需考虑教师、教室的冲突, 不需考虑教学班的冲突, 由学生根据自己的时间来选择合适的上课安排。

最后根据（二）问题二：利用所建模型及软件对本学期渭水校区的课表重排，并与现有课表进行比较。

由于对渭水校区所有班级课表重排数据太多，工作量太大，根据随机统计学抽样调查，随机抽选两个班级，对这两个班级的课程进行重排，根据这两个班的实验效果可以反映模型的可行性和实用性，将学校所有课程按1、2、3……编号，然后根据统计随机程序挑选，挑选班级为28010707和26050801（关于这两个班级的基础数据见附表1），并对其09-10第二学期的课表进行安排，安排的步骤与结果如下：一】班级28010707课表安排结果如下：1.课程的分类：公共必修课，0个；专业必修课，《土力学与基础工程》、《施工技术》、《钢筋混凝土》、《建筑电工学》、《施工组织》；选修课，《现代施工》、《系统工程》、《有限元素法》、《高层建筑结构》、《事故分析》、《土木工程施工（二）》、《结构稳定理论》。

2.课程优先级确定：《土力学与基础工程》>《建筑电工学》>《施工技术》>《钢筋混凝土》>《施工组织》>《现代施工》=《高层建筑结构》=《事故分析》=《结构稳定理论》=《土木工程施工（二）》=《系统工程》=《有限元素法》。