数学建模排课系统(共19页).doc

《数学建模排课系统(共19页).doc》由会员分享，可在线阅读，更多相关《数学建模排课系统(共19页).doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 监制: 数学建模协会 计算机上机课安排摘要本模型用于较为方便的排课，其步骤主要分三个部分。第一部分主要解决那些学生空课特别少的特殊班级，由于此种班级可供选择的空课时间不多，故而最为优先的进行考虑。这一部主要靠人工完成。第二部分也就是本模型的核心部分，用于初步解决余下班级的排课问题。首先将老师和学生的课表转化成相应的0-1分布的形式，然后利用所确定的优先级别，对课表中学生空课状态（记为X1），老师在原任课天内空课情况（记为X2）根据不同时段的空课情况赋予不同的值，以及实验室每个时段的上机占有情况（X3），即可通过参数的大小反应各个空课处优先被安排的程度，然后将老师的课

2、表矩阵与其所教班级的课表矩阵相加，使得学生上午优先、教师指导自己班学生最大化及实验室占有情况同时考虑，找出Y（Y= （X1+ X2 +X3）*e）最大值处的坐标，即为该班级上机实践应该安排在课表中的位置。而将0-1分布的矩阵转化为带有优先级别的矩阵通过Matlab很容易的实现，两个矩阵的相加也可以通过Matlab实现。这一模块将在智能化排课的过程中用到两次。第一次，把老师任课天内可以指导自己所教班级最大限度的排满。然后通过C程序选出需要加天的老师，及具体哪天，使得被选择的那天为所有可选天中，最大化指导学生的那天。关键代码将在附录二中给出。而后再对于还没有排课的班级进行下一轮的排课，这时只需可虑

3、老师所附加来校的那一天。这样就保证老师尽可能多的指导自己所教班级，教师来学校的意义最大化。以上的两轮排序，较为简便并且智能的实现了课表的基本确定。第三部分主要依靠人工完成。此部分主要考虑因第二部分机械排序以后还存在没有排到课的班级，这些班级是那些在老师加天后还无法在这几天中被自己老师指导到的班级，对于这样的班级，只能交给管理员指导。由于这只是极少的一部分，不会给人工排课人员带来很大的工作量。我们优先级别的确定原则：1.通过首次全部用人工进行课表的实际抄做安排所出现的现象，发现学生的空课时间主要集中在下午（见附录一 表1），若不考虑上午优先的话，则所有班级很难安排下去并且会出现下午一定面积的溢出

4、。2.教师优先：如果老师可以带自己所教的班级，那么这种情况也是应该优先考虑的，这来源于问题中提出的硬性要求和实际的教学效果的统计。3.此模型须要人工的地方，虽有两处，但所做工作量都不大；通过此模型建立的课表与全部人工安排的课表在相互检验的时候发现相差不大，故而此模型具有一定的可行性。关键词 智能化排课 优先级别 矩阵转化 人工调整 对照检验目录1问题重述42问题假设43分析及流程图43.1 问题的分析53.2有关构建假设的分析63.3 按优先级排序流程图64模型的建立及求解84.1符号设定84.2优先级别的确定84.3模型的建立及求解84.3.1 模型建立的准备84.3.2模型的组成及构建10

5、4.3.3 实际情况的模型求解145模型的检验156模型的评价166.1模型的优缺点166.2模型的不足及可以改进之处167参考文献（无）168附录17一、问题重述排课是教务运作中的一项重要工作，同时排课问题也是一个复杂的组合优化问题，对此问题的建模和求解，难度都非常大。多数情况下我们只是满足于求解问题的一个可行解，而对此可行解的进一步优化往往通过手工完成，效率很低。在此我们给出一个规模相对较少，约束相对较少的较为简单的排课问题，请同学们加以解决。目前我校的计算机上机课大都安排在计算机学院，计算机学院有5个机房用于学生上机，每个机房大约容纳90人。安排上机的课程共有4门，指导上机的教师共有24

6、人，其中20人为课程的授课教师，其他四人为机房的管理人员，依次为陆老师，章老师，张老师和彭老师，其中陆老师负责2个机房。教师和学生的上机时间不能和他们的授课课程时间冲突，为此我们给出了各位教师和各个班级学生的课程表，见附录二。四名管理人员可全天进行上机指导，但只能在自己负责的机房进行.共有123个班级需要上机本题需要用数学建模方法研究解决排课是教务问题。（1）根据你提出的要求（可以是上述要求的某个或多个，也可以是你自己合理设定的），确定约束条件，给出目标函数，建立数学模型；（2）设法求出满足约束条件的一个可行解，详细给出你的求解步骤；（3）根据你的目标，设计算法，求解问题的一个最优解或近似最优

7、解。二、问题假设1假设机房管理员一周内均可全天参与指导；2假设每个班级一周只安排一次上机且必须安排一次上机；3假设每个机房可以容纳至少两个班级同时上机；4假设每个老师在同一时段只指导一个班级；5假设在同一个机房老师和管理员共同指导自己所教的两个班级；6假设任课老师一定不指导非自己教学的班级；7假设周末和晚上不安排上机；8假设除周末外其他的假期均不考虑。三、分析及流程图3.1 问题的分析排课问题，由于其影响因子较多，并且基于现在的排课制度更多的是在一个可行解（并非比较优化）的基础上，通过手工进行优化，加大手工上调课带来的工作量。而且，由于提供可行解时的一些不合理性，使得人工优化时并没有最大化我们

8、所期望的要求。为了实现优化或者增加可行性，在手工优化的过程中甚至要去改动大量前面已经安排好的课程，每个课程的调动和优化时出现了连锁反应，最终甚至出现死循环，使得人工优化无法继续操作，为了完成排课，也许会出现优化变恶化的小概率现象。并且人毕竟不比机器，当大量需要优化的问题出现且相互影响的出现在他（她）面前时，总会有一些细节（有可能是重要细节）被忽略。这就是人工优化的瓶颈。因此，对于排课问题的研究就是要减小可行解和人工优化之间的差异性，让人工优化是驾驭在可行解之上的优化，而且最好是一次性排好，避免出现回头调课的现象。而对于避免回头调课这样的问题，有如下要求：就是要求系统有前瞻性：把一些特殊时段预先

9、的保留，在最优化其他条件的情况下，对不同班级，不同时段进行分级处理；把一些其他课程更加复杂的班级进行优先占有。从而实现“预留”和“先占”。以上是在排课这一纵项上的大致串行次序，而对于每次排课（即每排一个班），还需要考虑到教师，管理员，实验室等横向维度的并行次序。为此，以上两个较为重要的部分的实现，必须基于一定的“系统优先级别”。以下是基于前几次的手工完整模拟以及统计对优先级别的给定做出相关分析：由于存在课程安排特别紧张的班级（在本研究中，定义为一周空课数小于5的班级），对于这样少数几个班级，因在最前面给予安排，对于他们来说，可以安排到上机就可以了，而若可以遇上自己老师指导那则更好。对于上午排课

10、和教师指导自身班级的优先级的分析（例如：在未加天情况下，老师只有下午7、8节有空，学生上午1、2节，下午7、8节有空）。若是先考虑老师尽可能的能指导到自己的班级，那么就是一切以老师空为主，班级、实验室的情况尽可能去靠向老师这一侧，而通过建模前的样本实排，出现了大面积的溢出，情况远远超出附录一 表1中的现象。因此，从全盘考虑，我们更希望看到的是每个班每周都可以在周一到周五的白天进行上机。这就要求我们必须把上机向上午压缩，空下下午使得一些选择余地较小的班级可以完成每周一次的上机，也就是让那些上午较空的班级做出一定程度上的让步，以此保证了整体教学上理论与实践的结合，用理论指导实践，实践巩固理论。这也

11、是工科类课程的教学核心所在。那么上午下午的优先级别就不言而喻了，显然是上午优先。以上部分将在以下的2.3中通过流程图具体展现。3.2 有关构建假设的分析1.假设一中实验员可全天指导只是一个很宽泛的假设，目的是便于课程的安排。而实际中我们可以考虑让每个实验员一星期内至少有一到两个上午的时间是没有指导任务的。因为上午的课程并没有排满，我们可以通过选择不同的机房，让不同的管理员都有休息的时间。2.假设二中主要考虑的是上机课时能否满足的问题。因为最多的课时为32，而如果每周可以上机一次的话，18周内完全可以满足教学要求，我们可以考虑让上机晚于课堂教学一到两周开始，这样教学效果会更好。3假设三是可以满足

12、的，经我们分析以后，发现单个班级人数平均在40左右，而一个机房可容纳大约90人，完全可以满足要求。4.假设五为我们自行分析构建。由于结合实际，虽然看似老师只指导了一个自己任教的班级，另外一个由管理员负责，但是毕竟是在一个机房，两个班学生还是可以有机会向自己老师提问。这样其实也是从另外一个方面增大了教师指导自己班级的数目。这种间接的指导形式还是普遍存在于我们的教学当中的，并且不失为一个好的安排手法。5假设六由于考虑到每个老师教学模式、进度、风格不尽相同。而且让其他老师带非自己教学的班级还不如让管理员来带。更有一些特殊情况，学生会因为自己感觉自己老师的教学模式不如其他老师，在学习上产生了负面情绪，

13、这我们也有所体会。所以利用假设六，来解决这一问题。6.其余假设显然符合实际要求。再此，不作过多说明。3.3 按优先级排序流程图符号说明：C1：课表中只在下午出现空课或于一周内出现空课数小于五的班级C2：课表中上午出现空课的班级C3：课表中既在上午又在下午有空课的班级总流程人工微调排课完成各种课表的准备第一部分人工选择第二部分程序化排课NY省略号表示对C2、C3执行与C1相同的操作YN对C1进行安排搜索C1是否已安排完对C2进行安排上午优先教师最大化C1、C2、C3均匀已安排完毕检查课表排课完成手动调整开始四、模型的建立及求解4.1 符号设定A；管理员陆老师 B：管理员章老师C：管理员张老师 D

14、：管理员彭老师T01-T20：对二十位老师的编号，与原题附件二中所给的顺序一致MTI:教师课表矩阵（I表示教师编号）MSIJ：学生课表矩阵（其中I、J分别表示教师编号和教师所教班级编号）4.2 优先级别的确定 C1C2C3；A、B、C、D平级。4.3 模型的建立及求解 4.3.1 模型建立的准备模块的形成利用数据库语言将每个班的课表和老师的课表分别导出，并转为以0-1分布形式的矩阵（通过咨询数据库老师，得知这一点可以实现），其中0表示有课，1表示可以排课。班级矩阵：MSIJ 星期一 星期二 星期三 星期四 星期五0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1

15、0 0 （注：每行的第一个数为标记数，0表示未排，1表示已排,总数为123*21的矩阵）教师矩阵：MTI（此时I=01）流程要求1. 当每有一个班排了课，系统或是人工应：在学生的矩阵相应位置赋值为P，表示此天此时上机。并在行首状态区标记为1，表示已排。在教师矩阵相应坐标处赋值机房号（即：a，b，c，d，e）在机房矩阵处赋值MSIJ2. 班级信息只使用一次，即若状态处为1，即上机课已排，不再参与之后任何的参数计算和衡量。教师表和机房表将实时更新，用于后续班级排序的参数依据。3. 在每个班级进行程序化排序时，系统会提供一幅相对应的数字地图，在参数最大的坐标处，即为最佳排课处约束条件的设置依照我们的

16、优先级别，学生空课，教师空余，机房占有情况，分别设置参数，X1，X2，X3。分别表示：X1：学生空课情况。由实际课表上课密集度设置参数值：学生1，2节空，X1=10；学生3，4节空，X1=8；学生5，6节空，X1=4；学生7，8节空，X1=1；X2：教师空课情况。在教师所来天内： 教师1，2节空，X2=9；教师3，4节空，X2=7；教师5，6节空，X2=3；教师7，8节空，X2=2； X3：机房空余情况（同一时段机房空余数为e，0e10，即还有几个班可以插入上机） 机房1，2节空，X3= e*0.01*9；机房3，4节空，X3= e*0.01*8；机房5，6节空，X3= e*0.01*3；机房

17、7，8节空，X3= e*0.01*2；目标函数：Y=（X1+X2+X3）*e设置依据：由于X1X2为必备优先级别，但在实际检验操作以及特殊边缘情况的模拟发现会出现一些相同Y值的区域，这使得系统无法自动做出判断。基于这个原因，我们找出了相同的几个特例及相应Y值相同的区域，寻找不同点，从人的角度去安排课。最终给Y函数再加上一些附加约束使得这些相同值的区域得以区分，保证整个程序化排课的完整性。则对于附加约束X3，必须是小于X1X2的优先级别，即当XX一样时，X3才起作用，而X1X2不同时，X3就被覆盖。因此，选择设置X3的参数至少小于X1X2一位（即X1X2为个位，X3要小于分位）。而对于目标函数中

18、的“*e”，这是为了保证当机房没有空位时，直接致0。再此不影响前面的大小比较，只是整体放大，作为使能，防止程序化排课中，出现溢出的情况。4.3.2模型的组成及构建第一阶段：人工排序人工排序处也并非纯手工进行，首先利用matlab语言把矩阵中所有行分别相加，即可得到每个班每周的可排课数，对于总排课数小于且等于3的班级，输出其行坐标，把这些班级交给人工排序，再在每行的第一个状态处赋值1，排入课的位置赋值为P，表示此班在这个时候上机。在相应老师矩阵上的对应坐标处标赋相应的机房号。第二阶段：系统排序程序化操作流程概述：1. 各矩阵对应参数值的生成2. 对于教师任课天内上机指导的充分安排3. 对于所需加

19、天教师的具体加天安排并在需要加天教师所加天内的充分安排（方法同上）具体操作：一对应参数的设置及生成先设定e矩阵：矩阵中的值通过安排一个递减一个来表示机房课表矩阵中还可容纳的空余量，起始时个空余量均为10. 再设定一个矩阵X3(:,1)=e(:,1).*0.9X3(:,2)=e(:,2).*0.8X3(:,3)=e(:,3).*0.3X3(:,4)=e(:,4).*0.2经以上处理我们将得到：下面先对教师的0、1矩阵进行处理：MT01(:,1)=9*MT01(:,1)；MT01(:2)=7*MT01(:2)；通过该步骤课的如下矩阵：MT01 =9 7 1 09 0 1 19 7 1 19 0 0

20、 19 7 1 1即将老师上午一、二节有空的级别赋值为9和7，然后再通过语句：MT01(:,3)=3*MT01(:,3)；MT01(:,4)=2*MT(:4)；执行后可得到矩阵:即将教师下午一、二有空的优先级别赋值为3和2。此矩阵即为目标函数中的X2。同样的道理，我们可以得到每个班级的课表矩阵，如陈英老师所教班级物理1101班所对应的课表矩阵为:材控1103班的所对应的课表矩阵为:这也是经过相同的赋值语句得到的，只是我们根据优先级别的不同，对学生上午一、二有空赋值为10和8，下午一、二有空赋值为4和1。这样赋值即可将优先级别的不同通过数值的大小反映出来，此矩阵即为目标函数中的X1。下一步我们来

21、做两个矩阵的相加，通过如下语句：B0101=MT01+MS0101+X3和B0103=MT01+MS0103+X3得到老师与学生的课表矩阵以及X3的加和：B0101 =18 15 6 318 8 6 518 15 10 518 8 3 518 15 6 5和B0103 = 18 15 10 2 18 8 10 5 18 23 6 5 18 16 3 5 18 15 6 5上面两个矩阵中用黑体字标出的部分即为可安排上机的最优时间。如B0103中的23所在的位置，同时还应该让23对应于e矩阵中的位置中的元素递减一，即e变为：在这两个矩阵中我们还没有看见矩阵X3发挥出的作用，但在e矩阵逐渐递减以后，

22、X3在确定优先级上将起到重要作用。 事实上我们还可以用matlab语句直接输出最大值所在部分的下标m,v, 参数m表示优先级别最大的数值表示，i表示上机实践应该安排在课表中的位置，如B0103中m，v=15,8，即表示该班级的上机实验可以安排在周三的第二节课。（计算方式为以矩阵的列开始数，一直数到8，所在的位置即为应该安排的位置）但如B0101矩阵中的最大值有五个的情况，我们总是选取第一个来安排。同时在安排一个班级以后，该教师对应的位置就不应该再参与安排，所以需要实时更新教师的课表矩阵，可以通过以下的代码实现：for i=1:1:length(MS) B=MT+MS(:,:,i); m,v=m

23、ax(B(:); a=i,v; MT(i)=0;end设定X3矩阵和对教师矩阵进行更新就避免了每次在相同情况下总选择第一个而造成的溢出（对于极小概率的溢出，第三部分还会处理）。而程序中的MS元胞矩阵可以也是可以通过程序实现的。（以上的详细代码和解释参见附录二 代码1）以上对于排课的操作我们只是举了一例，对于一个老师教有多个班级的情况，我们是可以一次性通过循环语句来完成对矩阵中优先级的赋值和实现老师与学生课表矩阵以及X3的相加的，即一次给出老师所教所有班级的m,v。下面我们解决的问题是关于老师在任课天数内无法安排下所教所有班级的上机实践而需要老师另外单独来一次，专门指导学生上机的情况。 二确定加

24、天教师和具体所加天并在所加天中排课完成了教师所来天内的充分上机安排，则保证了已排课的班级必为任课老师指导。接下来，便是选出所要加天的教师，依据所带上机班级数是否大于所任教班级的一半进行加天老师的选择。而后进行的则是具体加哪天，这一部分所要保证老师所加的那天，尽可能的指导到最多的班级，这样才能让老师来的意义最大化。算法则应保证在所选天内，未排班级之间的空课是相互错开的。这一部分的算法，将在C代码中体现。详细见附录二 代码2在教师指定加天内（若加课，也只为一天），进行最优化排课，再按照上面方法进行进一步排课第二阶段：人工调整主要通过人工解决一些问题。 一种情况，对于还有未排的班级，由于先前已经最大

25、化教师，即剩下的班级在教师所来天内（包括之后的附加天）都无法被自己教师指导到，那么都交给管理员指导，这是很少的一部分。另一种情况是两个班级可以合并在一个机房的情况，如下表：周一第一节A 物理1101（01）B 物理1102注；（）里面的是安排去指导的老师的代号，01即表示陈英。同样，此例也是便于说明而作的假设，实际中不一定存在。如上表中在A机房中知道物理1101班的陈英老师就不可能再去B机房指导物理1102班（题目中有这样的要求），而A、B机房各有一个管理员，完全可以安排物理1102班也去A管理员的机房上机，这样就可把B管理员解放出来，使其有一定的休息时间。4.3.3 实际情况的模型求解第一阶

26、段：由matlab矩阵统计得出一周内空课数小于等于3的班级有如下五个班机工11070，0，0，0，0，0，0，0，0，0，1，1，0，0，0，0，0，0，0，1建艺11010，0，0，0，1，0，0，0，0，0，0，0，0，0，0，0，0，0，0，1建筑11020，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，1，1工业11010，0，0，0，0，0，0，0，0，0，1，1，0，0，0，0，0，0，0，1冶金英才11010，0，0，0，0，0，0，0，0，1，0，0，0，0，0，0，0，0，0，1对于以上五个班，我们的小组人员给予以下安排：第二阶段：系统给出的各班排课坐标

27、通过程序化给出每个班级应该排课的位置，如图中的v所示，m代表最高优先级。 第三阶段：人工优化整合 最终给出的上机安排 见附录一 表2五、模型的检验对于本模型的检验我们给出如下两个标准：机房课表的离散度。离散度数据评价：见附录一 表3离散度图形对比：第一次人工排课离散情况 （柱形高度表示相应时段空课数）本实验提供最优排课的离散情况（柱形高度表示相应时段空课数）由图可知离散度整体有很大的改善教师所指导班级占其任教班级总数的比例。见附录一 表4六、模型的评价6.1 模型的优缺点1本模型实现了程序化排课，并扩大了程序排课的部分，大大减少了人工排课的工作量，并且丝毫未减其合理性及其人性化排课的初衷。2.

28、本模型在现有的条件下，综合分析，利用合理的加天化模式，最大化地实现了“教师尽量指导任教班”，保证了教学质量。3.用此模型排的课表呈现了一定的离散度，使得机房上机不至于过于密集。首先，给管理员一定的休息时间；同时，也给机房的设备维护提供了可能。4.基于这种上课情况，本组给于了上限阀值：此方法适用于同样平均情况的班级数不能超过150个。为今后排课的初期预测提供了帮助6.2 模型的不足及可以改进之处1考虑上午让管理员有半天休息的时间，即各个管理员上午从周一到周五轮流值班（安排不同的机房以实现）2可以考虑让任课天内的老师指导非自己所教的班级。首先，可以让老师有更多的时间来搞科研或者休息。其次，不同老师

29、有不同的侧重，有的老师偏重于理论，有的则在实践方面比较出色。这就要求排课时有一定的偏好设置，这一点是机械化排课无法做到的3对于所给出的最优方案（附录一 表2），星期二上午处有四个班上机，却开了4个机房，这样就浪费了机房的资源。这里需要人工协调，把四个管理员集中到两个机房进行指导。七、参考文献（无）附录一表1：表2表3表4附录二 代码1代码2#includevoid main()int f,k,numb,tot,i;int b5=0,0,0,0,0;int teacher54=0,0,0,0,1,1,0,1,0,0,0,0,1,0,1,1,0,0,0,0;/*某教师上课情况0为空课*/int c

30、lasses1220=1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,0,1,1,1,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0;/*某班级情况，这里为两个班*/printf(n请输入教师所教班级未排数，numb:);scanf(%d,&numb);printf(n请输入教师所总教班数，tot:);scanf(%d,&tot);if(numb*2tot)/*/printf(“此教师符合要求无需加天”)for(i=0;i5;i+) /*统计还未排课班级的空课错开情况*/for(k=0;knumb;k+)for(f=0;f4;f+)if(teacherif=0 & classeskf+4*i=0)bi=bi+1;for(i=0;i5;i+)printf(n此教师需要加天，请取最大值那天 星期%d=%dn,i+1,bi); /*输出周一到周五每天的值*/专心-专注-专业