基于贪心算法的排课系统的设计与实现.doc

青岛农业大学本 科 生 课 程 论 文论 文 题 目 基于贪心算法的排课系统的设计与实现专 业 班 级 计算机科学与技术08级2班 学生姓名（学号） 指 导 教 师 许海洋 完 成 时 间 2010年11月10日 2010年 11 月 10日摘要：贪婪算法在解决诸如排课等NP完全问题中具有实用价值。本文通过描述排课问题及其数学模型，分析了基于优先级的贪婪算法在高校排课系统中的运用。利用该算法，既可以简化排课过程，缩短排课所花费的时间， 同时也能提高排课结果的满意度。关键词：排课问题；教学模型；优先级；贪婪算法一一、 引言排课是高校教务管理中一项十分重要的工作。它直接关系到全校的教学工作能否有序地按计划进行。同时，排课又是一项相当复杂的工作，其复杂性源于排课中资源约束条件和特殊要求对有限时空目标的制约。随着我国教育体制改革的不断深入，高校办学规模连年扩大，在校学生人数、教师人数、课程门类都显著增加，这对高校教务排课工作提出了更高的要求。研究开发一个实用的排课系统具有十分重要的现实意义。排课问题的本质是多维资源的冲突与争夺。它是一种典型的组合规划和目标不确定性调度问题。早在2O世纪7O年代，美国人SEven等就证明了排课问题是一个NP完全问题，其算法的时间复杂度呈指数增长。目前，除了使用“穷举法”获得近似最优解外，数学上还没有一个通用的算法能获得NP完全问题的最优解。然而由于“穷举法” 时问长，成本高，并无实际的应用价值。因此，降低解决NP完全问题的算法复杂度便成为研究课题，即利用一个近似算法，建立一个简约的模型，使解决问题的算法复杂度从指数增长简化为多项式增长，便于程序运行。在实际的应用中，很多研究者都提出了各种解决排课问题的算法，包括遗传算法、动态规划法、回溯法、模拟退火算法等，其中基于优先级的贪婪算法是一种简便有效的解决最优化问题的基本方法。根据贪婪算法设计的排课系统，可以简化排课过程，在实际的运行中再通过少量的人工干预，在资源条件充足的前提下，基本可以解决排课过程中的冲突和死锁问题，使排课系统具有实用价值。二、 排课问题描述(一) 排课原则排课问题是一个集班级、课程、时间、教师、教室五维组合优化问题。排课的主要任务，就是根据学校的学期教学计划，对全校各班级所开设的课程在上课时间和上课地点的合理安排，确保排课不发生冲突。排课的目标，就是在满足各种约束条件的前提下，充分利用学校的教学资源，获得最好的教学效果。一个好的课表应能符合学校的管理要求，满足所有参与者的基本要求，尽可能使绝大多数课程的安排能够令师生满意。为了编排出满意的课表，在排课中必须遵守以下基本原则：(1) 一个班级的学生在同一时间只能安排一门课程；(2) 一位教师在同一时间只能安排一门课程；(3) 一间教室在同一时或只能安排一门课程且教室类型必须符合该门课程的要求；(4) 同一时间安排的课程总数不能大于所能提供的教室总数；(5) 每门课程参加学习的总人数不应大于所安排教室的座位数；(6) 一个班级每门课程不能被重复安排；(7) 体育课不排上午1、2节；(8) 3课时的课安排在下午。同时，为了使排出的课表更合理、更具人性化，排课还应考虑以下因素：(1) 每门课程在一周内的上课时间尽可能分布合理；(2) 尽可能使同一个班级连续的两门课之间更换教室的机率小，或就近安排；(3) 同一课程的不同讲次尽可能安排在同一教室，而且要隔一天以上安排，使教师有充足的时间备课和批改作业，学生也有足够的时问复习消化；(4) 学生每天的必修课安排尽可能趋于平衡：(5) 尽可能满足每门课程教学的客观要求；(6) 满足个别教师(如外聘教师)的特殊上课时间要求。在排课中必须遵守的基本原则、人性化因素和特殊要求构成了排课约束条件。(二) 排课问题数学模型排课问题涉及班级、课程、时间、教师、教室五个方面数据，是一个典型的排列组合问题。由于排课前课程与教师的关系已经在教学计划中确定，因而，在排课时，只要对学校所有班级开设的每门课程，安排课程、教师、教室具有共同的空闲时间片上课即可，排课算法也就简化为班级、教师、教室三方面数据在具有共同的空闲时间片前提下的排列组合问题，三者关系如图1所示。它们在三维空间上的交点P表示一个排课组合的选择，即可能的教学安排。排课问题就是遵循一定的约束规则，在这个三维空间搜索空闲时间片集合，如果该集合存在，说明排课问题有解。为了描述排课算法，定义CNi为课程课时单元，其中CN表示所开设的课程名称，下标表示该门课程的第i个课时，那么，课程的课时单元集合可以表示为CNI，CN2，CNi ，定义TC为排课瞬间班级空闲时间片集合，TT为排课瞬间教师空闲时间片集合，TR为排课瞬问所有教室空闲时间片集合， CARD 用于求集合的元素个数。显然， 当每门课程都满足CARD(NT*TN*TR)=CARDCN1，CN2，CNi 时，排课问题有解。上面描述了排课算法有解时的理想化状况。实际的排课过程，往往受到各种各样约束条件的影响而出现无解情形，这些影响主要包括以下两个方面：(1)虽然整体上满足有解条件，但在当前条件下， 由于对特定资源条件的需求，导致局部资源的欠缺，将出现排课无解。例如， 由于学校只在部分教室安装多媒体设备，当有多个班级要求在多媒体教室上课时，虽然所有教室的空闲时间片集合大于待排课程的课时单元集合，但多媒体教室空闲时问片集合小于待排课程的课时单元集合，则导致求解失败。(2)基于排课原则或人性化排课要求，使得TCNTTNTR中的元素成为不可用元素，出现CARD(NT*TN*TR)=CARDCN1，CN2，CNj ，j也将出现排课无解。例如，要求一门课程的不同课时安排同一教室时，此约束条件导致TC*TT*TR中大多数元素成为不可用元素，也会导致求解失败。上面分析的两方面影响， 在排课的后半期， 当大部分资源被占用的情况下，特别容易发生，可以通过人工干预进行调整。三、 基于优先级的贪婪算法排课分析(一) 贪婪算法基本思想贪婪算法是一种简化解题复杂度的算法。它不在整体最优上加以考虑，而是采用优先级逐步构造最优解的解题思想。也就是说，它总是把整个解题过程分解成一个个细小的步骤，并根据其难易程度确定其处理顺序，做出在当前看来是局部最优的选择，逐步逼近给定的目标，以尽可能快地获得满意的处理结果。虽然贪婪算法不能使所有问题都得到整体最优解，但对很多问题它能产生整体最优解，如货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树问题等。在一些情况下，即使贪婪算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。使用贪婪算法解决问题一般包括以下几个步骤：(1) 确定求解目标；(2) 分析约束条件；(3) 建立优化函数：(4) 制定贪婪策略，贪婪策略的是利用贪婪算法解决最优化问题的关键，它关系到问题能否得到成功解决及解决质量。(二) 基于优先级的贪婪算法排课流程基于优先级的贪婪算法排课过程仿照人工排课方法，以排课班为单位，围绕着各对象(班级、教师、教室)的空闲时间片表选择合适的时间片，在时问片上选择最优的资源进行排课。每个排课班课表排定后，教师及教室的课表也就随之排定。在教师、教室资源不紧缺的情况下，基于优先级的贪婪算法能排出相对合理的课表。为了降低贪婪排课算法的复杂度，可以采用化整为零和优先级贪婪策略。首先根据教学计划确定排课班，然后分析各个排课班及开设课程对教学资源占有情况，并按各排课班所开课程对教学资源占有多少及特殊要求，确定优先级，最后再按照优先级逐个编排。图2描述了基于优先级的贪婪算法排课流程，具体步骤如下：(1)确定排课班。我们把按行政角度划分的班叫行政班，把在同一个教室上课的班叫做排课班，如果有A、B两个行政班，他们有课程合班上课，C代表合班，则形成A、B、C三个排课班，c班课表最后加入A、B班课表，形成完整的课表，每个排课班都维护着自己的一张课表。(2)确定优先原则。优先级涉及多个因素，如时间优先、地点优先等，它们之间的关系错综复杂，也受制于前面所述的排课原则。例如，在若要满足老师对授课时间提出特殊要求时，时间是最优先要考虑的因素；对于要求在特定的教室上课的课程，地点是最优先要考虑的因素。根据学校的具体情况，设计好优先原则是实现合理排课的关键。排课过程要在遵循排课原则的前提下，确定好解题的优先原则，具体表现为：第一，具有唯一性的特殊要求最优先；第二，对资源占有数量大、要求高、资源紧缺的、涉及班级多、同一个教师带多门课程的、课程重要的优先。例如，合班的课，实验类课程，体育课，全校性的公共基础课等；第三，最后考虑无任何要求的情况。(3)计算优先权值(Weight)。在实际排课中，要量化优先级，以便于计算机处理。为了量化优先级，基于以上优先原则，我们引入待排课程优先权值概念及计算方法。定义FT为一周排课时间片总数，AT为某课程该班可排课时间片数量，FR为排课教室总数，AR为该课程可排课教室(容纳人数排课班人数，且教室类型符合要求)数量，M为该课程课时单元数，N为合班数，则某门课程的优先权值。例如，学校每天有5个排课时间片，一周5天，则FT=25，学校总教室数100问，则FR=100，若某个班级的某门课程有2个课时单元，3个班合班，总人数120人，要求排在上午，使用多媒体教室，而学校大于120人的多媒体教室只有8间， 此时，。待所有排课班各门课程的优先权值计算好后，就可以按值从高到低分批排课。若优先权值相同，可以使用随机算法进行选择。(三) 死锁问题的处理所谓死锁，就是指在有效输入的前提下，课程无法找到满足条件的可排课时间和地点。造成死锁的原因有多个方面，其中资源约束条件和排课原则的冲突是造成死锁的主要原因。死锁是组合调度算法中经常出现的问题，在课表调度问题中，由于还没有一个完备的好算法，所以死锁也难以避免。死锁问题有多种处理方法。笔者认为，在计算机排课中，遇到死锁时，可以让排课系统中断运行，屏幕上同时显示导致死锁的原因和状态，根据系统提示的情况进行人工调整，使排课过程得以继续，不失为一种简便的处理方法。人工调整可以适当采取以下几种方法：(1)调整目标函数的参数，对预先设置的排课条件进行适当解禁；(2)调整课程的相关参数信息；(3)同一门课程不同教师所带班级互换；(4)调整某一门课程的排课时间，可以有助于算法转向解空间的其他区域；(5)重新运行排课系统。由于当优先权值相同时，系统通过随即算法选择，重新排课，可能解决死锁问题。四、 结束语本文分析了基于优先级的贪婪算法在高校排课系统中的运用。通过模拟实验，结果表明采用此算法，大大地简化了排课难题，降低了解题的时间复杂度，使长期困扰的难题变得简单、高效。参考文献：1 赵晓庆,熊璋,方义.高校智能排课系统的设计与实现J.计算机与现代化,2004(11) :102-105.2