数学建模排课系统

监制:数学建模协会计算机上机课安排摘要本模型用于较为方便的排课，其步骤主要分三个部分。第一部分主要解决那些学生空课特别少的特殊班级，由于此种班级可供选择的空课时间不多，故而最为优先的进行考虑。这一部主要靠人工完成。第二部分也就是本模型的核心部分，用于初步解决余下班级的排课问题。首先将老师和学生的课表转化成相应的0-1分布的形式，然后利用所确定的优先级别，对课表中学生空课状态（记为X1），老师在原任课天内空课情况（记为X2）根据不同时段的空课情况赋予不同的值，以及实验室每个时段的上机占有情况（X3），即可通过参数的大小反应各个空课处优先被安排的程度，然后将老师的课表矩阵与其所教班级的课表矩阵相加，使得学生上午优先、教师指导自己班学生最大化及实验室占有情况同时考虑，找出Y（Y=（X1+X2+X3）*e）最大值处的坐标，即为该班级上机实践应该安排在课表中的位置。而将0-1分布的矩阵转化为带有优先级别的矩阵通过Matlab很容易的实现，两个矩阵的相加也可以通过Matlab实现。这一模块将在智能化排课的过程中用到两次。第一次，把老师任课天内可以指导自己所教班级最大限度的排满。然后通过C程序选出需要加天的老师，及具体哪天，使得被选择的那天为所有可选天中，最大化指导学生的那天。关键代码将在附录二中给出。而后再对于还没有排课的班级进行下一轮的排课，这时只需可虑老师所附加来校的那一天。这样就保证老师尽可能多的指导自己所教班级，教师来学校的意义最大化。以上的两轮排序，较为简便并且智能的实现了课表的基本确定。第三部分主要依靠人工完成。此部分主要考虑因第二部分机械排序以后还存在没有排到课的班级，这些班级是那些在老师加天后还无法在这几天中被自己老师指导到的班级，对于这样的班级，只能交给管理员指导。由于这只是极少的一部分，不会给人工排课人员带来很大的工作量。我们优先级别的确定原则：1.通过首次全部用人工进行课表的实际抄做安排所出现的现象，发现学生的空课时间主要集中在下午（见附录一表1），若不考虑上午优先的话，则所有班级很难安排下去并且会出现下午一定面积的溢出。2.教师优先：如果老师可以带自己所教的班级，那么这种情况也是应该优先考虑的，这来源于问题中提出的硬性要求和实际的教学效果的统计。3.此模型须要人工的地方，虽有两处，但所做工作量都不大；通过此模型建立的课表与全部人工安排的课表在相互检验的时候发现相差不大，故而此模型具有一定的可行性。关键词智能化排课优先级别矩阵转化人工调整对照检验创新意识、团队精神、重在参与、公平竞争2目录1问题重述·····································42问题假设·········································43分析及流程图·····································43.1问题的分析·····································53.2有关构建假设的分析·······························63.3按优先级排序流程图······························64模型的建立及求解································84.1符号设定·································84.2优先级别的确定·····························84.3模型的建立及求解··························84.3.1模型建立的准备······················84.3.2模型的组成及构建···························104.3.3实际情况的模型求解·······················145模型的检验···································156模型的评价·····································166.1模型的优缺点················································166.2模型的不足及可以改进之处····································167参考文献（无）··········································168附录·········································17创新意识、团队精神、重在参与、公平竞争3一、问题重述排课是教务运作中的一项重要工作，同时排课问题也是一个复杂的组合优化问题，对此问题的建模和求解，难度都非常大。多数情况下我们只是满足于求解问题的一个可行解，而对此可行解的进一步优化往往通过手工完成，效率很低。在此我们给出一个规模相对较少，约束相对较少的较为简单的排课问题，请同学们加以解决。目前我校的计算机上机课大都安排在计算机学院，计算机学院有5个机房用于学生上机，每个机房大约容纳90人。安排上机的课程共有4门，指导上机的教师共有24人，其中20人为课程的授课教师，其他四人为机房的管理人员，依次为陆老师，章老师，张老师和彭老师，其中陆老师负责2个机房。教师和学生的上机时间不能和他们的授课课程时间冲突，为此我们给出了各位教师和各个班级学生的课程表，见附录二。四名管理人员可全天进行上机指导，但只能在自己负责的机房进行.共有123个班级需要上机本题需要用数学建模方法研究解决排课是教务问题。（1）根据你提出的要求（可以是上述要求的某个或多个，也可以是你自己合理设定的），确定约束条件，给出目标函数，建立数学模型；（2）设法求出满足约束条件的一个可行解，详细给出你的求解步骤；（3）根据你的目标，设计算法，求解问题的一个最优解或近似最优解。二、问题假设1．假设机房管理员一周内均可全天参与指导；2．假设每个班级一周只安排一次上机且必须安排一次上机；3．假设每个机房可以容纳至少两个班级同时上机；4．假设每个老师在同一时段只指导一个班级；5．假设在同一个机房老师和管理员共同指导自己所教的两个班级；6．假设任课老师一定不指导非自己教学的班级；7．假设周末和晚上不安排上机；8．假设除周末外其他的假期均不考虑。三、分析及流程图3.1问题的分析创新意识、团队精神、重在参与、公平竞争4排课问题，由于其影响因子较多，并且基于现在的排课制度更多的是在一个可行解（并非比较优化）的基础上，通过手工进行优化，加大手工上调课带来的工作量。而且，由于提供可行解时的一些不合理性，使得人工优化时并没有最大化我们所期望的要求。为了实现优化或者增加可行性，在手工优化的过程中甚至要去改动大量前面已经安排好的课程，每个课程的调动和优化时出现了连锁反应，最终甚至出现死循环，使得人工优化无法继续操作，为了完成排课，也许会出现优化变恶化的小概率现象。并且人毕竟不比机器，当大量需要优化的问题出现且相互影响的出现在他（她）面前时，总会有一些细节（有可能是重要细节）被忽略。这就是人工优化的瓶颈。因此，对于排课问题的研究就是要减小可行解和人工优化之间的差异性，让人工优化是驾驭在可行解之上的优化，而且最好是一次性排好，避免出现回头调课的现象。而对于避免回头调课这样的问题，有如下要求：○1就是要求系统有前瞻性：把一些特殊时段预先的保留，在最优化其他条件的情况下，对不同班级，不同时段进行分级处理；把一些其他课程更加复杂的班级进行优先占有。从而实现“预留”和“先占”。○2以上是在排课这一纵项上的大致串行次序，而对于每次排课（即每排一个班），还需要考虑到教师，管理员，实验室等横向维度的并行次序。为此，以上两个较为重要的部分的实现，必须基于一定的“系统优先级别”。以下是基于前几次的手工完整模拟以及统计对优先级别的给定做出相关分析：○1由于存在课程安排特别紧张的班级（在本研究中，定义为一周空课数小于5的班级），对于这样少数几个班级，因在最前面给予安排，对于他们来说，可以安排到上机就可以了，而若可以遇上自己老师指导那则更好。○2对于上午排课和教师指导自身班级的优先级的分析（例如：在未加天情况下，老师只有下午7、8节有空，学生上午1、2节，下午7、8节有空）。若是先考虑老师尽可能的能指导到自己的班级，那么就是一切以老师空为主，班级、实验室的情况尽可能去靠向老师这一侧，而通过建模前的样本实排，出现了大面积的溢出，情况远远超出附录一表1中的现象。因此，从全盘考虑，我们更希望看到的是每个班每周都可以在周一到周五的白天进行上机。这就要求我们必须把上机向上午压缩，空下下午使得一些选择余地较小的班级可以完成每周一次的上机，也就是让那些上午较空的班级做出一定程度上的让步，以此保证了整体教学上理论与实践的结合，用理论指导实践，实践巩固理论。这也是工科类课程的教学核心所在。○3那么上午下午的优先级别就不言而喻了，显然是上午优先。以上部分将在以下的2.3中通过流程图具体展现。3.2有关构建假设的分析1.假设一中实验员可全天指导只是一个很宽泛的假设，目的是便于课程的安排。而实际中我们可以考虑让每个实验员一星期内至少有一到两个上午的时间是没有指导任务的。因为上午的课程并没有排满，我们可以通过选择不同的机房，让不同的管理员都有休息的时间。2.假设二中主要考虑的是上机课时能否满足的问题。因为最多的课时为32，而如果每周可以上机一次的话，18周内完全可以满足教学要求，我们可以考虑让创新意识、团队精神、重在参与、公平竞争5上机晚于课堂教学一到两周开始，这样教学效果会更好。3．假设三是可以满足的，经我们分析以后，发现单个班级人数平均在40左右，而一个机房可容纳大约90人，完全可以满足要求。4.假设五为我们自行分析构建。由于结合实际，虽然看似老师只指导了一个自己任教的班级，另外一个由管理员负责，但是毕竟是在一个机房，两个班学生还是可以有机会向自己老师提问。这样其实也是从另外一个方面增大了教师指导自己班级的数目。这种间接的指导形式还是普遍存在于我们的教学当中的，并且不失为一个好的安排手法。5．假设六由于考虑到每个老师教学模式、进度、风格不尽相同。而且让其他老师带非自己教学的班级还不如让管理员来带。更有一些特殊情况，学生会因为自己感觉自己老师的教学模式不如其他老师，在学习上产生了负面情绪，这我们也有所体会。所以利用假设六，来解决这一问题。6.其余假设显然符合实际要求。再此，不作过多说明。3.3按优先级排序流程图符号说明：C1：课表中只在下午出现空课或于一周内出现空课数小于五的班级C2：课表中上午出现空课的班级C3：课表中既在上午又在下午有空课的班级总流程创新意识、团队精神、重在参与、公平竞争6人工微调排课完成各种课表的准备第一部分人工选择第二部分程序化排课创新意识、团队精神、重在参与、公平竞争7NY省略号表示对C2、C3执行与C1相同的操作YN……对C1进行安排搜索C1是否已安排完对C2进行安排上午优先教师最大化C1、C2、C3均匀已安排完毕检查课表排课完成手动调整开始创新意识、团队精神、重在参与、公平竞争8四、模型的建立及求解4.1符号设定A；管理员陆老师B：管理员章老师C：管理员张老师D：管理员彭老师T01-T20：对二十位老师的编号，与原题附件二中所给的顺序一致MTI:教师课表矩阵（I表示教师编号）MSIJ：学生课表矩阵（其中I、J分别表示教师编号和教师所教班级编号）4.2优先级别的确定C1C2C3；A、B、C、D平级。4.3模型的建立及求解4.3.1模型建立的准备模块的形成利用数据库语言将每个班的课表和老师的课表分别导出，并转为以0-1分布形式的矩阵（通过咨询数据库老师，得知这一点可以实现），其中0表示有课，1表示可以排课。○1班级矩阵：MSIJ星期一星期二星期三星期四星期五0000010010110001100110·······0·············（注：每行的第一个数为标记数，0表示未排，1表示已排,总数为123*