排课优化模型.doc

排课优化模型摘要在高校中，教学是培养学生的主要途径。排课的实质是为老师、学生的教学活动合理安排时间上和空间上的教学资源，以保证教学活动有计划有秩序地进行。因此在一系列的管理工作中，课表的编排是最基础、最复杂同时也是最核心的工作。在教学改革不断深化，招生人数逐年增加的情况下，做好有限教学资源的分配调度工作是有积极意义的。本文通过对排课问题的研究而对教师资源、教室资源以及时间资源的限制建立了最优化的评价模型。本模型不仅能对现有的教学资源进行最大化的调整和分配，而且还对教师资源的引进等有指导作用。1、问题一主要是通过数学模型的建立，使满足现有教学资源的条件下尽量使教学资源的最大化利用。我们根据附录中的附表中的属性进行分析，得出了教室资源、教师资源和时间资源等三方面之间存在的联系。根据以上三方面考虑我们建立了评价教学资源充分利用的最优化评价模型。2、由于问题二与问题一的区别仅在于晚上不能安排课程，所以本题中我们仍按问题一中根据教室资源、教师资源和时间资源之间的联系所建立的最优化评价模型进行求解。只是限制条件稍加区别而已。3、在问题一的求解结果之上我们发现，教师资源虽也尽可能的达到了最大的使用值，但仍然使得某些课程没有分配到教室进行上课，我们以聘请的老师尽可能上较多的周课时数的角度出发，对教师进行了较合理的利用。另外对聘请教师后为使教室的利用更加的充分对某些教室做出了简单的调整。该模型能尽可能的使教学资源达到最大化的利用，其解也具有较好的稳定性。为各高校排课的合理化提供了理论依据。同时，它具有很好的推广和应用价值。关键词：教室资源、教师资源、时间资源、优化模型一、 问题的重述对编号为C01C40的40门课程；，编号为T01T25的25名教师；编号为R01R18的8间教室，进行编排课表，编排规则为：每周以5天为单位进行编排；每天最多只能编排8节课（上午4节，下午4节），特殊情况下可以编排10节课（晚上2节），每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。（各类具体属性及要求见附表1，表2，表3）1、请你结合实际情况建立数学模型，通过编程计算，给出较为合理的课表编排方案，分析你所给出的方案的合理性。2、 如果不准晚上排课，排课结果是否有所变化，如何变化？3、对教师聘用，教室配置给出合理化建议。二、 模型假设1、 假设所有课程编号所对应的课程必须安排完2、 假设每门课程所对应的周课时数必须上完3、 假设每门课程的时间要求全部满足4、 假设每周以5天为单位进行编排5、 假设每门课程上课的教室座位数必须满足课程编号所对应的对教室座位最大要求数6、 假设上每门课程对教室必须满足该课程编号对教室类别的要求7、 假设在满足条件的情况下教师愿意上多门课程8、 假设同一教师不能在同一时间段上两门课程，同一教室不能在同一时间段被两门课程占用等9、 假设教师对开始分配的时间与实际需要上课时间相冲突时，教师愿意服从调整10、假设每天所排课程尽量均衡三、变量说明1、 表示教师编号为的教师对排课的满意度2、 表示对课程编号为的课程对教室标号为的教室的利用率教室3、 表示同类课程在星期的时段上课的效率4、 表示课程编号为的课程对教室座位最大要求数5、 表示课程编号为的课程对应教室编号为的教室的最大座位数6、 表示课程编号为的课程对教室的要求7、 表示课程编号为的课程对应教室标号为的教室类型8、 表示周时数为3节的课程门数的总和9、 表示课程号为的课程的周时10、 表示星期在时段所上的课程数11、分别表示教师资源、教室资源和时间资源的权重值12、 表示课程编号为的课程13、 表示教师编号为的教师14、 表示教室编号为的教室15、 表示为第时段16、 表示为星期其中；四、模型的建立与求解问题一：1. 建模思路：排课的主要任务是给课程安排时间、分配教室，同时要保证没有冲突发生（同一教师不能在同一时间段上两门课程，同一教室不能在同一时间段被两门课程占用等）。在保证教学资源时间空间的合理分配以及教学秩序有条不紊的前提下，尽量使教学资源最大化。并且课表的安排也要保证教学质量，比如同一课程的两次讲课的间隔尽量在一天以上，以保证学生有充足的作业、消化时间。在基于以上问题的分析下，我们从教师资源、教室资源以及时间资源三方面进行入手建立模型，以使上面三方面利用率达到最优为目标函数。2.模型建立：在考虑教学资源是否合理运用时，我们从以下三方面考虑： 教师资源：本模型通过教师对排课的满意度来进行衡量，这里我们设：教师对所排课时间满意时满意度为1，教师对所排课进行时间不满意时满意度为0。所以此时我们可以得到： 教室资源：本模型通过对教室的利用率的大小作为教室是否合理运用，因为比如说上某门课程要求的座位数少时，该门课程的同学就应该分配到能够容纳下他们的最小教室。比如说某门课程要求的座位数为40，分配是就尽量的应该将其分配到教室座位数为40的教室而不是在能满足此种条件下时将其安排到教室座位数为100的教室，而使得教室的利用率大大降低，这引起了教学资源的浪费。教室利用率表示为： 时间资源：我们将一天上课的时间分为5个时段，即上午第1、2节为第1时段，上午第3、4节为第2时段，下午第1、2节为第3时段，下午第3、4节为第4时段以及晚上为第五时段。关于这种因素本模型通过同类课程在星期的时段上课的效率来进行衡量，若在星期的时段上同类课程表示效率低下，此时我们用0来表示; 若在星期的时段上不同类课程时表示效率高，此时我们用1来表示;所以我们可以得： 其中通过以上各方面的分析从而建立了如下的数学模型：3.求解方法：第一步：确定上课教室由教室利用率可知：要使教室的利用率达到最大，我们在安排课程编号对应的教室时使满足教室类别的情况下，课程对教室座位最大要求只能数略小于或者等于所在教室的最大座位数。根据贪心算法的原理，我们先安排利用率最高的教室，这样我们就得出了一张含有课程编号，课程类别，周课时数，教室编号，对应教室要求，时间要求的字段的一张表。把课程表和教室属性表合并。第二步：确定老师上课我们仍根据贪心算法的原理，筛选完全满足教师上课要求的课程，我们就完全让这些教师去上这些课，即让这些教师满意度为1。在不能完全满足教室上课要求的教师，我们就考虑调整教师的上课时间的要求尽量使每位教师有课上以达到教师资源达到最大化利用，但此时的教师满意度为0。第三步：确定上课时间由一、二步可知，哪门课由哪个老师上，在哪个教室上。我们再根据时间资源考虑，同类课程尽可能不安排在同一时间，尽量满足某些老师不在同一天上课。我们先排完全满足条件的（最优），再在排不能完全满足最优的。4.求解结果：带人数据用matlab求解得：问题二1、模型的思路及建立：基于第一问求解的基础之上考虑，问题二中只是晚上不准排课，那么我们将一天分为4个时段即：上午第1、2节为第1时段，上午第3、4节为第2时段，下午第1、2节为第3时段，下午第3、4节为第4时段。则此时的取值为1，2，3，4。本问题中与问题一的区别仅在于晚上不能排课，故我们与问题一相同的因素和方式考虑，着种情况下我们只在约束条件中进行限制即可。根据以上分析则目标函数仍表示为：2、求解方法及结论:第一步：确定上课教室由教室利用率可知：要使教室的利用率达到最大，我们在安排课程编号对应的教室时使满足教室类别的情况下，课程对教室座位最大要求只能数略小于或者等于所在教室的最大座位数。根据贪心算法的原理，我们先安排利用率最高的教室，这样我们就得出了一张含有课程编号，课程类别，周课时数，教室编号，对应教室要求，时间要求的字段的一张表。把课程表和教室属性表合并。第二步：确定老师上课我们仍根据贪心算法的原理，筛选完全满足教师上课要求的课程，我们就完全让这些教师去上这些课，即让这些教师满意度为1。在不能完全满足教室上课要求的教师，我们就考虑调整教师的上课时间的要求尽量使每位教师有课上以达到教师资源达到最大化利用，但此时的教师满意度为0。第三步：确定上课时间由一、二步可知，哪门课由那个老师上，在哪个教室上。我们在根据时间资源考虑，同类课程尽量可能不安排在同一时间。和满足不在同一天上课的老师。我们先排完全满足条件（最优），最后在排不能完全满足最优的。根据以上分析由matlab求解可得：问题三：1、对教师聘请的建议:根据对问题一的理解和求解，以及对附表中各张属性表的关联我们可以发现：在现有的教学资源尽可能充分使用的情况下仍然有多门课程编号对应的课程没有教师教授。基于问题一的结果上，为使教学资源最大化的利用我们人为的对某些教师上课的时间进行了调整，使得某些老师在其闲暇的时间可以教授其他课程。调整后的结果显示仍有11门课程编号对应的课程缺少教师，这11门课程编号分别为,它们占了8种不同的课程类型，所以这时学校在条件允许的情况下同类型的课程可以聘请一名教师，此时可以聘请8位教师。如果学校的各种条件不允许上述情况时，学校可以聘请11教授名分别会这11门课程。2、对教室分配的建议：由于外聘教师教授这11门课程时对学校原有的教师配置并无关系，这些外聘的教师教授课程对学校原有的教师教授课程并不产生影响，且聘请的教师一般只教授12门课程，他们自身时间并不约束课程安排。所以学校对这11门课进行安排教室上课时，只要这11门课程编号对应的教室类型没被占用的时间均可安排新聘请的教师教授这11门课程，如果在很多时段该类型的教室同时闲置时，我们分别选取该类教室中对教室利用率最大的教室进行授课就可以了。短文： 课表编排具有规模大、约束条件复杂以及执行过程中不断变化等特点，难以实现自动化。目前很多学校的排课工作还只能靠教务科的管理员凭经验手工完成，这一般需要花费大量的时间和精力，而且每学期初的调课、换课也是教务科必须的额外工作负担。要想使各类资源优化利用，排课时需考虑涉及全校上上下下、方方面面的因素，而人脑处理数据的能力有限，很容易出错，一旦出错就会打乱正常的教学秩序导致教学事故。所以，完全以手工为主的排课管理已远不能适应新形势的要求，本文通过自动排课数学模型的建立使得学校课表编排工作能够实现自动化、高效化、人性化。五.模型的分析与检验本模型通过对教师资源、教室资源和时间资源等三方面的考虑。分别以该三方面设定了权重而建立了资源利用的最优化模型，对给出的数据本文通过贪心算法用进行求解。根据模型求解的结果基本使得教学资源达到了充分有效地利用，模型具有很好的稳定性。经检验，该模型能够对高校的排课问题有很好的适用价值，能尽可能的使教学资源达到充分的利用。六、模型的评价与推广从整个模型看，结构清晰，层次分明，数学表达式简洁直观地刻画了问题所提出的条件，目标函数的建立充分利用优化思想解决了题目给出的问题，并得到了组合数学中一些基本定理的支持。具有较强的实用性。本模型还有需要进一步改善的地方，如：当授课的学时数不一致（部分课程是2学时一次，部分课程为3学时一次）等问题。本模型还可以推广到其它冲突任务的合理优化安排问题。七、参考文献1 史书良，统计学原理，北京，清华大学出版社、北京交通大学出版社，2007年2 李大潜，工程数学学报，西安，西安交通大学理学院，2007年3 薛定宇、陈阳泉，北京，高等应用数学问题的MATLAB求解，2004年4 石博强、滕贵法，北京，MATLAB数学计算范例教程，2004年5 寿纪麟，数学建模方法与范例，西安，西安交通大学出版社，1995年6 姜启源、谢金星、叶俊，数学模型第三版，高等数学出版社，2003年8月八、附录附表一：课程属性及要求：课程编号课程类别周课时数对教室座位最大要求数对教室类别要求时间要求C011450多媒体教室上午C021430普通教室下午C031640普通教室下午C041425多媒体教室上午C051360普通教室下午C0624100普通教室下午C072450多媒体教室上午C082230普通教室上午C092440普通教室下午C102325多媒体教室上午C113660普通教室上午C123480普通教室上午C133650多媒体教室下午C143230普通教室下午C153340普通教室下午C164425多媒体教室上午C174460普通教室下午C184690普通教室上午C194450多媒体教室上午C204250普通教室上午C215430普通教室上午C225440多媒体教室下午C235325普通教室上午C245660普通教室下午C2554100多媒体教室上午C266350多媒体教室下午C276430普通教室下午C286440普通教室下午C296450多媒体教室上午C306430普通教室下午C317640普通教室上午C327425多媒体教室下午C337360普通教室无C347480多媒体教室上午C357450普通教室下午C368630机房无C378440机房上午C388225机房上午C398460机房下午C408450机房无附表2：教师属性：教师编号能胜任课程类别周最大课时数对教室类别要求上课时间要求尽可能不同天上课的教师T011，84多媒体教室或机房上午T4T0214普通教室下午T0316普通教室上午T0424多媒体教室上午T1T0524普通教室下午T0626普通教室无T0734普通教室上午T083，83普通教室或机房下午T0934普通教室上午T11,T18T1036多媒体教室上午T1148普通教室下午T9,T1244普通教室无T1346多媒体教室下午T1452普通教室上午T155，83普通教室或机房下午T23T1654普通教室上午T1764普通教室下午T1866普通教室无T9T1964多媒体教室下午T2074普通教室上午T2176普通教室下午T2276多媒体教室上午T233，84普通教室或机房无T15T244，86普通教室或机房上午T256，84普通教室或机房下午附表3：教室属性：教室编号最大座位数教室类别R01100多媒体教室R02100普通教室R03100普通教室R0450多媒体教室R0550普通教室R0650普通教室R0750普通教室R0860普通教室R0960普通教室R1060多媒体教室R1160普通教室R1260机房R1340机房R1440机房R1540机房R1640多媒体教室R1750普通教室R1840普通教室程序： %多媒体用1表示，普通教室用2表示， 机房用3表示，上午用1表示 下午用2表示 晚上用3表示 %c表示课程数组clear;clc;c=1 1 4 50 1 1; 4 1 6 40 2 1; 7 2 4 50 2 1; 10 2 3 25 1 1; 11 3 6 60 2 1; 12 3 4 80 2 1; 21 5 4 30 2 1; 23 5 3 25 2 1; 31 6 4 50 1 1; 34 7 6 40 2 1; 37 8 4 40 3 1; 38 8 2 25 3 1; %c29 c8 c16 c19 c25 c18没有符合要求的老师上课，暂时出除开； %r表示教室数组 r=1 100 1; 2 100 2; 3 100 2; 4 50 1; 5 50 2; 6 50 2; 7 50 2; 8 60 2; 9 60 2; 10 60 1; 11 60 2; 12 60 3; 13 40 3; 14 40 3; 15 40 3; 16 40 1; 17 50 2; 18 40 2; %t表示教室数据 %其中t01取得课程类别为1，没有取8其中t24取的是8没有取4课程类 t= 1 1 4 1 1; 3 1 6 2 1; 4 2 4 1 1; 7 3 4 2 1; 9 3 4 2 1; 10 3 6 1 1; 14 5 2 2 1; 16 5 4 2 1; 20 7 4 2 1; 22 7 6 1 1; 24 8 6 3 1; %sh存储上午课程与对应的教室 n=1;%表示存储上午课教室合理分配行数 %c1下午课程安排 c1=2 1 4 30 2 2; 3 1 6 40 2 2; 5 1 3 60 2 2; 6 2 4 100 2 2; 9 2 4 40 2 2; 14 3 2 30 2 2; 15 3 3 40 1 2; 17 4 4 60 2 2; 24 5 6 60 2 2; 26 6 3 50 1 2; 27 6 4 30 2 2; 28 6 4 40 2 2; 30 6 4 30 2 2; 35 7 4 50 2 2; 39 8 4 60 3 2; %c1(13 22 32)没有安排的下午课程 %t1表示下午教师表 其中t1(8)取的是教3类课程t1(15)取的是教5类课程t1(25)取的是教8类课程 t1=2 1 4 2 2; 5 2 4 2 2; 8 3 3 2 2; 11 4 8 2 2; 13 4 6 1 2; 15 5 3 1 2; 17 6 4 2 2; 19 7 6 2 2; 21 7 6 2 2; 25 8 4 3 2; m=1; for i=1:12 for j=1:18 if c(i,5)=r(j,3) & r(j,2)-c(i,4)=0 sh(n,:)=c(i,1) c(i,2) c(i,3) c(i,4) c(i,5) c(i,6) r(j,1) r(j,2); n=n+1; end end end k=1;%表示上午分配符合要求的老师去上课的对应表行数 for i=1:n-1 for j=1:11 if sh(i,2)=t(j,2)&t(j,4)=sh(i,5) & sh(i,3)=t(j,3) sh1(k,:)=sh(i,1) sh(i,2) sh(i,3) sh(i,4) sh(i,5) sh(i,6) sh(i,7) sh(i,8) t(j,1) ; k=k+1; end end end %m表示存储下午课教室合理分配行数 %xia存储上午课程与对应的教室 for i=1:15 for j=1:18 if c1(i,5)=r(j,3) & r(j,2)-c1(i,4)=0 xia(m,:)=c1(i,1) c1(i,2) c1(i,3) c1(i,4) c1(i,5) c1(i,6) r(j,1) r(j,2); m=m+1; end end end p=1;%p表示下午分配老师去上课的排列对应的行数 for i=1:m-1 for j=1:10 if xia(i,2)=t1(j,2)& t1(j,4)=xia(i,5) & xia(i,3)=t1(j,3) xia1(p,:)=xia(i,1) xia(i,2) xia(i,3) xia(i,4) xia(i,5) xia(i,6) xia(i,7) xia(i,8) t1(j,1); p=p+1; end end end %c2把课程没有上课要求但为偶数的课排晚上上课 c2=36 8 6 30 3 3; 40 8 4 50 3 3; %t2晚上上课的老师 w=1; t2=23 8 4 3 3; for i=1:2 for j=1:18 if c2(i,5)=r(j,3) & r(j,2)-c2(i,4)=0 wan(w,:)=c2(i,1) c2(i,2) c2(i,3) c2(i,4) c2(i,5) c2(i,6) r(j,1) r(j,2); w=w+1; end end end w1=1; for i=1:w-1 for j=1 if wan(i,2)=t2(j,2)& t2(j,4)=wan(i,5) & wan(i,3)=t2(j,3) wan1(w1,:)=wan(i,1) wan(i,2) wan(i,3) wan(i,4) wan(i,5) wan(i,6) wan(i,7) wan(i,8) t2(j,1); w1=w1+1; end end end %c3上下午课的总和 , c33 c3=1 1 4 50 1 1; 2 1 4 30 2 2; 3 1 6 40 1 2; 4 1 3 25 1 1; 5 1 3 60 2 2; 6 2 4 100 2 2; 7 2 4 50 1 1; 8 2 2 30 1 1; 9 2 4 40 2 2; 10 2 3 25 1 1; 11 3 6 60 2 1; 12 3 4 80 2 1; 13 3 6 50 1 2; 14 3 2 30 2 2 ; 15 3 3 40 2 2; 16 4 4 25 1 1; 17 4 4 60 2 2; 18 4 6 90 2 1; 19 4 4 50 1 1; 20 4 2 50 2 1; 21 5 4 40 2 1; 22 5 4 40 1 2; 23 5 3 25 2 1; 24 5 6 60 2 2; 25 5 4 100 1 1; 26 6 3 50 1 2; 27 6 4 30 2 2; 28 6 4 40 2 2; 29 6 4 50 1 1; 30 6 4 30 2 2; 31 7 6 40 2 1; 32 7 4 25 1 2; 33 7 3 60 2 3; 34 7 4 80 1 1; 35 7 4 50 2 2; 37 8 4 40 3 1; 38 8 2 25 3 1; 39 8 4 60 3 2; %t3上上下午课的老师 t3=1 1 4 1 1; 2 1 4 2 2; 3 1 6 2 1; 4 2 4 1 1; 5 2 4 1 2; 7 3 4 2 1; 8 3 3 2 2; 9 3 4 2 1; 10 3 6 1 1; 13 4 6 1 2; 14 5 2 2 1; 15 5 3 2 2; 16 5 4 2 1; 17 6 4 2 2; 19 6 4 1 2; 20 7 4 2 1; 21 7 6 2 1; 22 7 6 1 1; 24 8 6 3 1; 25 8 4 3 2; %把按上述排法后剩余的课程分析出来 z=1; for i=1:38 for j=1:k-1 if c3(i,1)=sh1(j,1)&c3(i,6)=sh1(j,6) break; end if j=k-1 kecheng(z,:)=c3(i,1) c3(i,2) c3(i,3) c3(i,4) c3(i,5) c3(i,6); z=z+1; end end end l=1; for i=1:z-1 for j=1:p-1 if kecheng(i,1)=xia1(j,1)&kecheng(i,6)=xia1(j,6) break; end if j=p-1 kecheng1(l,:)=kecheng(i,1) kecheng(i,2) kecheng(i,3) kecheng(i,4) kecheng(i,5) kecheng(i,6); l=l+1; end end end t4=6 2 6 2 3; 12 4 4 2 3; 18 6 2 2 3; tt=1; for i=1:l-1 for j=1:18 if kecheng1(i,5)=r(j,3) & r(j,2)-kecheng1(i,4)=0 wu(tt,:)=kecheng1(i,1) kecheng1(i,2) kecheng1(i,3) kecheng1(i,4) kecheng1(i,5) kecheng1(i,6) r(j,1) r(j,2); tt=tt+1; end end end pp=1; for i=1:tt-1 for j=1:3 if wu(i,2)=t4(j,2)&t4(j,4)=wu(i,5) & wu(i,3)=t4(j,3) wu1(pp,:)=wu(i,1) wu(i,2) wu(i,3) wu(i,4) wu(i,5) wu(i,6) wu(i,7) wu(i,8),t4(j,1); pp=pp+1; end end end ll=1; for i=1:l-1 for j=1:pp-1 if wu1(j,1)=kecheng1(i,1) & kecheng1(i,6)=wu1(j,6) break; end if j=pp-1 kecheng2(ll,:)=kecheng1(i,1) kecheng1(i,2) kecheng1(i,3) kecheng1(i,4) kecheng1(i,5) kecheng1(i,6); ll=ll+1; end end end %把剩余的老师分析出来 q=1; for i=1:20 for j=1:k-1 if t3(i,1)=sh1(j,8) break; end if j=k-1 t5(q,:)=t3(i,1) t3(i,2) t3(i,3) t3(i,4) t3(i,5); q=q+1; end end end qq=1; for i=1:q-1 for j=1:p-1 if t5(i,1)=xia1(j,8) break; end if j=p-1 t6(qq,:)=t5(i,1) t5(i,2) t5(i,3) t5(i,4) t5(i,5); qq=qq+1; end end end %sheyuke把没有安排的老师按要教的课程安排不满足他们上课时间,把上下午更改 f=1; for i=1:ll-1 for j=1:18 if kecheng2(i,5)=r(j,3) & r(j,2)-kecheng2(i,4)=0 sheyuke(f,:)=kecheng2(i,1) kecheng2(i,2) kecheng2(i,3) kecheng2(i,4) kecheng2(i,5) kecheng2(i,6) r(j,1) r(j,2); f=f+1; end end end hh=1; for i=1:f-1 for j=1:qq-1 if sheyuke(i,2)=t6(j,2)&sheyuke(i,3)=t6(j,3) sheyuke1(hh,:)=sheyuke(i,1) sheyuke(i,2) sheyuke(i,3) sheyuke(i,4) sheyuke(i,5) sheyuke(i,6) sheyuke(i,7) sheyuke(i,8) t6(j,1) ; hh=hh+1; end end end %查询出没有排完课的老师 %t7 表示还没有排完课的老师 d=1; for i=1:3 for j=1:pp-1 if t4(i,1)=wu1(j,9) break; end if j=pp-1 t7(d,:)=t4(i,1) t4(i,2) t4(i,3) t4(i,4) t4(i,5); d=d+1; end end end for i=1:qq-1 for j=1:hh-1 if t6(i,1)=sheyuke1(j,9) break; end if j=hh-1 t7(d,:)=t6(i,1) t6(i,2) t6(i,3) t6(i,4) t6(i,5); d=d+1; end end end %把没有排完课的课程找出 zz=1; for i=1:ll-1 for j=1:hh-1 if kecheng2(i,1)=sheyuke1(j,1) break; end if j=hh-1 kecheng3(zz,:)=kecheng2(i,1) kecheng2(i,2) kecheng2(i,3) k