排课问题分析.docx

《排课问题分析.docx》由会员分享，可在线阅读，更多相关《排课问题分析.docx（31页珍藏版）》请在三一办公上搜索。

1、排课问题分析排课问题分析 摘要： 本题要求我们对多约束条件的典型组合进行分析，求解，并作最优化处理。基于此种原因，我们先对各个元素间的冲突做预处理，进行约束条件的规划，再通过matlab软件将教室、教师、课程和时间间的约束条件统一化，构成R-T-C表，再将各个元素进行优先级的计算，从而根据排课的优化模型，求出最优解。 经过对所给的表格，数据的深入分析，我们可以得知，教师明显缺少，比如课程学时要求有160个课时，然而教师能上的课时仅有116个课时，所以开始排课时，不考虑教师，向教师中安排课程。 由于同类课程最好不要放在一起，同时根据老师的需求和教室的开放时间进行分配，经过与我们实际的课表的排课情

2、况的分析，比如隔一天排同一课，课程类别不同的课程不在同一时间上课，我们可以大致的排出一个按教室上课的表，即R-T-C表。通过对R-T-C表的分析，发现有很多课没老师上和老师没课上的情况，我们就对其进行相应的，合理的调整。最后发现还是老师要外聘。将外聘14名老师去上相应没人上的科目，具体情况见附表。 最后，我们得到了一张相对优化的，以教室为准的课表，从而解决问题的要求。对于我们课表的安排，发现再没对晚自习有其他条件约束是不会对所排的课表有所影响。 关键词：排课问题 组合规划 多目标函数 数据量化 优先级 一、 问题重述 对于有课程40门，教师共有25名，教室18间的条件下合理的安排课程表，而课程

3、、教师、教室的具体属性及要求详见附表 对于课表德编排，题目有如下规则：每周以5天为单位进行编排；每天最多只能编排8节课，特殊情况下可以编排10节课，每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。 要求所要解决的问题： 1. 请你结合实际情况建立数学模型，通过编程计算，给出较为合理的课表编排方案，分析你所给出的方案的合理性。 2. 如果不准晚上排课，排课结果是否有所变化，如何变化？ 3. 对教师聘用，教室配置给出合理化建议。 二、问题分析 随着现代教学的改革及各项教育工程的实施，新的教育体制对课表的编排提出了更高的要求。但现实生活中，排课问题屡屡皆是，小学如此，中学如此，大学更

4、是如此，不仅科目多样，而且教室、老师多变，这使得排课问题往往是很令人费解的。经过分析，排课问题就是的多资源组合问题，问题的求解就是找出各个元素间的对应关系。进而将各个元素间的联系进一步确定，转化成一个可以量度其大小的值，从而确定优先级，而我们又将如何确定各元素间的关系，目标函数的确定？ 根据已有知识可以知道，本题主要分析的是建立一个排课的优化模型。而它是一个在课程类别、教师编号、教师及时间上的一个四维空间模型，在各种约束条件下的组合规划问题，其实质就是解决各因素间的冲突问题。在模型建立后，我们有根据什么参量得到排课的最优解。 三、基本假设 模型假设： 1、学校的教师和教室资源及学生班结构在一个

5、学期内不会有的变动 2、所有的教室都在同一个校区，且12节课的教室到34节课的教室的路程不超过10min 3、在一学期内，任课教师身体都非常健康，不存在因病因事缺课的情况 4、各种教学资源在一学期内都不会发生故障，影响上课 5、在上课期间，老师、学生都不迟到，不影响上课质量 6、当有3个课时时，我们当做2个课时处理，及3节连堂上 符号说明： Rn Cn Tn Y外聘 P X1 X2 X3 D W1 W2 教室编号 n=1,2,3.18 课程类别 n=1,2,3.40 教师编号 n=1,2,3.25 外聘教师编号 n=1,2,3.14 T老师在R教室上C课 时间段效率 教室利用率 教师满意度 优

6、化级的量度值 权衡时间段效率参数 权衡教室利用率参数 W3 Q 权衡教师满意度参数 安排课程的最优值 相关名词解释： 时间段效率：经上网查询及对相关资料的查阅，我们得知一天内听课效率最高的是上午810，下午13，故我们定义上午12的听课效率为3，其余见附表。 教室利用率：为充分利用教室资源，我们定义：教室利用率= 上课总人数， 教室最大容纳量四、问题的分析及模型的建立 问题分析 从数学角度上讲，本题主要分析建立一个排课模型，而它是一个在课程类别、教师编号、教师及时间上的一个四维空间模型，在各种约束条件下的组合规划问题，其实质就是解决各因素间的冲突问题。在此为了简化处理，先从课程类别、教室编号入

7、手，建立一个关于C-R的关系表，再采用化零为整的思路建立我们的目标函数优化模型，最后，我们根据各因素对排课模型的优先度，求解出排课模型的最优解。 在对问题初始化分析时，我们发现课程类别、教室编号、教师、上课时间存在这么一个对关系： 1）11的对应关系 2）1n的对应关系 3）nn的对应关系 进而，我们再对它们之间的属性分析，根据它们间的联系求出一种相对合理的排课方案，最后，对方案的合理性进行分析。 模型的建立 经过分析，我们需将所有课程尽量合理的安排在一个星期内。首先我们将一个星期划分为五天，记作1、2、3、4、5，将一天分为四个部分，记作1、2、3、4，进而，我们将得到一个54的矩阵。其中，

8、j=1、2、3、4、5分别表示星期一、星期二、星期三、星期四、星期五；i=1、2、3、4分别表示12节课、34节课、56节课、78节课。即有： P(TRC) t=1r=1c=1251840我们记作P是一个TRC维的数列矩阵，表示T老师在R教室上C课， 我们定义P=1时，即老师、教室、课程三者都相互符合是记作1 而P=0时，即老师、教室、课程三者中有一项不符合记作0 规定：A(TR)表示T老师到R教室上了一次课是，即2个节 B(TR)表示T老师到R教室上总课时 约束条件： 1）每一个时间段都不能多于一个老师在一个教室上课，此时应满足的条件是： 25P(TRC)1 nN t=12）每位老师在每一天

9、不能同时对同一个班上上两次课， P(TRC)1 i=143）某位老师在某一间教室上课时，安排的课就该在这间教室排完，此时应满足的条件是： 2P(TRC)=2A(TR)B(TR) j=1i=154当一位老师连续两天对同一个班上两次课以上的次数越少、课程安排在听课效率高的时间段次数越多和老师与老师之间的冲突次数越少，此时定义： Q=t=125P(TRC) r=1c=11840同时有满足以上的约束条件，Q将取到最优值，即此时安排的课表最优化 排课的预处理 1) 同一教师在同一时间内不能安排两门课 同一教室在同一时间内不能安排两门课 同一时间内安排的课时总数不能大于教室的课时总数 所提供的教室属性安排

10、课程的所需教室属性一致 2) 优化级的计算： 考虑到课表的安排是为了按时保量的完成教学任务，而其影响因素有众多，这里我们主要考虑一下三种： 1）时间段效率 2）教室利用率 3）教师满意度 所以我们对课表的安排原则将依据优先级的大小进行排课。 先对以上三个因素进行量化处理可得到： 时间段效率： 上午12 上午34 下午12 3 0 2 教室利用率： 10.8 0.60.8 0.40.6 3 2 1 教师满意度： 很满意 满意 一般 3 2 1 我们定义优先级的函数表达式为： 下午34 1 0.20.4 0 不满意 0 D= W1X1+X2+ W3X3 其中W1 W2 W3表示相应参数，可根据实际

11、情况进行调整的 通过上式，我们可以很容易得知上课的时间段效率、教室利用率、教师满意度越大，D值就越大即优先级越大，就优先排课；反之，D值越小，优先级就越小，就相对后排课。 通过模型得到的T-R-C表，再根据优先级的排课，我们可得到一个相对优化的课表: R3教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 上午1-2 C12-T9 上午3-4 C18-T24 C18-T24 下午1-2 C6-T6 下午3-4 这里就不一一罗列，其余详见附表。 模型的评价与改进 优点： 到了一种排课的方法，即将课程表按课时数撤分，再按没门课程的优先顺序依次放入课表中。在考虑其他因素的情况下，本模型便于进

12、一步发展、完善。比起目前最相对合理的遗产法简单易懂很多。 缺点： 有很多待改进之处，该算法的优先级只是根据经验常识来进行优先级安排课程，具有一定的非科学性，如果能根据一定的科学知识，对课程的优先级进行科学的评定，科学的地算出其优先级系数，再确定其优先级，会具有更好的合理性。再解题过程中限制条件多，数据量大，过程相对较繁琐。 模型推广 本模型有编程优化的模块，但排课表是人为因素较多，也是为了满足课程的安排过程中更人性化。因此本模型适用于中小规模的排课，其主要限制因素是程序完善度不高，如要进行推广，则必须增加程序的模块，使其更完善，相信改进完善后，即可更科学的实现大规模大排 参考文献： 1 数学建

13、模，成都电子机械高等专科学校，二零一零年三月 2 数学建模资料最优化模型.pdf 2010.7 3 回溯法 2010.7 4 贪婪法 2010.7 5 一天的最有听课效率时间段 2010.7 附表： 表1：教师属性： 周最大 对教室类别要求 课时数 4 多媒体教室或机房 4 普通教室 6 普通教室 4 多媒体教室 4 普通教室 6 普通教室 4 普通教室 3 普通教室或机房 4 普通教室 6 多媒体教室 8 普通教室 4 普通教室 6 多媒体教室 2 普通教室 3 普通教室或机房 4 普通教室 4 普通教室 6 普通教室 4 多媒体教室 4 普通教室 6 普通教室 6 多媒体教室 4 普通教室

14、或机房 6 普通教室或机房 4 普通教室或机房 教师编号 T01 T02 T03 T04 T05 T06 T07 T08 T09 T10 T11 T12 T13 T14 T15 T16 T17 T18 T19 T20 T21 T22 T23 T24 T25 能胜任课程类别 1，8 1 1 2 2 2 3 3，8 3 3 4 4 4 5 5，8 5 6 6 6 7 7 7 3，8 4，8 6，8 上课时间要求 上午 下午 上午 上午 下午 无 上午 下午 上午 上午 下午 无 下午 上午 下午 上午 下午 无 下午 上午 下午 上午 无 上午 下午 尽可能不同天上课的教师 T4 T1 T11,T

15、18 T9, T23 T9 T15 课程编号 C01 C02 C03 C04 C05 C06 C07 C08 C09 C10 C11 C12 C13 C14 C15 C16 C17 C18 C19 C20 C21 C22 C23 C24 C25 C26 C27 C28 C29 C30 C31 C32 C33 C34 C35 C36 C37 C38 C39 C40 课程类别 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 表2：课程属性及要求： 对教室座位对教室 周课时数 最大要求数

16、类别要求 4 50 多媒体教室 4 30 普通教室 6 40 普通教室 4 25 多媒体教室 3 60 普通教室 4 100 普通教室 4 50 多媒体教室 2 30 普通教室 4 40 普通教室 3 25 多媒体教室 6 60 普通教室 4 80 普通教室 6 50 多媒体教室 2 30 普通教室 3 40 普通教室 4 25 多媒体教室 4 60 普通教室 6 90 普通教室 4 50 多媒体教室 2 50 普通教室 4 30 普通教室 4 40 多媒体教室 3 25 普通教室 6 60 普通教室 4 100 多媒体教室 3 50 多媒体教室 4 30 普通教室 4 40 普通教室 4 5

17、0 多媒体教室 4 30 普通教室 6 40 普通教室 4 25 多媒体教室 3 60 普通教室 4 80 多媒体教室 4 50 普通教室 6 30 机房 4 40 机房 2 25 机房 4 60 机房 4 50 机房 表3：教室属性： 时间要求 上午 下午 下午 上午 下午 下午 上午 上午 下午 上午 上午 上午 下午 下午 下午 上午 下午 上午 上午 上午 上午 下午 上午 下午 上午 下午 下午 下午 上午 下午 上午 下午 无 上午 下午 无 上午 上午 下午 无 教室编号 R01 R02 R03 R04 R05 R06 R07 R08 R09 R10 R11 R12 R13 R1

18、4 R15 R16 R17 R18 最大座位数 100 100 100 50 50 50 50 60 60 60 60 60 40 40 40 40 50 40 教室类别 多媒体教室 普通教室 普通教室 多媒体教室 普通教室 普通教室 普通教室 普通教室 普通教室 多媒体教室 普通教室 机房 机房 机房 机房 多媒体教室 普通教室 普通教室 表4：T-R-C表 课程 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C15 C16 C17 C18 C19 C20 C21 C22 老师 T1 T2 T3 T6 T4 T6 T5 T7 T10 T8 T9

19、 T13 T11 T24 T11 T12 T16 教室 容量 R(10) 50/60 R(18) 30/40 R(18) 40/40 R(2)R(3) 100/100 R(4) 50/50 R(18) 30/40 R(18) 40/40 R(2)R(3) 80/100 R(4)R(16) 50/50 R(18) 40/40 R(18) 40/40 R(16) 30/40 R(8)R(9)R(11) 60/60 R(2)R(3) 90/100 R(5)R(6)R(7)R(17)50/50 R(5)R(6)R(7)R(17) 50/50 R(18) 30/40 C23 C24 C25 C26 C2

20、7 C28 C29 C30 C31 C32 C33 C34 C35 C36 C37 C38 C39 C40 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 R(4) 50/50 R(18) 40/40 R(18) 40/40 R(8)R(9)R(11) 60/60 R(1) 80/100 R(5)R(6)R(7)R(17)50/50 R(13)R(14)R(15) 25/40 R(12) 60/60 R(12) 60/60 表5：各教室课程安排： R1教室一周内课程安排 星期一 星期二 星期三 星期

21、四 星期五 C34-T22 C34-T22 C25 C25 R2教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C18-T24 C12-T9 C6-T6 R3教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C12-T9 C18-T24 C18-T24 C6-T6 R4教室一周内课程安排 T19 T18 T17 T20 T22 T21 T15 T25 T23 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4

22、下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 星期一 星期二 星期三 星期四 星期五 C13-T10 C19-T11 C13-T10 C19-T11 C26-T19 R5教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C21-T16 C35-T21 C35-T21 C21-T16 C30 C17-T12 C30 R6教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C31-T21 C28-T17 C9-T5 C9-T5 C28-T17 R7教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C8-T6 C20-T12 C27-T17 C2

23、7-T17 C3-T3 R8教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C31 C31 C5 C33-T20 R9教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C11 C11 C11 C24 C24 C24 R10教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 C1-T1 C29 C29 C7-T4 C7-T4 C1-T1 R11教室一周内课程安排 星期二 星期三 星期四 星期五 C17-T11 C17-T11 R12教室一周内课程安排 星期一 上午1-2

24、上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 星期一 星期二 星期三 星期四 星期五 C40-T23 C39-T25 C39-T25 C40-T23 R13教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C28-T18 C36 C28-T18 R14教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C37 C37 C36 C36 R15教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C38-T24 R16教室一周内课程安排 星期

25、一 星期二 星期三 星期四 星期五 上午1-2 上午3-4 下午1-2 下午3-4 上午1-2 上午3-4 下午1-2 下午3-4 C16-T13 C4 C22 C32 C22 R17教室一周内课程安排 C10 星期一 C4 C16-T13 C32 上午1-2 上午3-4 下午1-2 下午3-4 外聘教师 YT1 YT2 YT3 YT4 YT5 YT6 YT7 YT8 YT9 YT10 YT11 YT12 YT13 YT14 星期二 星期三 星期四 星期五 C14-T08 C2-T2 C15-T9 R18教室一周内课程安排 星期一 星期二 星期三 星期四 星期五 C23 C8-T6 C3-T3

26、 C2-T2 C3-T3 C14-T8 表6：外聘教师课程安排表： 课程 课时 教室 时间 C25 4 R1 二34，五12 C30 4 R5 二56，五56 C31 4 R8 一12，三34 C5 3 R8 二123 C11 6 R9 一12，三12，五12 C24 4 R9 一56，三78，五78 C29 4 R10 二12，四12 C36 6 R14 一56，三78，五56 C10 3 R16 一123 C4 4 R16 二34，五12 C22 4 R16 一56，四78 C32 4 R16 二78，五78 C23 3 R18 三123 C37 4 R14 二12，四34 程序附录： c

27、lear; C= 1 2 2 1 1 1 2 1 2 -1 1 3 1 2 -1 1 2 1 1 1 1 2 3 2 -1 2 2 4 2 -1 2 2 2 1 1 2 1 1 2 1 2 2 1 2 -1 2 2 1 1 1 3 3 3 2 1 3 2 4 2 1 3 3 2 1 -1 3 1 1 2 -1 3 2 1 2 -1 4 2 1 1 1 4 2 3 2 -1 4 3 4 2 1 4 2 2 1 1 4 1 2 2 1 5 2 1 2 1 5 2 1 1 -1 5 2 1 2 1 5 3 3 2 -1 5 2 4 1 1 6 2 2 1 -1 6 2 1 2 -1 6 2 1 2

28、-1 6 2 2 1 1 6 2 1 2 -1 7 3 1 2 1 7 2 1 1 -1 7 2 3 2 0 7 2 4 1 1 7 2 2 2 -1 8 3 1 3 0 8 2 1 3 1 8 1 1 3 1 8 2 3 3 -1 8 2 2 3 0 ; T= 1 8 4 4 1 4 0 1 0 4 2 -1 0 0 1 0 6 2 1 0 0 2 0 4 1 1 1 0 2 0 4 2 -1 0 0 2 0 6 2 0 0 0 3 0 4 2 1 0 0 3 8 3 5 -1 0 0 3 0 4 2 1 11 18 3 0 6 1 1 0 0 4 0 8 2 -1 9 0 4 0 4 2

29、0 0 0 4 0 6 1 -1 0 0 5 0 2 2 1 0 0 5 8 3 5 -1 23 0 5 0 4 2 1 0 0 6 0 4 2 -1 0 0 6 0 6 2 0 9 0 6 0 4 1 -1 0 0 7 0 4 2 1 0 0 7 0 6 2 -1 0 0 7 0 6 1 1 0 0 3 8 4 5 0 15 0 4 8 6 5 1 0 0 6 8 4 5 -1 0 0 ; R= 4 1 4 2 4 2 2 1 2 2 2 2 2 2 3 2 3 2 3 1 3 2 3 3 1 3 1 3 1 3 1 1 2 2 1 2 ； %Rt为教室与老师的关系 Rt=zeros(25,

30、18); for i=1:18 for m=1:25 for n=1:40 if R(i,1)=C(n,3) i1=C(n,1); if T(m,1)=i1|T(m,2)=i1 i4=T(m,4); switch (i4) case 1 if R(i,2)=1 Rt(m,i)=1; end case 2 if R(i,2)=2 Rt(m,i)=1; end case 3 if R(i,2)=3 Rt(m,i)=1; end case 4 if R(i,2)=1|R(i,2)=3 Rt(m,i)=1; end case 5 if R(i,2)=2|R(i,2)=3 Rt(m,i)=1; end

31、end end end end end end Rt; %Rc为教室与课程的关系 Rc=zeros(18,40); for i=1:18 for n=1:40 if R(i,1)=C(n,3)&R(i,2)=C(n,4) Rc(i,n)=1; end end end Rc; %Tc for m=1:25 for n=1:40 if T(m,1)=C(n,1)|T(m,2)=C(n,1) if T(m,3)=2*C(n,2) q=T(m,4); t=T(m,5); switch q case 1 if C(n,4)=1 switch t case 1 if C(n,5)=1 Tc(m,n)=1;

32、 end case -1 if C(n,5)=-1 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end case 2 if C(n,4)=2 switch t case 1 if C(n,5)=1 Tc(m,n)=1; end case -1 if C(n,5)=-1 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end case 3 if C(n,4)=3 switch t case 1 if C

33、(n,5)=1 Tc(m,n)=1; end case -1 if C(n,5)=-1 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end case 4 if C(n,4)=1|C(n,4)=3 switch t case 1 if C(n,5)=1 Tc(m,n)=1; end case -1 if C(n,5)=-1 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end case 5 if C(

34、n,4)=2|C(n,4)=3 switch t case 1 if C(n,5)=1 Tc(m,n)=1; end case -1 if C(n,5)=-1 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end end end end end end Tc; %在完全满足的情况下 课程选择最优化的老师 %Ct说明行代表课程，列代表能上该课的老师编号 %if有相同编号的老师 那针对该门课程进行求最优值，将值最大的老师放入相应课程中 Ct=1 0 0; 2 0 0; 0 0 0; 1 0 0; 2 0 0; 5 6 0; 4 0 0; 6 0 0; 5 6 0; 4 0 0; 0 0 0; 7 9 23; 0 0 0; 8 23 0; 23 0 0; 0 0 0; 11 12 0;