一、 问题的重述

        排课问题是高校制定教学计划、安排教学过程中的一项较为复杂的工作，在高校教务管理工作中处于重要地位。高校在每学期末都要根据培养计划和教学资源作出下学期的教学安排, 这主要体现在对课表的编排上。其中涉及的关键要素很多, 包括教师、班级、教室和授课时段等。根据排课总体目标、约束条件、及优先级, 充分利用紧缺资源, 设计并实现高校课表安排系统。我校所面临的问题主要有：

        第一，为节省学校在校车往返方面的开支，安排课表时应尽量减少校车运行车次。

        第二，渭水校区有包括从大一至大三三个年级的学生，20个学院近700个班级，教学任务繁重，课表安排难度较大；

        第三，基于学生的学习规律与习惯，应根据课程的难度与重要性进行课程时段的安排，若安排不当，会导致学生的学习效果不佳；

        第四，校区地处偏僻,距市区较远，老师上课需乘车来回奔波，如果课表安排不当，就会导致部分老师前往渭水乘车次数过多或在渭水逗留时间过长；

        为此应根据教学计划和排课要求,综合考虑教师、课程、班级和授课时段等因素，协调合理的编排课表,制作一个系统模型，根据这个模型使老师、同学和学校尽可能满意，并且具有足够的可行性和可变动性。让老师满意，即让每位老师一周内前往渭水的乘车次数尽可能少，同时还要使每位老师在渭水逗留的时间尽可能少；让学生满意，即同一班级同一门课程在时间段上尽量间隔开来，另外相对重要的课程应尽量安排在较好的教学时段上；让学校满意，即节约学校开支，使每周派往渭水的车次尽可能少。

        二、问题的分析

        课表安排的主要任务是把各学院的课程汇总, 然后根据教学计划或教学环节制订全校各班级的课表。根据学校的实际情况和学校所面临的问题，可以将这类题归为以老师、学生和学校的满意情况为多目标的多约束的规划问题。为了使课表的编排准确、合理、快速、高效, 充分利用学校资源，根据已知条件提出以下可行性要求：

        1、课程时段的规定：将每天分为5个时段(上午两个,下午两个,晚上一个)，并规定为：1-2节课为第一时段，3-4节课为第二时段  依此类推。根据学生的学习效果及课程难度与重要性，将课程时段按有利程度分为五个等级，即第一时段>第二时段>第三时段>第四时段>第五时段。

        2、课程的优先级：将大学所有课程分为三类，

        1）其他如专业选修课或公共选修课等：少数班级开设的课程，课程相对简单，可以任意安排时段授课。

        2）专业必修课：少数学院或一个学院开设的课程，课程重要且开设的班级数较多，这类课尽量安排在较好时段；

        3）公共必修课：多个学院开设的课程，课程重要且开设的班级数最多，这类课尽量安排在最好时段；

        3、时间段的有效性：

        1）一个老师一天内的两节课应连排, 即尽量安排在同一天上午或同一天下午, 为教师上课提供方便，同时也减少了派往渭水的车次

        2）同一班级同一门课的两次授课时间必须隔天，但相隔天数不宜超过两天；

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

        5、应避免各种冲突: 

        1）教师不冲突, 同一教师不能同一时间在不同地点上课。 

        2）学生不冲突, 同一班级学生不能在同一时间上两门或两门以上课程；

        3）教室不冲突, 同一教室同一时间不能安排两门课程，人数不能超过教室的最大容量；

        4）课程不冲突, 同一班级同一课程不能同一时间在不同地点上课； 

        根据上述可行性要求，解决以下问题： 

        问题一：

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

        问题二：

        利用加权综合评判法，对老师满意度、学生满意度和学校满意度进行加权综合评价。其中老师满意度从老师的滞留时间和老师的乘车次数方面考虑，学生满意度以重要课程的安排的时间段好坏考虑，学校的满意度以校车的车次考虑。

        问题三：

        要求建立排课表的数学模型，先确定公共基础课的课程数，并将这些课程数联系到教师和学生的满意程度，在优化满意程度的条件下，排出各个公共基础课的授课区域，指定老师在班级授课时间段的区域，并让老师在这个区域内对不同的班级的授课时间段进行排布。然后将专业课安插到未被占用的时间段上，最后是选修课。同时课程的安排原则是尽可能选择在较好时段。 

        问题四：

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

        三、符号说明

        ：课程集合

        ：课程类别的编号；

        ：按优先级程度规定的课程编号；   CR：时段集合；

        ：空闲时段集合；

        ：满足课程要求的空闲时段； 0：否；  1：是；

        ：间隔周期，单位：天；

        ：每周上课天数，单位：天； counts：周课时数；

        ：一次上课的节数； 

        Tc：班级的受限一维数组； 

        Tt：教师的受限一维数组； 

        P：加权后的总满意度； 

        Pt：老师的满意度； 

        Ps：学生的满意度；

        Pu：学校的满意度。

        四、模型的假设

        1.对于上课班级较多且任课老师较少的课程，每位老师可为几组班级授课，每组班级由若干个班级组成。

        2.假设学校教室资源足够，不考虑教室资源对课程安排的约束； 

        3.不考虑节日等因素对课程安排的影响；

        五、模型的建立与求解

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

        利用对课程添加优先级属性，再根据优先级程度每个课程进行排课，即解决死锁问题。同时也对时间段添加优先级属性，在每个课程排课的同时进行时间段的选择。根据实际情况和所的资料综合分析实行对课程和时间段优先级的确定，并利用C  或FORTRAN软件对最优课程最优时间段的选择。其步骤如下： 

                1、系统模型的设计

                系统模型数据库是排课系统中的一个很重要的组成部分。数据库中几个主要的表如下, 其中“* ”号指出了各个表的主键:

                班级表(* 班级号、专业号、入学时间、学制)；

                课程表(课程号、*课程名称、课程性质、授课要求、学时、选课人数、上课教室)；

                教师表(教师号、*教师名、所带课程、*所带班级数)； 排课结果表(*课程名称、*上课时段、上课周次)。 

                2、模型的建立

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

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

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

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

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

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

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

                3、约束条件

                （1）、排课时不能使班级、教师、教室的时间相冲突，因前面已假设教室资源足够，可不考虑教室的影响，故此类约束条件用一个受限时间数组来表示, 为Tc、 Tt。分别为其建立一维数组, 数组元素个数为周上课天数days, 每个元素用 “123456”的形式表示, 位数为每天上课的时段数, 取2节课为一个时段。如某班级的受限一维数组Tc= (123456, 120000, 123456,003456, 123456, 103456)则表示该班级周二的下午和晚上、 周四的上午、 周六的上午3、4 节课时段空闲, 其余时段已排课或另有安排。对于教师做同样的设置, 以便于检测空闲时段进行排课。对某课程进行排课, 首先要检测教师、 班级的受限时间数组，然后选择合适的时段进行排课, 如果交集为空, 则产生冲突, 做标记后返回重排。

                （2）为了使一门课的两次授课间隔合理, 规定了排课间隔周期。每周上课天数days, 周课时数counts, 一次上课的节数chapt 等。那么间隔周期T =[days/ (counts/ chap t)]-1。如果一门课周课时数counts= 4, 为了使老师一次授课可以连排, 两节课代表一个上课时段, 上课节数chapt= 2, 一般每周上课6天, 则间隔周期T = 2, 即间隔2 天排下一次课(此类情况必要时也可间隔一天，如安排在周二和周四)。必修课的间隔周期可按此法计算，选修课由于其学时和选课人数的不同可另作调整。

                （3）为了降低排课的复杂性, 设计合理的排课顺序,设定教学任务的优先级。教学任务i的优先级= 是否为公共课程或专业课程(0/1) 是否规定时段(0/1)  是否为必修课或基础课(0/1)。这三个因素后括号的取值若为“是” , 取值为 “1” , 否则为 “0” ; 表达式中的 “  ” 是这三个因素的值连接。如果排课优先级=“111” , 则表示: 公共课或专业课、规定了时段、必修课。计算出所有教学任务的优先级后以降序排列, 然后按此顺序进行课程编排。若两门课程的优先级相同，则对总学时较多的课程优先安排。

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

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

        由于对渭水校区所有班级课表重排数据太多，工作量太大，根据随机统计学抽样调查，随机抽选两个班级，对这两个班级的课程进行重排，根据这两个班的实验效果可以反映模型的可行性和实用性，将学校所有课程按1、2、3  编号，然后根据统计随机程序挑选，挑选班级为28010707和26050801（关于这两个班级的基础数据见附表1），并对其09-10第二学期的课表进行安排，安排的步骤与结果如下：

        一】班级28010707课表安排结果如下：

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

            2.课程的分类：公共必修课，0个；专业必修课，《土力学与基础工程》、《施工技术》、《钢筋混凝土》、《建筑电工学》、《施工组织》；选修课，《现代施工》、《系统工程》、《有限元素法》、《高层建筑结构》、《事故分析》、《土木工程施工（二）》、《结构稳定理论》。 

            3.课程布置步骤：

                1）鉴于《高层建筑结构》与《施工组织》、《事故分析及处理》与《结构稳定理论》上课时间的连续性及间隔周期的相似性，可分别等效为一门课程进行安排，安排见表1；

                2）《电工学与施工技术》间隔周期均为1-2天，可将其对称安排在周二与周四上午两个时段，安排见表1；

                3）鉴于《土力学与基础工程》的优先性与重要性，应首先对其进行安排，间隔周期为1天，规定时段为第一时段，则安排为每周一、三、五第一时段； 

        二】班级26050801课表安排结果如下： 

                1、课程分类：公共必修课，《大学英语（四）》、《概率论与数理统计》、《毛泽东思想与邓小平理论》；专业必修课，《积分变换》、《面向对象程序设计》、《经济地理与区域规划》、《测绘工程基础》；选修课，0个。 

                2、课程优先级：《测绘工程基础》>《大学英语（四）》>《概率论与数理统计》=《毛泽东思想与邓小平理论》=《面向对象程序设计》>《经济地理与区域规划》>《积分变换》。 

                3、课程布置步骤：

                ）鉴于《测绘工程基础》和《大学英语（四）》的优先性与重要性，应首先对这两门课程进行安排，间隔周期均为1天，规定时段均为第一时段，安排见表2；

                2）鉴于每位《毛泽东思想与邓小平理论》老师为多组班级授课，可将其安排在上午和下午的后两节课（3-4节或7-8节），以保证老师上课的连续性、来渭水乘车次数最少，安排见表2；

        ) 《概率论与数理统计》安排原理同《毛泽东思想与邓小平理论》，安排见表2；

        .所排课表与原课表的比较

                （1）两者公共必修课及专业必修课所排时间段相差不大，选修课相差较大； 

                （2）所排课表所选时间段尽量往好的时间段内取，而原课表由于某些原因而选择相对较差的时间段；

                （3）所排课表课程相对紧凑，学生、老师上课较原课表连续。

        （三）问题三：给出评价指标评价所建模型，并指出模型优点与不足之处。

                对于模型的评价，可以各个影响因素进行加权综合评价方法对模型进行综合评价。提出满意度的概念：教师、学生和学校对所排课表的满意程度，用百分制的打分方式表示。满意度越高，则老师、学生和学校最模型的综合评价越高。

                1.满意度的计算：

                满意度P由教师的满意度Pt、学生的满意度Ps和学校的满意度Pu表示。 并关于老师、学生和学校进行加权评价，其权重分别为：0.4,0.3,0.3。 P=0.4*Pt 0.3*Ps 0.3*Pu 2.满意度的影响条件：

                        （1）教师的满意度：教师一周内在渭水校区的逗留总时间，教师一周内前往渭水的乘车次数；

                        （2）学生的满意度：教师在一周内两次上课的时间间隔，优先等级高的课程安排的时段的好坏；

                        （3）学校的满意度：学校一周派往渭水的车次数。 

                3.评价满意度的具体评价指标： 

                        （1）教师的初始满意度（100分），在学校逗留一次扣去10分，因乘车次数扣去（实际乘车次数—最小乘车次数）乘以10分； 

                        （2）学生的初始满意度（100分），教师在一周内两次上课的时间间隔小于一天或大于两天扣10分，公共必修课和专业必修课分配在下午每课扣10分，选修课分配在晚上或周末每课扣10分； 

                        （3）学校的初始满意度（100分），根据乘车次数，扣去（教师实际乘车次数—教师最少乘车次数）乘以10分。 

                4.满意度指标的转化： 将教师、学生和学校的初始满意度—相应扣去的分数为教师、学生和学校的满意度，再将这个满意度化为百分制。

                5.对模型所排出的课表进行抽样评价，以问题二中随机抽取的两个班级进行评价，其评价结果如下：

        第一组评价：

        （一）所排课表：

                转化后的满意度Pt=90

                转化后的满意度Ps=97.5

                转化后的满意度Pu=90.8

                加权后总满意度P=0.4*Pt 0.3*Ps 0.3*Pu=92.49 原课表，见附表：

                转化后的满意度Pt=81.2

                转化后的满意度Ps=95

                转化后的满意度Pt=81.2

                加权后总满意度P=0.4*Pt 0.3*Ps 0.3*Pu=85.34 

        （二）第二组评价 所排课表：

                转化后的满意度Pt=88.6

                转化后的满意度Ps=98.6

                转化后的满意度Pu=88.6

                加权后总满意度P=0.4*Pt 0.3*Ps 0.3*Pu=91.6 原课表，见附表：

                转化后的满意度Pt=85.7

                转化后的满意度Pu=85.7

                加权后总满意度P=0.4*Pt 0.3*Ps 0.3*Pu=87

                根据数据及图可以得出：利用模型建立的课表，根据统计学知识，抽样调查，调查的结果模型建立的课表的总满意度和各种满意度都略高于原课表。

        六、模型的优缺点分析

                优点：

                （1） 由于考虑老师的带课班数及所授课程的重要程度，所以安排课程后可行性得到较好的保证。 

                （2） 根据这种根据优先级先后排课表的方式即要比精确排表方式要简单和快捷，而且所得到的实验结果也较好，满意度均在90分以上，保持了原课表一样的高效性；

                缺点：

                （1） 由于模型许多条件都是根据经验进行的人为规定，所以并不能达到最优化的程度。

                （2） 由于模型未考虑到教室数量对排课的限制，也未考虑到其他各种客观或主观条件对排课的限制，故排课后的准确性比原课表要差。 

        七、模型的改进

                1．由于在建立模型时只是单纯的减少老师次数来减少车次数，而实际上一个车次可以移动40多为老师，那么41与80所排出的车次数一样，那么可以让一部分老师乘车回家，而让一部分老师留校休息，而这个数量需要准确计算才能得出，所以对车次的优化对模型的改进也很有意义。

                2.由于在建立模型时未考虑到一个老师教授不同课程和老师由于生病或其他原因而临时改变课程时间段等实际较可能出现的情况。所以要准确的排出课表就需将每个老师用程序编码，将每个课程也用程序编码，一个老师码可以对应多个课程码，同时老师码可以缺码或编码号后移，也可以是课程号缺码或课程码后移，这样就可以增加模型的机动性，使得程序更加实用。

        八、模型的总结

                高校排课系统一直是高校教务管理中难以解决的问题, 由于约束条件多, 教学资源要求复杂, 而且每个学校有其特殊情况, 因此排课要求也不完全一样。按照渭水校区班级较多、课程任务繁重和老师离学校距离远和来校难度大等特点, 设计出系统,能较准确高效的作出安排, 满足必要的约束条件, 能够在一定程度上避免冲突, 提高教学管理水平。

        九、可行性建议

                1、较为重要的课程一次上课所对应的班级不宜过多，这样既可以减轻老师上课负担，提高教学进度，又可以避免学生因教室面积大、人数多等原因而对听课效果产生的不良影响。

                2、重要或是较为重要的课程尽量不要安排在晚上，由于学生的学习习惯和规律以及客观条件的限制，学习效率较白天低。可以考虑把公共选修课或专业选修课安排在晚间，以减小脑力负担。此外，重要的课程也尽量不要安排在周末，因受主观条件等的影响，不利于学生对知识的消化。

                3、诸如C语言，C  ，数据结构，数据库等计算机方面的课程，应尽量安排在计算机机房上课，在学习课程内容的同时锻炼编程等实际动手操作能力。

                4、制定课表时，应尽量安排出机动课时段，机动教室，以配合由于种种原因所导致的临时调课情况。

                5、在教室分配上，应尽量避免相临的两节课所用教室距离过远，如连续两节课教室分别在WM3501和WX1504，由于课间时间较为短暂，会在路上耽误过多时间甚至迟到，从而影响教学进度。

                6、在教室分配方面，应避免仅有一个或两个班所上的课程占用大教室，这会因学生就座相对分散，而导致老师不便授课、影响课程进度，另一方面，影响学生听课效果。

                7、尽量避免把两门以及两门以上难度较大的课程安排在连续时段上，这会增加学生脑力负担，不利于学生对知识的吸收。

                8、英语等需要记忆的课程应尽量避免安排在一天的最后时段，此阶段学生大脑进入疲劳期，学习效果不佳。