课表编排问题

魅力数模美丽力建力建学院第六届数学建模竞赛自信坚强团结创新论文题目A题：课表编排问题参赛编号 2009tm0502监 制：力建学院团委 数学建模协会（2010年11月）力建学院第六届数学建模竞赛承诺书我们仔细阅读了第六届建工数学建模竟赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以 外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到 的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意 承担由此引起的一切后果。我们的参赛编号为：2009tm0502参赛队员（签名）：队员1：李超队员2：王超队员3：秦允皓A题：课表编排问题摘要在学校的教务管理工作中，课程表的编排是一项十分复杂、棘手的工作。排课需要考虑时间、课程、 教学区域、教室、院系、班级、教师等因素。我们经过讨论后，对题目的要求进行分析，并认为可以规划 为优化问题，可以将“教师” “教室”“课程”作为优化因素讨论，以便分配到不同的时间段上，形成课表。 首先，确定各优化因素之间的约束关系，根据各因素间约束关系的不同，将多重约束条件分为硬约束（强 制要求）和软约束（用偏好系数表示），编制出各因素间的效用矩阵。其次，把课程随机分配到课表上的每 一个时间段，再以01规划方法分别将教师、教室分配到课表上的不同时间段上。形成时间+课程+教师+教 室的组合。最终，形成满足要求的课表。我们优化、01规划的方法，加入多重约束条件，引入了偏好系 数，形成排课模型，根据题目给的数据，通过计算机编程，进行模型验证，求出了所需课表。最后给出了 教师、教室的配置建议。【关键词】：优化因素排课模型多重约束条件0-1规划1问题的重述在学校的教务管理工作中，课程表的编排是一项十分复杂、棘手的工作。排课需要考虑时间、课程、 教学区域、教室、院系、班级、教师等等因素。经优化的排课，可以在任意一段时间内，教师不冲突，授 课不冲突，授课的班级不冲突，教室占用不冲突，且综合衡量全校课表在宏观上是合理的。如何利用有限 的师资力量和有限教学资源，排出一个合理的课程安排结果，对稳定教学秩序、提高教学质量有着积极的 意义。某高校现有课程40门，编号为C01C40；教师共有25名，编号为T01T25；教室18间，编号为R01 R18。具体属性及要求见表1，表2，表3：课表编排规则：每周以5天为单位进行编排；每天最多只能编排8节课，上午4节，下午4节，特殊情况 下可以编排10节课，每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。你所要解决的问题：请你结合实际情况给出较为合理的课表编排方案，分析你所给出的方案的合理性。对教师聘用，教室配置给出合理化建议。2问题的假设 假设课程全部编排； 假设是学生自选课程； 假设在课程要求为强制要求（硬约束）； 假设在教师属性中，能胜任课程类别、周最大课时数为强制要求（硬约束）；对教室类别要求、上课时间 要求用偏好程度衡量（软约束）； 假设所得4张课表中2张同时上课，上完后另外2张课表开始上课； 假设课表内容由上课时间、教师、教室、课程组成。3符号说明主要符号A1A2A3A4A5TiRiCiaSiSTSCiSi=Yij,T，R符号意义效用矩阵教师编号教室编号课程编号偏好系数，表示教师对教室、教师对上课时间的偏好系数。课程表上时间段的编号为T一教师的要求课时数为Ci课程的要求课时数课程表上某一时间段的课程-教师-教室组合5模型准备根据关联关系，刻画每个关系的效果指标矩阵上课时间一共五根据分析，关联关系有教师一教室、教师一课程、教师一上课时间、课程一教室、课程 个。图1关联关系示意图（实线表示“硬约束”，虚线表示“软约束”）依次建立A1,A2A4七个效用矩阵。其中，为强制约束的有A2、A4。A2矩阵：A2（aij）（刻画i教师上j课程时的效果指标）其中：aij 0,1A4矩阵：A4（aij）（刻画i课程在j教室上时的效果指标）其中：aij 0,1偏好约束有A1、A3。A1矩阵A1（aij）（刻画i教师上j教室的偏好效果指标）其中：0 aij 1A3矩阵A3（aij）（刻画i教师上j时间段上课时的偏好效果指标）其中：0 aij 1时间段Si的编号每一张课表上有星期一到星期五，每天有4个时间段（每两个课时算一个时间段）。根据假设，假设题目需要同时排四张课程表，需要对四张课程表上的时间段都进行编号星期一 星期五星期一 星期五星期五上午1、2 节 s1 s5 s6 s10 s20上午3、4 节 s21 s25 s26 s30 s40下午5、6 节 s41 s45 s46 s50 s60下午7、8 节 s61 s65 s66 s70 s80表1时间段编号对课程的处理当某一课程的课时数为奇数时，取大于他的最小偶数。对所有课程的课时数进行调整。新的课时数为Ki (1=1,2-40，即为40位教师)，原课程编号为Ci (i=1,240),Yij (i表示原课程的编号，j =1,2(k1+k2+-+ki) /2)，待排课程集合为Yij教师的课时数为。课程的课时数为。STi(k=1.2.25) SCi(i=1.2.40)6模型的建立与求解6.1模型的建立6.1. 1随机分配课程到各个时间段当课程的上课时间(上下午)要求为强制性约束时，分别选出上下午的课程集合B上午二Y11-Yij，B下午二Y21-Yij。我们随机给中的每一个元素抽取一个上午的时间段，其中满 足的条件是，给中的每一个元素抽取一个下午的时间段。组成时间段一课程(SiYij)组合。此时，Si= Yij (某一时间段对应的某一课程)。6.1.2给每一个时间段安排教师6.1.2.1结合教师、课程的Si根据教师Tk对课程Cj的效用矩阵A2,对i s进行第二次赋值。当第i个时间段上的初值是Yij，若aij=1,则Si =1,否则，Si =0。6.1.2.2结合效用矩阵A3的Si根据教师Tk对上课时间的偏好A3矩阵，对i s进行第三次赋值，Si=Si -aij。6.1.2.3结合效用矩阵A1的Si根据教师Tk对s/寸间段上的课程所要求的教室的偏好A1矩阵，对七 进行第四次赋值，s.= s.-aijo最终得到S1I 冏s =k Ji . 1li 4 chJi XSul 知i jS：T：SliS12Si：iT?S21中申 e4 4 4 P -V *串 * 中申. I* -TvSkiSkw*TSk i表2九教师对Si时间段的效用指标6.1.2.4 0-1 规划目标是将 丁善师分配到不同的时间段上，约束条件是分配结果必须满足教师的课时数要求。因此，问题 转化为求有约束条件的0-1规划问题。目标函数：n nmax Z = ZZ ski x xki约束条件:k=i i=i私=$。/2*=1所得解为:将教师安排到最优的时间段，此时Si=Yij,Ti,Ri。若无最优解，重回6.1.1。6.1.3为每一个时间段安排教室Ri教室对Si这一时间段的效果指标：（1）该时间段的老师对教室的偏好（2） 该时间段课程对教室的效果指标6.1.3.1结合效用矩阵A4的Si根据S|时段课程Ci对教室Ru的效果矩阵 A4,对s进行第一次赋值，若aij=1,则s =1,否则，s=0。iii6.1.3.2结合效用矩阵A1的Si根据，寸段教师Ti对教室Ru的效用矩阵A1，对s】进行第二次赋值， SjSj-aij。最终得到：S = 15ull SllTj S .RiSi:SJ2BaB*gjSai珥- Hi II. - - ,： ! II，-、v v !r !r Rc .早UJill表3 R,教室对S：时间段兼用指标6.1.3.30-1 规划目标是将 Ru教师分配到不同的时间段上，约束条件是分配结果必须满足同一 间教室在四张课表的同一时间段不重复。因此，问题转化为求有约束条件的0-1 规划问题。目标函数：n nmax Z 空 5u. x %u.u 1 Z=1约束条件：X + Xll + Xl6 = 1X2 + X2()+ X31 + *36 = 1X4I + XA6 + Xl + 工帝=1-Xii：所得解为：Ji lX2 XiX21.*X22i.X2i,1Xu 2 Xui j将教室安排到最优的时间段，此时sYjk,Ti,Ri 。若无最优解，重回6.1.1。6.1.4安排课程表将每个、的组合按照其编号读入到表1中，得到最后的课程表。6.2模型的求解6.2.1为时间段编号并随机分配课程充分考虑课程的时间要求（上午或下午），随机分配课程，得到“时间段-课程” 组合。分配示例见附录一。由于，题目所给数据中，教师的总课时数小于课程总课时数，又经过计算，设定 目标是为做成四张课表，其中两张先行开课，上完后，另外两张课表再开课。利 用0-1规划求解，构造要用矩阵时，要考虑的是，教师对这一事件的偏好，教 师对这一试点的课程的效用两个因素，利用excel构造出效用矩阵。lingo编 程计算。程序代码见附录二。6.2.2分配教师结合效用矩阵，为每个“时间段-课程”组合分配教师，得到“时间段-课程-教 师”组合。6.2.3分配教室结合效用矩阵，为每个“时间段-课程-教师”组合分配教室，得到“时间段-课 程教师-教室”的最优组合，从而得到所求课程表。课程表见附录三 6.2.3编排课表将获得的时间段编号+课程+教师+教室的组合编制成课表，编制结果参看附录。 其中，第一、二张课表同时开课，上完后，第三、四张课表开课。7模型的检验与分析7.1模型的检验（偏好系数a的检验a =1时，课表中教师所上课程满足其对时间、教室类别的要求。当a =0时， 课表中教师所上课程完全不满足其对时间、教室类别的要求。另外，当教师和教 室的偏好度越大时，0-1规划得到的效用最小，例如当偏好系数为0.1时，效 用只有38.2,当偏好系数为0时，为最大效用40。可以见得，取极限，当偏 好度为1时，无解。所以，我们的模型能较大程度地满足教师、课程和教室的 要求，给出最终符合条件的课表。7.2模型的分析7.2.1合理性分析模型充分考虑了课程、教室、教师等的相互约束，建立了关系关联，并对约束采 用0-1规划，确定出“时间段-课程-教师-教室”组合。同时，我们也充分考虑了教师对教室和上课时间的偏好，建立了一个偏好系数可调的模型，使所得课 表尽量满足课程、教室、教师的各种属性及要求，对教师聘用，教室配置给出合 理化建议。但是，当四张课表一起开课时，无法达到教师的学时要求，即四张课 表总需要周学时数为160，但教师所能提供的只有116学时。计算机模拟表示， 没有最优解。于是，我们做出以下调整：将题目简化为两张课表一同开课，待到 上完课程后，再开另外两张课表。7.2.2几种特殊情况的处理1. 在模型准备的对课程的课时数的处理中，将奇数课时的处理成偶数，以便计算。 在最终课表中，对排好的课表进行调动，奇数课时课程只上其要求的课时数，即 找到课程所在时间段，随机取消一节课。2. 如果所给课程的总课时数（取偶后的总和）大于教师的总课时数，则按照教师 的课时数取n个课表，且n个课表同时开课。3. 如果所给课程的总课时数（取偶后的总和）小于或等于教师的总课时数，则将 课程安排到n个课表中，且n个课表同时开课。8模型的评价8.1模型的优点1. 引入了偏好系数a，能较大程度地满足教师、课程和教室的要求；2. 建立了关联关系，使模型建立更清晰、明确、具有条理性；3. 用0-1规划解决相互约束问题，形成“时间段-课程-教师-教室”组合，科学 合理；4. 逐步优化，层层递进，思路清晰，简单易懂。5. 充分考虑各个教师、教室、课程的要求，具有良好实用性。8.2模型的缺点1. 当课时数为奇数时，将其近似为偶数计算，导致课表中所有时间未能充分利用；2. 在随机给每个时间段安排课程时，未能确立完善的分配方式；9参考文献(1) 韩中庚，数学建模方法与应用，北京：高等教育出版社，2005。(2) 张小红、张建勋，数学软件与数学实验，北京：清华大学出版社，2004。附录附录程序代码：model:sets:teacher/ fil e(偏好0.1 .txt) /:teacheryaoqiu;kecheng/ file(偏好0.1 .txt) /:kechengyaoqiu;links(teacher,kecheng):c,x;endsetsdata:teacheryaoqiu=file (偏好0.1.txt);kechengyaoqiu=file (偏好0.1 .txt);c=file (偏好0.1.txt);enddatamax=sum(links:c*x);for(kecheng(j):sum(teacher(i): x(i,j)二kechengyaoqiu(j);for(teacher(i):sum(kecheng(j): x(i,j)=teacheryaoqiu(i);for(links:bin(x);End附录二所得四张课程表时间 项目 星期一星期二 星期二 星期四 星期五acT第一节 鞍怵T羸T：fiLrLi教室R山R做RU赢血Q aR. .2 c- LRU 7 S 2 匚T:R, 血 QTM 程帅堂J. EII. cr:乱cl;程师堂煤款款CiCjlC iT01T.-T：cRciRuiRueCmT皓Rua课程G第叫节教师T.教室R山课程C：第五节救师金教室褊CfiTm匾C：第六节C:艺程帅堂深程ClGGctd第七节教师 邕 羸孩 L.救窒RlsjR 皿RmRuaRua第八节:血C:金福 程师室时间质目星期一星期二星期三星期四星期五课程CmC.tiCi-CluKt-M-*第一 F教师T”L，inTL0Tu!S*caiCaoK A 1 1 L第一 1教师TfltLiTioJotTn救室E?i2RUiR站Rii课程CaTCmcaiCgCar第二节教FaaTsa1 2.MLi教室E?i2也甚Rl2Rii课程毒C-J4caiCjCm第四节教师TuaTahlT们漏教堂RliRo.如Rl2Rii课程Ca2方以CamC如第五节教师港TaTea以T”救室RlORioR：aRl2Rii课程Cs2CmCamCm第六节教师T如1x2血Taa教室RlflRioRjaR|Rii课程Csh方CssCabCm第七节教师TatImLT皿Li教室RiaRiohRlSR课程Cau方Ci!CabCm第八节教师TaiImL%Li教室RiaRioh%第四张诀程表