基于遗传算法的排课系统

第２３卷第１１期　！￣Ｊｌｌ教育学院学报　２００７年１１月　Ｖｏ１．２３　ＪＯＵＲＮＡＬ　ＯＦ　ＳＩＣＨＵＡＮ　ＣＯＬＬＥＧＥ　０Ｆ　ＥＤＵＣＡＴＩＯＮ　Ｎｏｖ．２。Ｏ０７　。　

基于遗传算法的排课系统　许楠　（四川教育学院电子信息工程系，成都６１００４１）　摘要：随着高校的发展，在教务管理系统中使用的排课模型也变得越来越复杂，亟需一种适用于开发、重　用及设计的方法。针对这种情况，文章给出了排课问题的数学模型，提出基于遗传算法解决方案。结果表明，该　算法能比较有效的解决排课问题。该方法易于学习和应用，且不必依赖特殊的实现模式。　关键词：排课；遗传算法；优化算法　

Ｔｈｅ　Ｃｌａｓｓ　Ａｒｒａｎｇｅｍｅｎｔ　Ｓｙｓｔｅｍ　Ｂａｓｅｄ　ｏｎ　Ｈｅｒｅｄｉｔｙ　Ａｌｇｏｒｉｔｈｍ　Ａｂｓｔｒａｃｔ：Ａｓ　ｔｈｅ　ｏｎｇｏｉｎｇ　ｄｅｖｅｌｏｐｍｅｎｔ　ｉｎ　ｔｈｅ　ｈｉｇｈｅｒ　ｅｄｕｃａｔｉｏｎ　ｉｎｓｔｉｔｕｔｉｏｎｓ，ｔｈｅ　ｃｌａｓｓ　ａｒｒａｎｇｅｍｅｎｔ　ｍｏｄｅｌ　ｉｎ　ｔｈｅ　ｍａｎａｇｅｍｅｎｔ　ｓｙｓｔｅｍ　ｉｓ　ａｌｓｏ　ｂｅｃｏｍｉｎｇ　ｍｏｒｅ　ａｎｄ　ｍｏｒｅ　ｃｏｍｐｌｉｃａｔｅｄ，ｅｘｔｒｅｍｅｌｙ　ｉｎ　ｎｅｅｄ　ｏｆ　ａ　ｗａｙ　ｗｈｉｃｈ　ｉｓ　ｓｕｉｔａｂｌｅ　ｆｏｒ　ｄｅｖｅｌｏｐｉｎｇ．ｒｅ—ｕｓｉｎｇ　ａｎｄ　ｄｅｓｉｇｎｉｎｇ．Ｉｎ　ｔｈｉｓ　ｋｉｎｄ　ｏｆ　ｓｉｔｕａｔｉｏｎ，ｔｈｉｓ　ｐａｐｅｒ　ｈａｓ　ｓｈｏｗｅｄ　ｓｏｍｅ　ｄｅｍｅｒｉｔｓ　ｉｎ　ｔｈｅ　ｃｌａｓｓ　ａｒｒａｎｇｅｍｅｎｔ　ｓｙｓｔｅｍ，ａｎｄ　ｐｕｔ　ｆｏｒｗａｒｄ　ｓｏｍｅ　ｂａｓｉｃ　ｍｅｔｈｏｄｓ　ｓｏｌｖｉｎｇ　ｈｅｒｏｄ－　ｉｔｙ　ａｌｇｏｒｉｔｈｍ．Ａｓ　ａ　ｒｅｓｕｌｔ，ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ｓｈｏｗｅｄ　ｂｅｔｔｅｒ　ｒｅｓｕｌｔ　ｏｆ　ｃｌａｓｓ　ａｒｒａｎｇｅｍｅｎｔ　ｓｙｓｔｅｍ．Ｔｈｉｓ　ｍｅｔｈｏｄ　ｉｓ　ｅａｓｙ　ｔｏ　ｌｅａｒｎ　ａｎｄ　ｄｏｅｓ　ｎｏｔ　ｎｅｅｄ　ａｎｙ　ｓｐｅｃｉａｌ　ｒｅａｌｉｚａｔｉｏｎ　ｍｏｄｅ１．　Ｋｅｙ　ｗｏｒｄｓ：ｃｌａｓｓ　ａｒｒａｎｇｅｍｅｎｔ；ｈｅｒｅｄｉｔｙ　ａｌｇｏｒｉｔｈｍ；ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　

中图分类号：ＴＰ３１　文献标识码：Ａ　文章编号：１０００－５７５７（２００７）１１－０１０２－０２　一、

介绍　

随着近几年各个高校的合并与扩招，我国的综合性大学　和各个高校中在校的学生数量的大大增加，对于高校教务部　门来说，排课工作是非常令人头痛的事，经常会出现课程排　列冲突，比如：一个教师在同一时间上两门课，有两个教师同　时去一个教室上不同的课程，有些教师在特定时间不可以上　课。如果没有很好地解决这些冲突，必将产生教学混乱等现　象。可见，排课算法的正确性、高效性是非常关键的。…　２Ｏ世纪７Ｏ年代中期，就有人论证了课表问题是ＮＰ完　全问题。当课表所涉及的任何信息量稍有变化将会导致课　表编排选择方案的剧增。课表问题存在固定的数学模型，　能找到相应的解，且是一组解集。Ｌ２　为此，现提出一些关于　高校教学管理系统排课的算法。　二、排课问题的数学模型　学校排课问题本质上是时间表问题的一类典型应用实　例，是为了解决课程安排对时间和空间资源的有效利用并　避免相互冲突。在排课过程中，需要考虑课程教学效果、满　足教师特殊要求等多项优化指标，将各门课程安排到相应　的时间和教室需要付出一定的“成本”（Ｃｏｓｔ）。　符号与约束条件　设课程集合：Ｌ＝｛１１，１２，．，ｌｐ，．，１Ｐ｝；班级集合：Ｃ：　｛ｃ１，ｃ２，．，ｃｍ，．，ｃＭ｝；教室集合：Ｒ＝｛ｒｌ，ｒ２，．，１－ｉｌ…ｒＮ｝　；教师集合：Ｓ＝｛ｓｌ，ｓ２…ｓｋ，．，ｓＫ｝；时间集合：Ｔ＝｛ｔｌ，　ｔ２，．，ｔｄ，．，ｔＤ｝；时间与教室对的笛卡尔积为：Ｇ＝Ｔ・Ｒ＝　（ｔｌ，ｒ１），（ｔｌ，ｒ２），．，（ｔＤ，ｒＮ）；Ｇ中的元素称为时间教室　对；课表问题的求解过程就转化成为每一门课程寻找一个　合适的时间教室对。　排课过程中必须满足各种约束条件，可以将各种约束　条件归纳成两类以简化分析过程。　（１）硬约束条件　硬约束条件是在排课过程中由于各类资源的有限，因此　必须满足而无法变更的约束条件，通常只要满足下面三类硬　约束条件就能够保证在排课的过程中不发生此类冲突。　①同一时间，一个教师不能同时有一门以上的课程，记　为Ｒ１：　Ｒ１为：≤１　其中：ｋ＝１，．，Ｋ；ｄ＝１，．，Ｄ。　＝１教师ｓｋ在时间ｔｄ和教室ｒｎ上课程ｌｐ；Ｏ否则。　②同一时间，一个班级不能同时有－－ｆ－］以上的课程，记　为Ｒ２：　Ｒ２为：≤１　其中：ｍ＝１，．，Ｍ；ｄ＝１…Ｄ。　＝１班级ｃｍ在时间ｔｄ上教师ｓｋ的课程ｌｐ；０否则。　

③同一时间，一个教室不能同时有－ｆ－ｉ以上的课，记为　Ｒ３：　Ｒ３为：≤１　其中：ｎ＝１，．，Ｎ；ｄ＝１，．，Ｄ。　

＝１教室ｌｎ在时间ｔｄ由教师ｓｋ上课程ｌｐ；０否则。　

＋收稿日期：２ｏｏ７＿ｏ７・１２　作者简介：许楠（１９８３一），女，天津人，助教，研究方向：计算机软件工程。　

１０２　

维普资讯 http://www.cqvip.com 第２３卷（总第１７５期）　许楠：基于遗传算法的排课系统　（２）软约束条件　软约束条件是在排课过程中可以满足但又可以不完全　满足的约束条件，是排课过程中在满足硬约束条件的基础　上能尽量要求满足的约束条件，软约束条件会因不同的教　学情况而有所差异。通常也可以通过调节软约束条件的满　足程度而改变排课的效果，可以将一定要满足的软约束条　件转换为“硬约束条件”。＿ｌｊ　以下是排课过程中常用的软约束条件，也是本文中所　考虑的软约束条件。　（１）课程尽量安排在教学效果较好的节次。课程上课　的效果与上课的节次有密切的关系，在排课的过程中我们　应该尽量将课程安排在教学效果较好的节次中，用ｐｈ表示　第ｈ节次的教学效果系数；　（２）多学时课程的周次安排要错开。在实际的排课过　程中，一般对于每周多学时（≥４）的课程，应该能够尽量　将其隔天安排，才能保证有较好的教学效果，用ｑｔ（ｔ＝１，２，　３，４，５）表示一门课程安排隔天天数ｔ的教学效果系数；　（３）满足教师所提出的上课时间和地点的要求。课程　的主讲教师和课程有着对应的关系，我们将教师提出的上　课要求固化在其对应的课程上，用ｈｊ表示满足课程上课要　求的系数；　（４）当一个班的周总课时数需在某个数值范围内的要求。　三、排课问题的算法　１．算法分析　排课的冲突异常复杂，对于这些冲突的复杂度我们进　行分析。以下给出分析的过程。　过程１：将模型中的五个集合降维为一个给定四维空　间Ｖ（Ｓ，Ｔ，Ｒ，Ｃ），称之为：课表。　四维分别代表了：　Ｓ（教师）：全校所有课程的任课教师；　Ｔ（时问）：上课的时间段，每天分为１—２、３—４、５—６、７　—８、９—１０，总共五个时间段，每学期２０周，每周五天，合计　每学期有５００个上课时问段；　Ｒ（教室）：全校所有的可用教室，包括不同的教室属　性，如：教室大小、是否为多媒体或语音教室等等；　Ｃ（班级）Ｃｌａｓｓ：当前学期的所有教学班级，包括班级属　性，如：班级人数、是否合班。　过程２：在课表Ｖ中求解存在着子空间Ｌ，且Ｌ　过程３：在课表Ｖ中求解存在着四维向量ｌ（ｓｒ，Ｔｍ，　Ｒ，Ｃ），且ｌＥＬ，那么称ｌ为：课。　过程４：在课表编排过程中，对于Ｐ（１ｉ　Ｅ　ＶＡｌｊ　Ｅ　Ｌ，ｉ，ｊ　ＥＮ），ｌｉ（Ｔｒ，Ｔｍ，Ｒ，Ｃ）与Ｉｊ（Ｔｒ，Ｔｍ，Ｒ，Ｃ），没有冲突，认为　Ｖ是：有效课表。　通过对四维向量ｌｉ（Ｓｒ，Ｔｍ，Ｒ，Ｃ）与ｌｊ（Ｓｒ，Ｔｍ，Ｒ，Ｃ）　的简化。在排课过程中的所有关系情况ＴｍＲ＋Ｔｍ　ＲＣ。　那么：由过程１、过程２可以推导出，在课表空间中，恒　有ｆ（Ｔｒ，Ｔｍ，Ｒ，Ｃ），那么Ｖ就是有效的课表。最后为了简　化，再给出过程５。　过程５：在课表Ｖ中，对于ｌｉ（Ｓｒ，Ｔｍ，Ｒ，Ｃ）与ｌｊ（ｓｒ，　Ｔｍ，Ｒ，Ｃ），ｉ、ｊ　Ｅ　Ｎ，没有冲突，记为：ｌｉ，￣ｌｊ；对于Ｌｉ、Ｌｊ没有　冲突，记为：Ｌｉ￣Ｌｊ。　这样有对于Ｐ（１ｉ　Ｅ　ＶＡｌｊ　Ｅ　Ｌ），ｌｉ（ｓｒ，Ｔｍ，Ｒ，Ｃ）与ｌｊ　（ｓｒ，Ｔｍ，Ｒ，Ｃ），ｉ、ｊＥＮ，没有冲突，就可以得到Ｖ　Ｌ。　四、结束语　该模型与求解方法已在实际中得到应用，取得了较好的　效果。在使用遗传算法优化后排课算法的实际效率有极大的　提高。因此用遗传算法实现类似排课问题的最优解也是一种　比较简单实用的方法，收敛速度很快，时间段分配均匀。　但是在实际应用中也可能没有终止条件，目的是可以　依次提供不同的可行解以供使用者选择直到所有解给完或　者使用者终止。　如果只考虑最优解的问题，可以使用迭　代的适应度几乎不变作为终止条件或者规定迭代次数。值　得一提的是，有些实际问题的可行解可能是唯一的，比如教　学场地或教师资源紧缺的情况，更严重的是如果约束条件　太苛刻，甚至可能没有可行解，在此类情况下人工干预还是　有必要的。　参考文献：　［１］　陶滔，李赫男，熊正为．多维冲突在排课算法中的应　用［Ｊ］．华东地质学院学报．２００１，（４）：２５６～２５９．　［２］　吴志斌，陈淑珍，孙晓安．回溯算法与计算机智能排　课［ｊ］．计算机工程．１９９９，（３）：７９２８０１．　［３］　高喜玛，张萍．大学自动排课系统内核算法设计［Ｊ］．　南阳师范学院学报．２００３，（１２）．　［４］　张亚东，叶克江．高校计算机排课系统的设计与实现　［Ｊ］．郑州轻工业学院学报．２００３，（１２）．　［５］　董艳云，钱晓群，张字舒．基于课元相关运算的高校　排课算法［Ｊ］．西南交通大学学报．１９９８，（１２）．　（责任编辑：刘春林责任校对：林子）　

（上接第９６页）处理问题的方式也有所不同，借他山之石攻玉，　可以促进教师更有效地进行反思；二是教师与学生间通过对话　交流，直接了解学生的所思所想，对教学的需求、建议甚至意见，　把教学真正落实到“以学生为主体”上、为学生学习服务上。　四、结束语　教学是门艺术，也是一门遗憾的艺术，而科学、有效的　反思可以减少遗憾，使这门艺术真正发挥出其独特的魅力。　由于其在我国高等教育体系中特定的历史地位、培养功能、　社会效应和发展进程，大学英语教学自然受到广泛关注，大　学英语教学质量的提高也就得到普遍重视。大学英语教学　改革是一个系统工程，涉及面广，改革成效自然与大学英语　教师的努力有直接联系。成功的大学英语教师应当是也必　

定是反思的实践者，是积极进取、永远向前、敢于尝试、不断　完善的行进者，而不是墨守成规、固步自封的教书匠。大学　英语教师只有不断实践、不断反思，才有不断创新，专业化　水平才可能不断提升，步人新境界。　参考文献：　［１］　教育部高等教育司．大学英语课程教学要求［Ｓ］．上　海．上海外语教育出版社，２００４．　［２］　束定芳、庄智象．现代外语教学一理论与实践［Ｍ］．　上海：上海外语教育出版社，１９９６年，１６７．　［３］　吕洪波．教师反思的方法［Ｍ］．北京．教育科学出版　社，２００５．　（责任编辑ｉ刘春林责任校对：林子）　】０３