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

时间：2025-04-04

系统资料

维普资讯

第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排课流程 .

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