基于贪心法和禁忌搜索的实用高校排课系统

时间:2025-04-02

系统资料

维普资讯

第2 7卷第 1 1期20 0 7年 1 1月文章编号:0 1— 0 1 2 0 ) 1 2 7— 4 10 9 8 ( 0 1— 8 3 0 7

计算机应用Co u e mp t rApp ia in lc t s o

Vo I 7 No. 1 l2 1No . 2 0 v 07

基于贪心法和禁忌搜索的实用高校排课系统王伟余利华, (1浙江医学高等专科学校基础部,杭州 305; 2浙江大学计算机学院,杭州 302 . 10 3 . 10 7)f e@z .d .n p t yh 6 .o i j eu c; ee l@1 3 cm) w w u r

摘要:在深入分析普通高校排课的流程、点和难点的基础上,出一个基于贪心法和禁忌搜特提索的排课算法。算法采用基于优先级的贪心法构造排课的初始解,而利用禁忌搜索获得全局较优进的排课结果。设计中充分考虑了当前高校课表问题的实际情况,如课程性质对排课的要求、师的特教殊要求等。实现的原型系统同时支持自动排课和交互式排课,于一些难度较大的问题,j对 - ̄通过人 . -机交互方式来解决。通过对高校的实际排课数据进行测试,果表明该算法可行且能够有效地提高结排课效率。

关键词:排课;先级;心法;优贪禁忌搜索 中图分类号: P 8文献标识码: T 11 AI t r c i e tm e a i pp o c a e n g e dy m e ho nd t bu s a c n e a tv i t bl ng a r a h b s d o r e t d a a e r hW ANG e YU ih a W i. L. u

f .Dp r etfB e h agMei l o ee 1 eat n ̄i m o,Z e n dc lg,HaghuZ eag30 5,C i; i f aC l nzo h in 10 3 hn j a 2 ol e o p t c ne h ag U i rt,H nzo h in 10 7 hn ) .C lg C m ue Si c,Z e n n e i e o f r e i f v sy aghuZ ea g30 2,C i j aAb ta t s r c:U ie st t t b ig i a w d l s d NP h r p i z t n p o lm,h n ef dn ih q ai i tb e i n v ri i a l i ey u e ad o

t y me n s miai rb e o e c n i g ah g u l y t i t me a l s a c a e gn o k h l n i g w r .Th ad a d s f c n t i t o n v ri i t l g p o lm r n y e, a d t e n i tr ci e l e h r n ot o sr n s f u i e t t a s y mea i rb e wee a a z d b n l n h n a n ea t v t tb i g s se b s d o re y meh d a d tb e r h w s p o o e . Gr e y meh a s d t o s u ta n t i a l y tm a e n ge d t o n a u s a c a r p s d me n e d t o w s u e o c n t c n i i a d r i l s l t n a h rt p a e a d t u s a c a s d t n p i l t t l t t e s c n h e Th rt tp s ou i tt e f h s n a e r h w o i s b s u e o f d a o t i n ma i a e a h e o d p a . me b s e p o oy e i i lme td a d te e p rme t e u t s o h t h p r a h i b t rc ia n f c e t mp e n e n h x e i n a r s l h w t a e a p o c s o h p a t l a d e ii n . l s t c Ke r s i tb ig y wo d:t mea l;p o t;g e d t o; tb e r h n d f y r e y me h i d a u sac

0引言 课表问题是调度问题的一种。Wr e n在 19 9 6年将课表问

合相较于单一的启发式算法,以提高搜索效率和生成课表可的质量。

本文提出了一个基于优先级的贪心法和禁忌搜索的排课算法,并利用该算法构建原型系统。我们基于课程的优先级利用贪心法构造初始课表,可以大大提高初始课表的质量。 进而采用禁忌搜索调整课表的合理性。在设计中选择禁忌搜索主要是基于以下考虑:禁忌搜索的效率较高;禁忌搜索有较

题描述为:将资源按照约束条件安排进有限的时间和空间内,并满足特定的目标和最大的扩展性“。国内外对课表问题 做了大量的研究,出了多种可行

的解决方案,实际应用的提但情况并不理想。尽管目前大多数高校都有自己的排课系统,

实现了资源的统一规划,然而,计算机自动排课的结果往往无法满足实际需要,课表编排仍然以手工为主。 课表问题的复杂性主要源于需要满足大量的约束条件。

强的爬山能力,以跳出局部最优解,向解空间的其他区域可转寻找最优解;禁忌搜索的人机交互性较强,以随时中断进行可人工干预。解决课表问题的多种研究和实践证明,禁忌搜索

这些约束条件包括课表的冲突问题、授课时段的限制、教室资源问题等。为了编排出更为合理的、性化的课表,课过程 人排

具有较高的搜索效率和较好的全局最优解 J。

中还需要考虑课程性质、教师连排要求等。由于各个学校情况不同、约束条件和评价最优解的标准也有较大的差距。给排课算法的设计带来了困难。 课表问题被证明是一个多资源约束的 N P难题,有任没

1排课流程及要求 1 1排课流程 .

高校的排课问题有如下特点:课程可以是小班教学也可

以是不同专业合班;同一个教师可以讲授多门不同的课程:每次授课节次为连续的 2节或 3节;学生上课的教室不固定。

何算法可以保证在多项式时问内找到最优解 j因此在实。际应用中,常采用启发式算法来获得近似最优解。这些通

图1借鉴浙江大学学分制下的排课经验,描述了基本的排课流程和每个流程生成的课表数据。 阶段 1下发教学计划。学校将教学计划下发到各开课:

启发式优化算法包括:模拟退火算法、禁忌搜索、遗传算法等。其中禁忌搜索模拟人类的智力过程,对局部邻域搜索的扩是

展,在搜索过程中标记已搜索到的局部最优解,并在进一步的迭代搜索中尽量避开这些对象。研究表明多种启发式算法结收稿日期:0 7— 5—1修回日期:07— 7—1。 20 0 6; 20 0 8

学院( )下发的数据是课程信息和计划学生人数信息。系, 阶段 2落实教学任务。各学院 ( ):系根据自身的资源情

作者简介:王伟 (9 1一)女, 18,内蒙古乌兰察布人,硕士,主要研究方向:高性能计算、网格计算、能计算;余利华 ( 9 2一)男,江温岭 …… 此处隐藏:10195字,全部文档内容请下载后查看。喜欢就下载吧 ……

基于贪心法和禁忌搜索的实用高校排课系统.doc 将本文的Word文档下载到电脑

    精彩图片

    热门精选

    大家正在看

    × 游客快捷下载通道(下载后可以自由复制和排版)

    限时特价:7 元/份 原价:20元

    支付方式:

    开通VIP包月会员 特价:29元/月

    注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
    微信:fanwen365 QQ:370150219