基于贪心法和禁忌搜索的实用高校排课系统
时间:2025-04-02
时间: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字,全部文档内容请下载后查看。喜欢就下载吧 ……