高校排课方案简单方法

《高校排课方案简单方法》由会员分享，可在线阅读，更多相关《高校排课方案简单方法（19页珍藏版）》请在装配图网上搜索。

1、承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮 件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问 题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他 公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反 竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：_B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整

2、的全名）：中南民族大学参赛队员（打印并签名）：1.2.3.指导教师或指导教师组负责人（打印并签名）：日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：课堂教学时间表的制定摘要本文是针对学校食堂拥挤，排课不完善等实际情况，来研究并确定一个比较 好的排课方案,用以解决包括食堂拥挤一系列的问题。给出了在符合实际情况的 假设下，重点研究了 3 个比较关键的因素:食堂拥挤度,教室利用率,单个教室利 用率，并对这3 个因素建

3、立了多目标的 0-1 规划模型。整个建模过程分为三步。第一步是产生随机课表，在此我们分步采用蒙特卡 洛模拟技术(随机模拟)，随机产生再派生了多张课表，并且分课程优先级和课时 段优先级把课表安排完成；第二步是根据第一步中所排出的课表建立多目标 0-1 规划模型，由于多目标问题比较难以解决，于是我们就采用移动加权平均值的方 法构建了综合评价函数，将多目标问题转化为单目标的线性规划问题，各因子间 的权重采用层次分析法得到，通过了一致性检验，权重向量为：(w w w )= (0.6870 0.1865 0.1265)；第三步是根据第二步的模型求解目标123函数数和各因子的值，本题中的值为：f = 0.

4、06055，耳=12.2%弭=25.0%,耳=18.46%再结合实际情况进行分析知：据统123计一般食堂拥挤度在 20%以上时，学生会觉得拥挤，本题中我们的解耳=12.2%下午的课（2堂） 晚上的课（1堂）。2. 课程性质优先级：必修 选修；专业 基础公共课；基础选修课 公选必修。3. 由于英语课的特殊性（小班上课，专用教室），我们将它独立出来，与其它六 门课并列，又由于四六级考试，在此定为英语最重要，即优先级最高。4. 由于题目中未给出老师的任何信息，我们默认为老师的资源足够。5. 假设教室有三种属性：大教室20个（一次可上4个班），中等教室130个（一 次最多可上 2 个班），小教室 50

5、 个（一次最多上一个班）。6. 假设每个年级有 120 个班，每班 50 人，可大概将其分为六大类，每类 20 个班 级，其课程性质及数目基本一致，故可共用一张课表。7. 由于大四学生在校上课人数实际上很少，所以我们的排课上基本忽略大四学生对我们目标的影响。几个原则：1. 默认教师属性与课程属性对应，如英语课用小教室，选修课和公共必修课 用大教室，其它必修课用中等教室。2. 同一时间上课所占用的教室数不可多于可用的教室数。3根据学校的实际情况：大一只开设了： S S S S （已排好优先级）； 0124大二开设立： S S S S S S ； 031456 大三只开设了： S S 。354.

6、同一天内不可排2堂及以上相同的课程，这里的相同指同性质的同一门课 程。5. 从食堂的拥挤度和时间段的优先级考虑，公共课最好放在35 堂上。 6课程连上时，尽量不要换教室，即使换也不要隔太远三 符号说明14 i = 11.设第i个年级每周的平均课时数S = 15 i = 2 i12 i = 32在一周内设第i个年级第j天第k个课堂上课的情况为A，则ijk1上课A = ijk 0不上课1 i 3;1 j 5;1 k 25（k为按先行后列的顺序对一周内25堂课进行的编号）20 m = 13设第m类教室有B个，则B =130 m = 2 mm50m = 34. 设S为课程的编号，S为S的第a门课程 n

7、 na n0 n 6, n g N*S :英语；S :基础必修课（简称基必）；S :基础选修课（简称基选）； 0 1 2S :专业必修课（简称专必）； S :公共必修课（简称公必）； 34S : 专业选修课（简称专选）； S : 公共选修课（简称公选） 565. N为第i个年级的Sinn6. 设耳表示中午食堂的拥挤度，耳表示教室的利用率，12耳表示单个教室的利用率；w分别为其权重（l =1,2,3） 3l四 问题分析高校排课问题要考虑很多因素，现在大部分的高校依然采用机械加手动的方 式去解决问题，这样就无可避免的产生了各类问题，比如题目中所叙述的选课冲 突、教室利用率过低，教室设备维修不方便等

8、问题。本文在结合我校实际情况后建立了多目标决策模型，采用计算机模拟，层次 分析等方法确定了一个比较完善的排课方案具体思路分为三步：第一步 产生随机课表 根据我校的实际情况，我们对个年级分别排课，大一大二大三每周上课的平 均次数分别为14,15,12堂（两小节课为一堂，晚上只安排一堂课），每周学校安 排25堂课，据此，可以通过matlab编程随机产生一系列符合该初始条件的上课 时间点，得到初级课表；再根据所确立的优先级原则，结合计算机模拟，在时间 点上排上相应的课程，得到次级课表；最后按教室类型为课堂安排教室，随机分 配，此时得到的课表为还未进行优化的原始课表。第二步 由产生的课表建立 0-1

9、多目标规划模型，构建课表的综合评价函数 在第一步的基础上我们再根据题目要求建立 0-1多目标决策模型，对题目出 的六个因素进行排序，选出其中三个比较重要的因素，并引入各自的权重（层次 分析法）建立一个课表的综合评价指标函数 f ,作为我们的优化模型，最后将排 好的课表根据我们的多目标决策模型的 f 函数和各因素产生的原因微调，比较各 自的 f 值，当 f 取值比较合理时就认为我们的次级课表已经排好了；根据实际情况，我们学校的教室比较多，利用率不高，于是在次级课表的基 础上我们继续采用计算机模拟，按课堂性质的要求将教室分配好，接着根据我们 之前设定的几个原则，对排好的教室进行微调，最后我们就可以

10、得到全校大一大 二大三的三张课表 第三步 对综合评价函数进行求解分析，回代到课表再优化之前随机产生的课表只要每次产生了课表就会有一个对应的最佳f值，每一个f值都会对应一组 因素值（如耳，耳，耳），每次在解出一组值时都做分析，当我们的因素值和综合评价 123 值都比较合理时就认为课表已经在题目中的约束条件下排好了。如下图就是我们整个分析的循环简略图否五 模型建立与求解5.1 步骤一 产生初级课表（只含上课时间）首先，我们结合实际情况，对各年级的课程情况进行估算，得到以下数据表 表 5.1.1 各年级课程情况数据表S0S1S2S3S4S5S6大一2 x N102 x N111X N121 x N1

11、4大二2 x N201X N212 x N231 x1 x N251 x N26大三2 x N332 x N35其中，除N =4, N =3, N =2, N =4, N =3, N =4, N =2 外，其余N =0。11 14 23 24 26 33 35 in接着,我们利用计算机模拟的方法,随机产生了大一,大二,大三的各一张初级课表（见表 5.1.2）：周周周周 四周 五一10110二00110三11001四01110五11001大一 表 5.1.2a周周周周 四周 五一10111二11000三11001四01000五11111大二 表 5.1.2b周周周周 四周 五一01000二100

12、01三00011四11011五00111大三 表 5.1.2c然后,再分时间段（为了保证同类课表的同时间段内课堂数相等）进行计算 机模拟,分别得到各年级的另外 5 张平行课表,故现有 3 6=18 张初级课表。5.2 步骤二 产生次级课表（含有上课时间和相应课程）在初级课表的基础上,按照课程性质和上课时间段的优先级,在上课时间段 上安排合适的课程,由于有18 张课表需要排,工作量较大,这里,我们只给出 排课方法和一个排课结果,依次类推可排出其它17 张次级课表,具体排课方式如下：（以大一第一类班级,即表 5.1.2a 为例）图一过程表示将S的2堂课随机排入上午5堂课，故上午剩余3堂课；0过程表

13、示在S中随机选3堂课随机排入上午剩余的3堂课中；1过程表示将S中剩余的5堂课随机排入下午的6堂课中，故下午剩余11堂课；过程表示将S的1堂课排入下午剩余的1堂课中；2过程表示将S的3堂课随机排入晚上的3堂课中。4 此次排课过程中，每当出现与原则 4 相违背的情况时，即对课表进行微调至 符合。由此得到的次级课表为：（见表5.2.1）表 5.2.1 大一第一类班级次级课表周一周二周三周四周五一S0S0S11二S11S12三S12S13S13四S14S2S14五S43S41S425.3 步骤三 产生原始课表（含有上课时间，课程及教室）首先将所有教室按类型进行编号：20 个大教室分别编号为： C C

14、;1 201 3 0个中等教室分别编号为： D D1 13050个英语小教室分别编号为： E E 。1 50接着，再按照原则 1，在 18 张次级课表的基础上，将同一时间段同种教室上 课的课程，随机分配在相应的教室类型中，由于各个类型教室硬件设施没有差别， 故教室可以按原则 1 随机安排，在此就不具体列出了至此，我们的 18 张课表已经全部排完。步骤四 优化课表模型 以上课表只是我们根据实际情况及一些基本原则随机排出的，并未考虑到题 目的要求，因此，接下来我们根据题目要求，建立多目标的0-1 模型，对课表进 行优化：5.3.1 模型建立：食堂拥挤度片=一周内上第二堂课的次数一周内上课的总次数代

15、入我们的符号系统有：20 X另因Aijkn i=1 j=1 k = 6广20另艺A3 610 Aijk i=1 j=1 k = 6-工另艺Aijkijk教室利用率役=m20 x 沁 25 Aijki=1 j=1 k =12一(20 +130 + 50) x 25单个教室的利用率n =3某个教室一周内使用的次数 某个教室一周内能用的次数单个教室的使用率我们在此用使用到的教室的平均利用率乘以一个使用系数n2来表示，即：n =一周内使用教室的总次数3（使用教室的个数）X2520 x 土6 25 Aijki=1 j=1 k=125 x s工r a-mm设 s = -m=1工amm=1其中使用教室的个数

16、我们采用加权平均值的模型来解决，而各类教室的使用次数我们再次借助计算机模拟的方法得到：利用计算机模拟技术，模拟100 次，我们得到了各类教室一周的使用次数表，见表 5.11表 5.11教室类型一周内的利用次数rm一周内的平均利用次数大教室10 1110中等教室272928小教室29 3331由此我们建立了如下的模型1：工为艺Aijk=i=1 j=1 k =6广工为送Aijki=1 j=1 k=120 x工艺艺Aijk n =iT j_l k_12 (20 +130 + 50) x 2520 x工为送Aijki=1 j=1 k=125x s工r a-m ms = -m=1amm =1A =0,1

17、ijk5.3.2 模型求解：根据我们所列出的课表，现在对n,n,n进行分析，确定可行域。123根据计算机模拟可知： 大一一周每天的第二堂课最多可上 5 次，大三一周每天的第二堂课最多可上 3 次，于是每天第二堂课最大的总数为5+5+3=13 ，最小的总次数为 1，故可得1n 即：丄纲 13411411314+15+12，14+15+121arm mm =1a 针对n，我们可以对公式进行转换，n =m=1 m，根据表5.11的结果，利22200 x 25用 matlab 编程可以得到0.2481 n 0.25082 在模型建立的过程中，我们已经分析过使用教室个数的计算方法（见式 ），在此，我们就

18、直接给出结果，每周教室的使用个数为 2633;于是有：0.2982n n 3的成对比较阵Q，将它的一致性指标CI与同阶的随机一致性指标RI (般查表，见附录 3,这里取0.58)之比称为一致性比率CR，若CR 0.1，则认为Q的不一致性程度 在容许范围内，可以用其特征向量作为权向量。否则就要调整Q，使之具有满意 的一致性用matlab编程可得到Q的特征向量(程序代码见附录3),归一化后为:Wp = (0.6870 0.1865 0.1265)7 n最大特征根为：九 =3.094 于是 CI = max = 0.047maxmaxn 一 1对其进行一致性检验CR = CI = 0.081 。，符

19、合一致性目标即表明 wp 可以作为各指标的权重向量,即：(w w w )= (0.68701230.1865 0.1265)于是，min f = 0.6870 0.1865 + 0.126512,至此,问题转化为一个简单的线3性规划问题：min f = 0.6870 - 0.1865耳 + 0.1265耳123113n 411410.2481 n 0.250820.2982n n 0.3785 n232六 模型的结果及分析针对以上规划模型，用lingo软件可解得,minf = 0.06055,且此时耳=12.2%1山=25.0%2=18.46%3据统计一般食堂拥挤度在 20%以上时，学生会觉得拥挤，本题中我们的解 =12.2% 1/41;a0.2481;b0.2508; c=0.2982*b; end