排课问题分析

排课问题分析摘要：本题要求我们对多约束条件的典型组合进行分析，求解，并作最优化处理。基于此种原因，我们先对各个元素间的冲突做预处理，进行约束条件的规划，再通过matlab软件将教室、教师、课程和时间间的约束条件统一化，构成R-T-C表（详见附表），再将各个元素进行优先级的计算，从而根据排课的优化模型，求出最优解。经过对所给的表格，数据的深入分析，我们可以得知，教师明显缺少，比如课程学时要求有160个课时，然而教师能上的课时仅有116个课时，所以开始排课时，不考虑教师，向教师中安排课程。由于同类课程最好不要放在一起，同时根据老师的需求和教室的开放时间进行分配，经过与我们实际的课表的排课情况的分析，比如隔一天排同一课，课程类别不同的课程不在同一时间上课，我们可以大致的排出一个按教室上课的表，即R-T-C表。通过对R-T-C表的分析，发现有很多课没老师上和老师没课上的情况，我们就对其进行相应的，合理的调整。最后发现还是老师要外聘。将外聘14名老师去上相应没人上的科目，具体情况见附表。最后，我们得到了一相对优化的，以教室为准的课表（详见附表），从而解决问题（1）的要求。对于我们课表的安排，发现再没对晚自习有其他条件约束是不会对所排的课表有所影响。关键词：排课问题组合规划多目标函数数据量化优先级一、问题重述对于有课程40门，教师共有25名，教室18间的条件下合理的安排课程表，而课程、教师、教室的具体属性及要求详见附表（表1，表2,表3）对于课表德编排，题目有如下规则：每周以5天为单位进行编排；每天最多只能编排8节课（上午4节，下午4节），特殊情况下可以编排10节课（晚上2节），每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。要求所要解决的问题：请你结合实际情况建立数学模型，通过编程计算，给出较为合理的课表编排方案，分析你所给出的方案的合理性。如果不准晚上排课，排课结果是否有所变化，如何变化？对教师聘用，教室配置给出合理化建议。二、问题分析随着现代教学的改革及各项教育工程的实施，新的教育体制对课表的编排提出了更高的要求。但现实生活中，排课问题屡屡皆是，小学如此，中学如此，大学更是如此，不仅科目多样，而且教室、老师多变，这使得排课问题往往是很令人费解的。经过分析，排课问题就是的多资源组合问题，问题的求解就是找出各个元素间的对应关系。进而将各个元素间的联系进一步确定，转化成一个可以量度其大小的值，从而确定优先级，而我们又将如何确定各元素间的关系，目标函数的确定？根据已有知识可以知道，本题主要分析的是建立一个排课的优化模型。而它是一个在课程类别、教师编号、教师及时间上的一个四维空间模型，在各种约束条件下的组合规划问题，其实质就是解决各因素间的冲突问题。在模型建立后，我们有根据什么参量得到排课的最优解。三、基本假设模型假设：1、学校的教师和教室资源及学生班结构在一个学期不会有的变动2、所有的教室都在同一个校区，且1〜2节课的教室到3〜4节课的教室的路程不超过10min3、在一学期，任课教师身体都非常健康，不存在因病因事缺课的情况4、各种教学资源（课桌、多媒体、机房电脑）在一学期都不会发生故障，影响上课5、在上课期间，老师、学生都不迟到，不影响上课质量6、当有3个课时时，我们当做2个课时处理，及3节连堂上符号说明：Rn教室编号n=1,2,3・・・.18Cn课程类别n=1,2,3・・・.40Tn教师编号n=1,2,3-..25Y—外聘外聘教师编号n=1,2,3・・・..14P(TRC)T老师在R教室上C课X时间段效率X教室利用率X3教师满意度D优化级的量度值W权衡时间段效率参数权衡教室利用率参数

岛权衡教师满意度参数Q安排课程的最优值相关名词解释:上课总人数教室最大容纳量时间段效率：经上网查询及对相关资料的查阅，我们得知一天听课效率最高的是上午8〜10,下午1〜3,故我们定义上午1〜2的听课效率为3,其上课总人数教室最大容纳量教室利用率：为充分利用教室资源，我们定义：教室利用率二四、问题的分析及模型的建立问题分析(1)从数学角度上讲，本题主要分析建立一个排课模型，而它是一个在课程类别、教师编号、教师及时间上的一个四维空间模型，在各种约束条件下的组合规划问题，其实质就是解决各因素间的冲突问题。在此为了简化处理，先从课程类别、教室编号入手，建立一个关于C-R的关系表，再采用化零为整的思路建立我们的目标函数一一优化模型，最后，我们根据各因素对排课模型的优先度，求解出排课模型的最优解。在对问题初始化分析时，我们发现课程类别、教室编号、教师、上课时间存在这么一个对关系：1—1的对应关系)1—n的对应关系)n—n的对应关系进而，我们再对它们之间的属性分析，根据它们间的联系求出一种相对合理的排课方案，最后，对方案的合理性进行分析。模型的建立经过分析，我们需将所有课程尽量合理的安排在一个星期。首先我们将一个星期划分为五天，记作1、2、3、4、5,将一天分为四个部分，记作1、2、3、4,进而，我们将得到一个5X4的矩阵。其中，j=1、2、3、4、5分别表示星期一、星期二、星期三、星期四、星期五；i二1、2、3、4分别表示1〜2节课、3〜4节课、5〜6节课、7〜8节课。即有：力ISP(TRC)t=1r=1c=1我们记作P(TRC)是一个TXRXC维的数列矩阵，表示T老师在R教室上C课，我们定义？(TRC)=1时，即老师、教室、课程三者都相互符合是记作1而P(TRC)=0时，即老师、教室、课程三者中有一项不符合记作0规定：A(TR)表示T老师到R教室上了一次课是，即2个节B(TR)表示T老师到R教室上总课时约束条件：每一个时间段都不能多于一个老师在一个教室上课，此时应满足的条件是：IP(TRC)<1ngN(N=1、2、3-25)t=1每位老师在每一天不能同时对同一个班上上两次课，IP(TRC)<1i=1某位老师在某一间教室上课时，安排的课就该在这间教室排完，此时应满足的条件是：x室4P(TRC)=2xA(TR)xB(TR)J=1i=1当一位老师连续两天对同一个班上两次课以上的次数越少、课程安排在听课效率高的时间段次数越多和老师与老师之间的冲突(满意度)次数越少，此时定义：Q=IIIP(TRC)t=1r=1c=1同时有满足以上的约束条件，Q将取到最优值，即此时安排的课表最优化排课的预处理同一教师在同一时间不能安排两门课同一教室在同一时间不能安排两门课同一时间安排的课时总数不能大于教室的课时总数所提供的教室属性安排课程的所需教室属性一致优化级的计算：考虑到课表的安排是为了按时保量的完成教学任务，而其影响因素有众多，这里我们主要考虑一下三种：1)时间段效率2）教室利用率3）教师满意度所以我们对课表的安排原则将依据优先级的大小进行排课。先对以上三个因素进行量化处理可得到：时间段效率：上午1〜2上午3〜4下午1〜2下午3〜43021教室利用率:1〜0.80.6〜0.80.4〜0.60.2〜0.43210教师满意度:很满意满意一般不满意3210我们定义优先级的函数表达式为：D=W1XX1+XXUW3XX3其中W1W2W3表示相应参数，可根据实际情况进行调整的通过上式，我们可以很容易得知上课的时间段效率、教室利用率、教师满意度越大，D值就越大即优先级越大，就优先排课；反之，D值越小，优先级就越小，就相对后排课。通过模型得到的T-R-C表（见附表），再根据优先级的排课，我们可得到一个相对优化的课表：R3教室一周课程安排星期一星期二星期三星期四星期五上午1-2C12-T9上午3-4C18-T24C18-T24下午1-2C6-T6下午3-4这里就不一一罗列，其余详见附表。模型的评价与改进优点：到了一种排课的方法，即将课程表按课时数撤分，再按没门课程的优先顺序依次放入课表中。在考虑其他因素（某课程只能安排在固定的某时间段上课，教师只在固定时间段安排课程）的情况下，本模型便于进一步发展、完善（只需改变最优解的参数加相应限制就可解决）。比起目前最相对合理的遗产法简单易懂很多。缺点：有很多待改进之处，该算法的优先级只是根据经验常识来进行优先级安排课程，具有一定的非科学性，如果能根据一定的科学知识，对课程的优先级进行科学的评定，科学的地算出其优先级系数，再确定其优先级，会具有更好的合理性。再解题过程中限制条件多，数据量大，过程相对较繁琐。模型推广本模型有编程优化的模块，但排课表是人为因素较多，也是为了满足课程的安排过程中更人性化。因此本模型适用于中小规模的排课，其主要限制因素是程序完善度不高，如要进行推广，则必须增加程序的模块，使其更完善，相信改进完善后，即可更科学的实现大规模大排参考文献数学建模（上册），电子机械高等专科学校，二零一零年三月数学建模资料——最优化模型.pdf2010.7回溯法baike.baidu./view/45.htm?fr=ala012010.7贪婪法——baike.baidu./view/112297.html?tp=0102010.7一天的最有听课效率时间段zhidao.baidu.2010.7附表：表1:教师属性:教师编号能胜任课程类别周最大课时数对教室类别要求上课时间要求尽可能不同天上课的教师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普通教室或机房下午

表2：课程属性及要求:课程编号课程类别周课时数对教室座位最大要求数对教室类别要求时间要求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机房无表3：教室属性:教室编号最大座位数教室类别R01100多媒体教室R02100普通教室R03100普通教室R0450多媒体教室R0550普通教室R0650普通教室R0750普通教室R0860普通教室R0960普通教室R1060多媒体教室R1160普通教室R1260机房R1340机房R1440机房R1540机房R1640多媒体教室R1750普通教室R1840普通教室表4：T-R-C表课程老师教室容量C1T1R(10)50/60C2T2R(18)30/40C3T3R(18)40/40C4C5C6T6R(2)R(3)100/100C7T4R(4)50/50C8T6R(18)30/40C9T5R(18)40/40C10C11C12T7R(2)R(3)80/100C13T10R(4)R(16)50/50C14T8R(18)40/40C15T9R(18)40/40C16T13R(16)30/40C17T11R(8)R(9)R(11)60/60C18T24R(2)R(3)90/100C19T11R(5)R(6)R(7)R(17)50/50C20T12R(5)R(6)R(7)R(17)50/50C21T16R(18)30/40C22

C23C24C25C26T19R(4)50/50C27T18R(18)40/40C28T17R(18)40/40C29C30C31C32C33T20R(8)R(9)R(11)60/60C34T22R(1)80/100C35T21R(5)R(6)R(7)R(17)50/50C36C37C38T15R(13)R(14)R(15)25/40C39T25R(12)60/60C40T23R(12)60/60表5：各教室课程安排:R1教室一周课程安排星期一星期二星期三星期四星期五上午1-2C34-T22C34-T22C25上午3-4C25下午1-2下午3-4R2教室一周课程安排星期一星期二星期三星期四星期五上午1-2C18-T24上午3-4C12-T9下午1-2C6-T6下午3-4R3教室一周课程安排星期一星期二星期三星期四星期五上午1-2C12-T9上午3-4C18-T24C18-T24下午1-2C6-T6下午3-4R4教室一周课程安排

星期一星期二星期三星期四星期五上午1-2C13-T10C19-T11C13-T10上午3-4C19-T11下午1-2C26-T19下午3-4R5教室一周课程安排星期一星期二星期三星期四星期五上午1-2C21-T16C35-T21上午3-4C35-T21C21-T16下午1-2C30C17-T12C30下午3-4R6教室一周课程安排星期一星期二星期三星期四星期五上午1-2C31-T21上午3-4下午1-2C28-T17C9-T5C9-T5下午3-4C28-T17R7教室一周课程安排星期一星期二星期三星期四星期五上午1-2C8-T6上午3-4下午1-2C20-T12C27-T17下午3-4C27-T17C3-T3R8教室一周课程安排星期一星期二星期三星期四星期五上午1-2C31上午3-4C31下午1-2C5C33-T20下午3-4R9教室一周课程安排星期一星期二星期三星期四星期五上午1-2C11C11C11上午3-4下午1-2C24下午3-4C24C24R10教室一周课程安排星期一星期二星期三星期四星期五

上午1-2C1-T1C29C29C7-T4上午3-4C7-T4C1-T1下午1-2下午3-4R11教室一周课程安排星期一星期二星期三星期四星期五上午1-2上午3-4下午1-2C17-T11下午3-4C17-T11R12教室一周课程安排星期一星期二星期三星期四星期五上午1-2上午3-4下午1-2C40-T23C39-T25下午3-4C39-T25C40-T23R13教室一周课程安排星期一星期二星期三星期四星期五上午1-2上午3-4下午1-2C28-T18下午3-4C36C28-T18R14教室一周课程安排星期一星期二星期三星期四星期五上午1-2C37上午3-4C37下午1-2C36C36下午3-4R15教室一周课程安排星期一星期二星期三星期四星期五上午1-2C38-T24上午3-4下午1-2下午3-4R16教室一周课程安排星期一星期二星期三星期四星期五

上午1-2C10C16-T13C4上午3-4C4C16-T13下午1-2C22下午3-4C32C22C32R17教室一周课程安排星期一星期二星期三星期四星期五上午1-2上午3-4下午1-2C15-T9C14-T08C2-T2下午3-4R18教室一周课程安排星期一星期二星期三星期四星期五上午1-2C23上午3-4C8-T6下午1-2C3-T3下午3-4C2-T2C3-T3C14-T8表6：外聘教师课程安排表:外聘教师课程课时教室时间YT1C254R1二34，五12YT2C304R5二56，五56YT3C314R8一12，三34YT4C53R8二123YT5C116R9一12，三12，五12YT6C244R9一56，三78，五78YT7C294R10二12，四12YT8C366R14一56，三78，五56YT9C103R16一123YT10C44R16二34，五12YT11C224R16一56，四78YT12C324R16二78，五78YT13C233R18三123YT14C374R14二12，四34clear；C=[1221121213121211123222422221211222122211333232423321311232124211423243424221412252125211521253325241622162126212程序附录:-1-11-1-111-1111-1-1-11-11111-1-11-1-1-1

TOC\o"1-5"\h\z1-11-101-1011-101402-1002100110-10020002100-100211118100-1902000-1001005-123021002-1002090-1001002-1001100501505100622621731721723724722831821811823822];T=[184104106204204206304383304306408404406502583504604606604704706706384486684];R=[414242212222225-100KRc-t-*#网>出身建>部Rc-t-nzeros(25“18)'riHr一8ormHr25for3Hr40ifR(r-1)〉HC(F3)ilHCp1)'ifTGIhlYHil一一T(nh2)Ril*T(m-4)\switch(i4)case1ifRF2YH1Rr+(m“iYrendcase2ifR(r-2)H2Rr+(m“iYrendcase3ifR(r-2)R3Rr+(m3)Hl'endcase4ifR(r-2)H1--R(r-2)R3Rr+(m3)Hl'endcase5ifR(r-2)R2--R(r-2)H3Rr+(m“iYrendendendendendendendRt；%Rc为教室与课程的关系Rc二zeros(18,40)；fori=1:18forn=1:40ifR(i,1)>=C(n,3)&&R(i,2)==C(n,4)Rc(i,n)=1;endendendRc；%Tcform=1:25forn=1:40ifT(m,1)=C(n,1)||T(m,2)=C(n,1)ifT(m,3)>=2*C(n,2)q=T(m,4);t=T(m,5);switchqcase1ifC(n,4)==1switchtcase1ifC(n,5)==1Tc(m,n)=1;endcase-1ifC(n,5)==-1Tc(m,n)=1;endcase0ifC(n,5)==1||C(n,5)=T||C(n,5)=0Tc(m,n)=1;endendendcase2ifC(n,4)==2switchtcase1ifC(n,5)==1Tc(m,n)=1；endcase-1ifC(n,5)==-1Tc(m,n)=1;endcase0ifC(n,5)==1||C(n,5)=T||C(n,5)=0Tc(m,n)=1;endendendcase3ifC(n,4)==3switchtcase1ifC(n,5)==1Tc(m,n)=1;endcase-1ifC(n,5)==-1Tc(m,n)=1;endcase0ifC(n,5)==1||C(n,5)=T||C(n,5)=0Tc(m,n)=1;endendendcase4ifC(n,4)==1||C(n,4)==3switchtcase1ifC(n,5)==1Tc(m,n)=1;endcase-1ifC(n,5)==-1Tc(m,n)=1;endcase0ifC(n,5)==1||C(n,5)=T||C(n,5)=0endendendcase5ifC(n,4)==2||C(n,4)==3switchtcase1ifC(n,5)==1Tc(m,n)=1;endcase-1ifC(n,5)==-1Tc(m,n)=1;endcase0ifC(n,5)==1||C(n,5)=T||C(n,5)=0Tc(m,n)=1;endendendendendendendendTc;%在完全满足的情况下课程选择最优化的老师%Ct说明行代表课程，列代表能上该课的老师编号%if有相同编号的老师那针对该门课程进行求最优值，将值最大的老师放入相应课程中Ct=[100;00;000;TOC\o"1-5"\h\z00;00;60;00;00;60;400;000;923;000;230;00;000;TOC\o"1-5"\h\z120；00；000；240；00；000；00；000；000；00；1825；171825；000；171825；000；000；000；00；00；000；12324；12324；250；2300；］；%具体实现Ct1二zeros(40,1)；%用于存放最终值%先判断只有一个老师上课的课程forn=1:40fornn=n+1:40iflength(Ct(Ct(n,:)~=0))==1ifnn~=nforu=1:3ifCt(n,1)==Ct(nn,u)%判断老师编号相同u1二Ct(n,1)；%获取老师编号a1=n；%获取课程号a2二nn；%获取课程号b1二T(u1,3)-2*C(a1,2)；%计算老师课时与课程课时的差b2二T(u1,3)-2*C(a2,2)；%计算老师课时与课程课时的差ifb1<=b2ifCt1(a1)==0Ct1(a1)二u1；endelseifCt(a2)==0Ct(a2)=u1；endendifCt(n,2)==Ct(nn,u)%判断老师编号相同u1二Ct(n,1)；%获取老师编号a1=n；%获取课程号a2=nn;%获取课程号b1二T(u1,3)-2*C(a1,2);%计算老师课时与课程课时的差b2二T(u1,3)-2*C(a2,2);%计算老师课时与课程课时的差ifb1<=b2ifCt1(a1)==0Ct1(a1)二u1;endelseifCt(a2)==0Ct(a2)=u1;endendendifCt(n,3)==Ct(nn,u)%判断老师编号相同u1二Ct(n,1);%获取老师编号a1=n;%获取课程号a2=nn;%获取课程号b1二T(u1,3)-2*C(a1,2);%计算老师课时与课程课时的差b2二T(u1,3)-2*C(a2,2);%计算老师课时与课程课时的差ifb1<=b2ifCt1(a1)==0Ct1(a1)二u1;endelseifCt(a2)==0Ct(a2)=u1;endendendendendiflength(Ct(Ct(n,:广二0)广二1ifnn~=nforu=1:3ifCt(n,1)==Ct(nn,u)%判断老师编号相同u1二Ct(n,1);%获取老师编号a1=n;%获取课程号a2=nn;%获取课程号b1二T(u1,3)-2*C(a1,2);%计算老师课时与课程课时的差b2二T(u1,3)-2*C(a2,2);%计算老师课时与课程课时的差ifb1<=b2ifCt1(a1)==0endelseifCt(a2)==0Ct(a2)=u1；endendendifCt(n,2)==Ct(nn,u)%判断老师编号相同u1二Ct(n,1)；%获取老师编号a1=n;%获取课程号a2=nn;%获取课程号b1二T(u1,3)-2*C(a1,2);%计算老师课时与课程课时的差b2二T(u1,3)-2*C(a2,2);%计算老师课时与课程课时的差ifb1<=b2ifCt1(a1)==0Ct1(a1)二u1;endelseifCt(a2)==0Ct(a2)=u1;endendendifCt(n,3)==Ct(nn,u)%判断老师编号相同u1二Ct(n,1);%获取老师编号a1=n;%获取课程号a2=nn;%获取课程号b1二T(u1,3)-2*C(a1,2);%计算老师课时与课程课时的差b2二T(u1,3)-2*C(a2,2);%计算老师课时与课程课时的差ifb1<=b2ifCt1(a1)==0Ct1(a1)二u1;endelseifCt(a2)==0Ct(a2)=u1;endendendendendendendendend%T-R-C优化［老师教室］TRC=［110；%1-3218；TOC\o"1-5"\h\z18；2；%6-94；18；18；2；%12-214；18；18；16；8；2；5；5；18；4；%26-2818；18；8；%33-351；5；1513；%38-4012；12；］;%定义时间片%B［周几上课时间段老师一周几节］B二zeros(26,4)；%课程1%课程1B二zeros(10,4,20)；n=1；fora=1:5a1二a；forb=1:2b1二b；forn=n+1:20B(1,:,n)=［a1b112］；breakendendend%课程2n=1；fora=1：5al二a；forb=3：4b1=b；forn=n+1：20B(2,：,n)=[alb122]；breakendendend%课程3n=1;fora=1:5a1二a;forb=3:4b1二b;forn=n+1:20B(3,:,n)=[a1b133];breakendendend%课程6n=1;fora=1:5a1二a;forb=3:4b1二b;forn=n+1:20B(4,:,n)=[a1b162];breakendendend%课程7n=1;fora=1:5a1二a;forb=1:2b1=b；forn=n+1：20B(5,：,n)=[albl42]；breakendendend%课程8n=1;fora=1:5a1二a;forb=1:2b1二b;forn=n+1:20B(6,:,n)=[a1b161];breakendendend%课程9n=1;fora=1:5a1二a;forb=3:4b1二b;forn=n+1:20B(7,:,n)=[a1b152];breakendendend%课程12n=1;fora=1:5a1二a;forb=1:2b1二b;forn=n+1:20B(8,:,n)=[a1b172];breakendendendn=1；fora=1：5al二a；forb=3：4b1=b；forn=n+1：20B(9,：,n)=[alb1103]；breakendendend%课程14n=1;fora=1:5a1二a;forb=1:2b1二b;forn=n+1:20B(10,:,n)=[a1b181];breakendendend%课程15n=1;fora=1:5a1二a;forb=3:4b1二b;forn=n+1:20B(11,:,n)=[a1b192];breakendendend%课程16n=1;fora=1:5a1二a;forb=1:2b1二b;forn=n+1:20B(12,:,n)=[a1b1132];breakendend%课程17n=1；fora=1：5al二a；forb=3：4b1=b；forn=n+1：20B(13,：,n)=[a1b1112];breakendendend%课程18n=1;fora=1:5a1二a;forb=1:2b1二b;forn=n+1:20B