高校排课模型分析

毕业设计（论文） 题 目: 排课模型分析 系 名: 姓 名: 专 业: 班 级: 学 号: 指导老师:

2010年6月 摘要 排课是现在各个高校都会遇到的问题，高校教学活动中的排课也是对教学活动开展过程中需要的相关资源进行有机的组合，避免由于教学资源的浪费而影响学校教学活动的正常开展。 本文提出了在贪心算法的基础上建立数学模型，以课程人数对教室的需求，结合课程课时、类别对教师资源安排的影响，再加上教师自身及上课时间因素，通过条件筛选及实际的应用，得到各个子问题的局部最优解，再把子问题的解局部最优解合成原来解问题的一个解，在较短得时间里找到一系列比较满意的最优解。

关键词：排课；多因素；贪心算法；数学模型 Abstract Timetabling university now will encounter various problems, Timetabling university teaching activities is also carried out in the course of teaching activities related to a combination of organic resources, avoid waste of teaching resources to affect the normal teaching activities carried out. This paper proposes a greedy algorithm based on mathematical models, the number of the classroom curriculum requirements, combined with curriculum lessons, teacher resources category on the impact of the arrangements, together with their teachers and class time factors, and screening and the actual application conditions , each sub-problem by the local optimal solution, then the local sub-optimal solutions of problem synthesis of the original solution a solution of the problem, found in a relatively short time series were relatively satisfied with the optimal solution.

Keywords: Timetabling; multi-factor; greedy algorithm; mathematical model 目 录 引 言.............................................................................................................................. 1 第1章 问题重述、模型的假设及变量说明.............................................................. 1 1.1、问题重述.......................................................................................................... 1 1.2、模型的假设...................................................................................................... 5 1.3、变量说明.......................................................................................................... 5 第2章 模型建立与求解.............................................................................................. 7 2.1建立排课模型..................................................................................................... 7 2.2问题一求解......................................................................................................... 8 2.3问题二求解....................................................................................................... 10 2.4问题三求解....................................................................................................... 12 第3章 略模型的分析、检验和评价推广................................................................ 13 3.1排课模型分析与检验....................................................................................... 13 3.2排课模型的评价及推广................................................................................... 13 3.3程序的编写和计算........................................................................................... 14 结 论.......................................................................................................................... 20 致 谢.......................................................................................................................... 21 参考文献...................................................................................................................... 22 1

引 言 排课问题是查找满足多因素约束的“教室—课程—时间—教师”配对。我们把约束条件分成三类：硬性条件、中性条件和软性条件。 硬性条件：即绝对必需满足的条件。 ·和教室相关：课程对教室座位的最大要求数不能超过该教室的容量，且以最优近似值满足其需求量，以保证教学资源的充分利用； ·和课程相关：所有的课程都必须被安排； ·和时间相关：同类课程不能安排在同一个时间或同一个教室； ·和教师相关：同一个教师的不同课程不可以发生在同一个时间；且不同天上课的教师能被适当安排；教师的最大课时适时调整或增加聘用新教师来胜任多余课时。 中性条件：往往是介于绝对硬性和绝对软性条件中间的由学校自己决定。 ·当课程对教室有要求的时候，尽量满足；不以教室类别对课程产生的影响为条件，即在教室类型排完条件下，任意教室皆可用于一切教学活动。 软性条件：即在满足上面的基本条件的基础上，提出的更高的要求。 ·每个课程均匀的分布在工作日中；每周以五天为单位，每天以上午、下午、晚上为时限进行编排； ·同一类课程的不同课程编号均匀的分布在各工作日中，可以进行灵活的添加，它们并不影响可行解域的大小，只影响解的优劣。 只有符合硬性条件的配对，才是一个合法的配对。中性条件和软性条件用来评价配对的优劣度，在此约束条件下，得到目标解，即最优课程组合。 全文分为三章：引言，问题重述、模型的假设及变量说明，模型建立与求解，模型的分析、检验和评价推广。 1

第1章 问题重述、模型的假设及变量说明 1.1、问题重述 现有课程40门，编号为C01～C40；教师共有25名，编号为T01～T25；教室18间，编号为R01～R18。具体属性及要求见表1，表2，表3： 课表编排规则：每周以5天为单位进行编排；每天最多只能编排8节课（上午4节，下午4节），特殊情况下可以编排10节课（晚上2节），每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。 你所要解决的问题： 1. 请你结合实际情况建立数学模型，通过编程计算，给出较为合理的课表编排方案，分析你所给出的方案的合理性。 2. 如果不准晚上排课，排课结果是否有所变化，如何变化？ 3. 对教师聘用，教室配置给出合理化建议。 表1：课程属性及要求：表2：教师属性：表3：教室属性：下页附。