（计算机软件与理论专业论文）智能排课算法的研究及实现.pdf

1 3 l 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 张华 日期：p 归! 午! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：毯竺导师签名： 广 务- 第1 章引言1 1 1 研究背景1 1 2 研究历史及现状2 1 3 本文主要工作4 1 4 本文组织结构5 第2 章问题描述及解决思路6 2 1 排课问题分析6 2 2 常用排课算法7 2 2 1 模拟退火算法8 2 2 2 遗传算法8 2 2 3 回溯算法j 9 2 2 4 蚁群算法1 0 2 2 5 贪心算法1 0 2 3 解决思路1 1 2 3 1 选择贪心算法的原因“1 1 2 3 2 解决思路1 3 第3 章排课问题模型的建立1 4 3 1 符号规定1 4 3 2 冲突建模1 5 3 3 目标函数定义1 6 3 3 1 多目标优化1 6 3 3 2 排课问题的多目标函数1 7 第4 章基于贪心思想的智能排课算法2 1 4 1 历史排课信息学习2 1 4 2 数据预处理2 2 4 3 自动排课算法2 5 山东大学硕士学位论文 4 3 1 教室选择2 6 4 3 2 时间选择2 6 4 3 3 排课后处理2 8 4 4 解决“甩课”问题的方法2 8 4 4 1 “甩课 产生的原因2 8 4 4 2 解决方法2 9 4 5 排课结果评价3 0 4 6 手动调课3 1 4 7 实例求解分析3 2 4 7 1 实例说明3 2 4 7 2 历史信息学习3 3 4 7 3 自动排课结果分析3 4 4 7 4 “甩课”处理3 4 第5 章系统设计与实现3 5 5 1 系统环境及总体架构3 5 5 2 系统设计3 5 5 2 1 数据库设计3 5 5 2 2 功能设计3 8 5 3 系统实现3 8 5 4 系统实现3 8 5 4 1 基础数据维护4 1 5 4 2 智能排课和手动调课4 2 5 4 3 课表查询4 3 第6 章总结和展望4 4 6 1 总结4 4 6 2 进一步工作4 5 参考文献4 6 致谢5 0 攻读学位期间发表的学术论文5 l 攻读学位期间参加的主要科研项目5 2 、 1 j z 山东大学硕士学位论文 c o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h c h a p t e r1p e r f a c e 1 1 1r e s e a r c hb a c k g r o u n d 1 1 2r e s e a r c hh i s t o r ya n d o b j e c t i v e ：2 1 3m a i nc o n t r i b u t i o n 4 1 4c o n t e n t so r g a n i z a t i o n 5 c h a p t e r2p r o b l e md e s c r i p t i o na n ds o l u t i o n s 6 2 1a n a l y s i so f c o u r s e a r r a n g i n gp r o b l e m 6 2 2c o m m o nc o u r s e - a r r a n g i n ga l g o r i t h m 7 2 2 1s i m u l a t e da n n e a l i n ga l g o r i t h m 8 2 2 2g e n e t i ca l g o r i t h m 8 2 2 3b a c k t r a c k i n ga l g o r i t h m 9 2 2 4a n t c o l o n ya l g o r i t h m 1 0 2 2 5g r e e d ya l g o r i t h m 1 0 2 3s o l u f i o n s 11 2 3 1r e a s o n so f g r e e d ya l g o r i t h ms e l e c t i o n 1 1 2 3 2s o l u t i o n s 1 3 c h a p t e r3c o u r s e a r r a n g i n gp r o b l e mm o d e l l i n g 1 4 3 1s t i p u l a t i o no f s y s b o l s 1 4 3 2c o n f l i c tm o d e l l i n g 1 5 3 3d e f i n i t i o no f o b j e c t i v ef u n c t i o n 1 6 3 3 1m u l t i o b j e c t i v eo p t i m i z a t i o n 1 6 3 3 2m u l t i - o b j e c t i v ef u n c t i o no fc o u r s e - a r r a n g i n gp r o b l e m 。1 7 c h a p t e r4i n t e l l i g e n tc o u r s e - a r r a n g i n ga l g o r i t h mb a s e do ng r e e d yt h e o r y 2 1 4 1s t u d yo f h i s t o r i c a ld a t a 2 1 4 2d a t ap r e p r o c e s s i n g 2 2 4 3a u t o m a t i cc o u r s e a r r a n g i n g 2 5 j k 山东大学硕士学位论文 4 3 1r o o ms e l e c t i o n 2 6 4 3 2t i m es e l e c t i o n 2 6 4 3 3p r o c e s s i n ga f t e rc o u r s e - a r r a n g i n g 2 8 4 4s o l u t i o n so f “c o u r s es k i p p e d p r o b l e m 2 8 4 4 1r e a s o n so f c o u r s es k i p p e d p r o b l e m 2 8 4 4 2s o l u t i o n s 2 9 4 5r e s u l t se v a l u a t i o n 3 0 4 6m a n u a lc o u r s e a d j u s t i n g 3 1 4 7c a s es t u d y 3 2 4 7 1c a s ed e s c r i p t i o n 3 2 4 7 2s t u d yo f h i s t o r i c a ld a t a 3 3 4 7 3e v a l u a t i o no fa u t o m a t i cc o u r s e a r r a n g i n gr e s u l t s 3 4 4 7 4t r e a t m e n to f “c o u r s es k i p p e d p r o b l e m 3 4 c h a p t e r5s y s t e md e s i g na n di m p l e m e n t a t i o n 3 5 5 1s y s t e me n v i r o n m e n ta n df r a m e w o r k 。3 5 5 2s y s t e md e s i g n 3 5 5 2 1d a t a b a s ed e s i g n 3 5 5 2 2f u n c t i o nd e s i g n 3 8 5 3s y s t e mc l a s sd i a g r a m 3 8 5 4s y s t e mi m p l e m e n t a t i o n 3 8 5 4 1b a s i cd a t am a i n t e n a n c e 4 1 5 4 2i n t e l l i g e n tc o u r s e a r r a n g i n ga n dm a n u a lc o u r s e - a d j u s t i n g 4 2 5 4 3t i m e t a b l ei n q u i r y 4 3 c h a p t e r6c o n c l u s i o n s 4 4 6 1w o r ks u m m a r y 4 4 6 2f u t u r ew o r k 4 5 r e f e r e n c e s 4 6 a c k n o w l e d g e m e n t 5 0 p u b l i s h e dp a p e r s 5 1 p r o j e c t sp a r t i c i p a t e df o rt h em a s t e r sd e g r e e 5 2 i v ，鼻 j】 山东大学硕士学位论文 摘要 课表的编排是高校教务活动中非常重要的工作之一，是保证教学秩序正常进 行的前提和基础。目前大多数院校的排课主要采用手工编排方法，但是随着高校 招生规模的扩大，教学资源变得严重不足，教学资源的利用率也日益被重视起来， 同时办学形式的多样化及排课涉及面广、约束条件多等各类复杂要求使得手工排 课已经无法完成，因此借助计算机辅助排课成为一种解决手段。如何利用计算机 快速、有效地编排出合理、满意的课表，是一项值得研究的工作，也吸引了国内 外一大批研究人员对其进行深入研究。然而，在实际应用中，由于排课问题是一 个n p 完全问题，开发出符合要求的排课系统是一件难事，迄今为止，国内尚没 有用户普遍反映良好的计算机自动排课系统。 本文通过分析课表制定的原则和要求，依据我校排课的实际需求，建立了排 课问题的多目标组合规划模型，提出了基于贪心思想的智能排课算法。模型通过 将无冲突的硬性条件作为约束条件，将一些合理性、适应性原则作为优化目标， 采用多目标优化的理论进行求解。本文提出的智能排课算法通过分析历史排课数 据，利用全概率计算公式，将得到的排课规律应用到自动排课过程中，使得到的 排课结果更加合理。在自动排课过程采用了优先级的思想，根据用户定义的或依 照一定规则计算出的优先级顺序进行课程安排，算法分成教室选择和时间选择两 个阶段，按照贪心算法的思想，针对每次选定的教室和时间计算其目标函数，根 据多目标优化的理论选择当前最优解进行课程安排。 针对排课过程中出现的“甩课”问题，本文提出了一个无回溯的简单调整算 法，通过搜索出要安排“甩课”任务可能需要取消的任务集合，结合用户决策， 取消某些任务安排即降低其安排的优先级，然后重新利用自动排课算法进行“甩 课”任务安排。用户的参与避免了产生不合理的调整结果，该算法可以在无回溯 的情况下有效的解决“甩课”问题。 最后，本文通过实验详细介绍了智能排课算法过程，证明了通过该算法产生 的排课结果是正确的，并且可以较好的满足课程、教师等约束条件，有效的利用 教室资源。在此基础上，本文设计实现了一个排课系统，对系统的数据库结构、 功能结构等进行了详细的分析和设计。 l 山东大学硕士学位论文 本文提出的智能排课算法及在此基础上设计实现的排课系统，具有较高的理 论和应用价值，系统提供了良好的交互方式，产生的课表在一定程度上可以满足 合理性及用户的满意度要求。目前，本文提出的排课算法已在考试编排和课程编 排中开始试用，并取得了较好的结果。 关键字：智能排课算法；多目标优化；贪心算法；历史信息学习：全概率 i i t l ii 东大学硕士学位论文 a b s t r a c t c o u r s e a r r a n g i n gi so n eo ft h ei m p o r t a n tw o r k si nc o l l e g ea c a d e m i ca c t i v i t i e s ；i t i st h ep r e m i s ea n df o u n d a t i o ni ne n s u r i n gt h en o r m a lt e a c h i n gp r o c e s s n o w , m a n u a l c o u r s e - a r r a n g i n gm e t h o d si sm a i n l yu s e di nm o s tc o l l e g e s ，b u t 谢mt h ee x p a n s i o no f c o l l e g ee n r o l l m e n t , t h e r ei sas e r i o u ss h o r t a g eo ft e a c h i n gr e s o u r c e sa n dt h et e a c h i n g r e s o u r c eu t i l i z a t i o ni sa l s oi n c r e a s i n g l yb e i n gt a k e ns e r i o u s l y , a l s oa l o n gw i mt h e d i v e r s i f i c a t i o no fs c h o o lr u n n i n gf o r ma n dv a r i o u sk i n d so fr e q u i r e m e n t si nt h e p r o c e s s i n go fc o u r s e - a r r a n g i n g ，s u c ha sw i d er a n g e ，m u l t i c o n s t r a i n t sa n ds oo n ，t h e m a n u a lc o u r s e - a r r a n g i n gm e t h o db e c o m e su n p r a c t i c a l l y t h e r e f o r e ，as o l u t i o nu s i n g c o m p u t e ri nc o u r s e - a r r a n g i n gp r o c e s s i sb e e nc o n s i d e r e d i ti saw o r t hs t u d y i n gw o r k i nr e s e a r c h i n gh o wt oa r r a n g i n gar e a s o n a b l ea n ds a t i s f a c t o r yc o u r s et i m e t a b l eq u i c k l y a n de f f i c i e n t l yu s i n gc o m p u t e r , w h i c ha t t r a c t e sal a r g en u m b e ro fr e s e a r c h e r sa th o m e a n da b r o a d b u ti ti sd i f f i c u l tt od e v e l o pac o u r s e a r r a n g i n gs y s t e ma c c o r d i n gt ot h e r e a la p p l i c a t i o n s of a r , t h e r ei sn o ty e ta na u t o m a t e dc o u r s e a r r a n g i n gs y s t e mw i t h g o o du s e r - r e f l e c t i n g i nt h i sp a p e r , t h r o u g ha n a l y z i n gt h et h ep r i n c i p l e sa n dr e q u i r e m e n t so fc o u r s e a r r a n g i n g ，a c c o r d i n gt o t h ea c t u a l r e q u i r e m e n t s i n 0 1 1 1 s c h o o l ，w eb u i l da m u l t i o b je c t i v e c o m b i n a t o r i a l p r o g r a m m i n g m o d e la n dp r o p o s ea n i n t e l l i g e n t c o u r s e a r r a n g i n ga l g o r i t h mb a s e do ng r e e d yt h e o r y i nt h em o d e l ，w et a k et h e c o n f l i c t - f r e eh a r dc o n d i t i o n sa sc o n s t r a i n t sa n ds o m er a t i o n a l ，a d a p t i v ep r i n c i p l e sa s o p t i m i z a t i o no b je c t i v ea n ds o l v ei tu s i n gm u l t i - o b je c t i v eo p t i m i z a t i o nt h e o r y i nt h e c o u r s e a r r a n g i n ga l g o r i t h mp r o p o s e di nt h i sp a p e r , w ef i n dt h er e g u l a r i t i e si nc o u r s e a r r a n g e m e n tb ya n a l y z i n gt h eh i s t o r i c a ld a t au s i n gt o t a lp r o b a b i l i t yf o r m u l a ，w h i c h c a nb ea p p l i e dt ot h ea u t o m a t e dc o u r s e a r r a n g i n gp r o c e s st om a k et h er e s u l tm o r e r e a s o n a b l e t h et h e o r yo fp r i o r i t yi su s e da n da l lc o u r s e sa r ea r r a n g e da c c o r d i n gt o t h ep r i o r i t yd e f i n e db yt h eu s e r o rc a l c u l a t e d a c c o r d i n gt o c e r t a i nr u l e s t h e a l g o r i t h mp r o c e s si sd i v i d e di n t ot w op a r t s ：r o o ms e l e c t i o na n dt i m es e l e c t i o n ，i n a c c o r d a n c e 、析mt h et h e o r yo fg r e e d ya l g o r i t h m , w ec a l c u l a t et h eo b je c t i v ef u n c t i o n v a l u ef o re a c hs e l e c t e dr o o ma n dt i m e ，a n dt h e nt a k et h ec u r r e n to p t i m a ls o l u t i o nf o r c o u r s ea r r a n g i n ga c c o r d i n gt ot h et h e o r yo fm u l t i o b j e c t i v eo p t i m i z a t i o n t h eo p t i m a l i i i 矗j 山东大学硕士学位论文 s o l u t i o nt os e l e c tt h ec u r r e n tc u r r i c u l u m f o rt h e “c o u r s es k i p p e d p r o b l e ma p p e a r e di nt h ec o u r s e - a r r a n g i n gp r o c e s s ，w e p r e s e n tas i m p l ea d ju s t m e n ta l g o r i t h mw i t h o u tb a c k t r a c k i n gi nt h i sp a p e r b y s e a r c h i n go u tt h et a s kc o l l e c t i o nw h i c hn e e d e dt ob ec a n c e l e dp o s s i b l yi no r d e rt o a r r a n g et h es k i p p e dc o u r s e ，w ec a n c e lt h ea r r a n g e m e n t so fs o m et a s k sa c c o r d i n gt o t h eu s e r sd e c i s i o nt h a tm e a n sr e d u c et h e i rp r i o r i t y , a n dt h e nr u nt h ea u t o m a t e d c o u r s e - a r r a n g i n ga l g o r i t h ma g a i nf o rt h e c o u r s es k i p p e d t a s k s t h i sa l g o r i t h m r e d u c e st h en u m b e ro f c o u r s es k i p p e d a tt h ee x p e n s eo fl o w - g o o d n e s sc o u r s e a r r a n g e m e n tr e s u l t ，a n du s e r sp a r t i c i p a t i o na v o i d st h eu n r e a s o n a b l ec o u r s e a r r a n g i n g r e s u l t s ，i tc a ns o l v et h e “c o u r s es k i p p e d ”p r o b l e me f f e c t i v e l yw i t h o u tb a c k t r a c k i n g f i n a l l y ，w ed e s c r i b et h ep r o c e s so fi n t e l l i g e n tc o u r s e - a r r a n g i n ga l g o r i t h mi n d e t a i lt h r o u g he x p e r i m e n t s i ti sp r o v e dt h a tt h ec o u r s et i m e t a b l eg e n e r a t e db yt h i s a l g o r i t h mi st r u ea n dc a nb e t t e rm e e tt h ec o n s t r a i n t so fc o u r s e s ，t e a c h e r s ，a n ds oo n o nt h i sb a s i s ，w ed e s i g na n di m p l e m e n ta c o u r s e a r r a n g i n gs y s t e mi nt h i sp a p e r , a n d g i v ead e t a i l e da n a l y s i sa n dd e s i g no ft h es y s t e md a t a - s t r u c t u r e ，s y s t e mf u n c t i o na n d s o o n t h ei n t e l l i g e n tc o u r s e a r r a n g i n ga l g o r i t h ma n ds y s t e md e s c r i b e di n t h i sp a p e r h a v es o m ed e g r e eo ft h e o r e t i c a la n dp r a c t i c a lv a l u e t h es y s t e mw ed e s i g n e da n d i m p l e m e n t e dp r o v i d e sag o o di n t e r a c t i v ew a y , a n dt h ec o u r s et i m e t a b l eg e n e r a t e db y t h es y s t e mi sr e a s o n a b l ya n du s e rs a t i s f a c t i o nt oac e r t a i ne x t e n t a tp r e s e n t , t h e c o u r s e 。a r r a n g i n ga l g o r i t h mh a sb r o u g h ti n t oe f f e c ti ne x a ma n dc o u r s ea r r a n g i n g p r o c e s sa n da c h i e v e dg o o d r e s u l t k e yw o r d s ：i n t e l l i g e n tc o u r s e - a r r a n g i n ga l g o r i t h m ：m u l t i o b j e c t i v e o p t i m i z a t i o n ；g r e e d ya l g o r i t h m ；s t u d yo fh i s t o r yd a t a ；t o t a l p r o b a b i l i t y t li 东大学硕士学位论文 懈 第1 章引言 吨1 1 研究背景 “ 排课是高校教学管理中一项重要而复杂的基本工作，实质上它是将书面的教 学计划通过课程表实现的过程。排课是为学校所开设的课程安排一组适当的教学 空间与时间，使整个教学活动有计划有秩序的进行，保证教学质量。目前，大多 数院校主要采用手工排课的方法，一般是由经验丰富的教务人员在学期末依据教 学计划集中时间和精力进行编排，这是一项繁重复杂的调度工作，主要是依靠人 长年积累的经验知识来完成的。排课实际过程中涉及教师、学生、资源分配和班 级合班、拆班上课等复杂情况，另外在课程安排结束之后，往往由于特殊原因不 得不进行课表调整。所有诸如此类因素，使得排课工作量大，时间周期长，排出 的课表不易调整。 随着我国教育体制改革的深入进行， 逐年增长，手工排课的缺点越来越突出， 以及高校扩招引起的学生、教师规模的 高校班级人数的增多与教师资源、教学 空间、仪器设备等的矛盾日益显现。近几年计算机在教学管理工作中得到了广泛 的应用，如何利用计算机实现劳动强度大、工作效率低的手工排课工作，成为教 学管理人员和计算机专家共同面临的一个难题。用计算机辅助进行课程表的编排 能够很快的得到满足约束条件的可行性结果，具有时间短、节约人力资源、质量 高和出错少等优点，它不但可以把教务人员从繁杂的排课任务中解脱出来，而且 对现代化高校教学、科研和管理建设有着重要的推动作用，使学校教务管理工作 现代化程度进一步提高。 计算机排课是通过把排课问题转化为有约束的时空组合优化问题来进行求 解的，它将每个时间片和教室空间组合成不同的时空块，根据排课的基本约束规 则对每个教学计划进行时空组合块的分配，得到的分配组合安排方案，必须在 目标空间中表现出良好的满意度，这些满意度往往不仅多个，而且通常包含很多 人为的因素并具有一定的模糊性。利用计算机来模拟手工排课工作，可以抽象出 问题中的各个要素进行建模，并根据课表的形式和安排规律，缩减问题空间的搜 索范围，呈现一定程度的智能化。手工排课时，信息的上通下达是极其麻烦的， l l f 东大学硕士学位论文 而采用计算机排课，教学信息可以一目了然，对于优化学生的学习进程，评估每 位教师的教学贡献，领导的合理决策等都具有重要的意义。计算机具有运算速度 快、批处理能力强等特点，在教学工作中得到了广泛的应用，因此采用计算机来 代替劳动强度大、工作效率低的手工排课，通过信息化手段来提高教务管理水平 是大势所趋。 综合上述，计算机排课是一个复杂的、难解的问题，同时它与教学管理关系 紧密，因此如何利用计算机安排出合理满意的课表越来越成为教学管理之中迫切 需要解决的研究课题之一。 1 2 研究历史及现状 排课问题也可称为课程时问表问题( c o u r s e t i m e t a b l i n gp r o b l e m ) ，是一个涉 及多因素的基于时间规划和组合优化的问题。1 9 6 2 年，g o t l i e b c c 教授就 对课程表问题进行了形式化描述【1 1 ，第一次将排课问题形式化描述为一系列规划 组合问题。到了7 0 年代，s e v e n 等人将排课表问题理论化【2 】，证明该问题是 一个n p 完全类问题( n p c o m p l e t ep r o b l e m ) 。根据计算理论的原理，到目前为止， 排课问题还不存在多项式时间算法，当问题的规模增大时，解的数目呈指数函数 增长，在一般的实际情况中是不可能准确地求出最优解的。由于该问题具有的难 度和挑战性，许多研究者在其中投入了大量精力，并取得了丰硕成果。 近4 0 年来，人们对计算机排课问题的算法、解的存在性等问题做出了很多 探索性的研究1 3 , 4 , 5 。随着算法复杂性理论的完善，人们不再强调一定要求得最优 解，而将更多的研究转向实际应用的角度。对于能够得到较好的解的近似算法， 或以一定的概率保证解的质量的随机算法的研究越来越受到重视，于是出现了崭 新的智能优化算法，诸如人工神经网络、遗传算法、蚁群算法、进化计算、模拟 退火、禁忌搜索及其混合优化策略等，还有研究者利用运筹中的分层决策思想及 图论方法【6 ，7 ，8 驯设计算法模型，另辟蹊径寻求解决之道。大部分算法都是使用加 权值或评价函数值的方法，进行只有人脑才能判断的满意程度的处理，遇到死锁 时一般也都进行回溯处理。在深入研究了各种算法的优劣之后，不少结合各算法 的综合思想被陆续提出，各算法之间取长补短，能更快地获得更优解。比如结合 模糊选择的思想，将专家系统引入排课系统的应用 1 0 】；s a f a a id ，s i g e r oo 提出 2 焰 强 山东大学硕士学位论文 的遗传算法结合控制约束的思想【1 1 1 。但是总的来说，课表问题的研究还处于相当 初级的阶段，这与课表问题属于n p c 问题有密切关系，什么时候p c 问题的研 究有了突破性进展，课表问题也能随之出现质变的算法。 伴随着计算机的普及和教育信息化的发展，国内外有不少教务系统相继被开 发。在国外，比较有代表的有印度v a s t a p u r 大学管理学院的a r a b i n d at r i p a t h y 、 加拿大m o n t r e a l 大学的j e a na u b i n 和j a c q u e sf e r l a n d 等n 2 , 1 3 , 1 4 。a r b a i n d at r i p a t h y 是针对以“人”为单位的情况进行课表编排的，他运用格拉朗日松弛法和分支定 界技术进行问题的求解，通过人为造成课程间的冲突来减少变量的个数。加拿大 m o n t r e a l 大学的j e a na u b i n 和j a c q u e sf e r l a n d 等人则把排课问题划分为两个子问 题：时间表问题和分组问题。在时间表问题中，根据学生的注册情况，教师和教 室的可利用情况形成一个主时间表。对于选课人数较多的大课，一个星期要分成 几个时间段来上，分组问题就是将学生分给各时间段。两个问题相关联，通过惩 罚因子来构造启发函数。国外的研究表明，解决大规模的排课问题单纯靠数学方 法是行不通的，可以考虑利用运筹学中分层规划的思想，将问题分解后再求解。 从8 0 年代初期开始，国内也出现了很多对排课问题的研究，并设计出了很多排 课系统，具有代表性的有：南京工学院的u t s s ( a u n i v e r s i t yt i m e t a b l es c h e d u l i n g s y s t e m ) 系统，清华大学的t i s e r ( t m a e t a b l es c h e d u l e r ) 系统，大连理工大学的智 能教学组织管理与课程调度等，这些系统大多数都是以“班”为单位，通过模拟 手工排课过程，运用启发式函数来进行课表编排的，这些系统往往比较依赖于各 个学校的教学约束条件，不宜进行大量推广【l5 1 。 从实际使用的情况来看，国内外开发的这些排课系统在实用性、通用性上仍 不尽如人意，且都需要借助人工辅助。一方面作为一个复杂的系统，现实世界中 的课表安排问题常常需要考虑许多约束条件，必须考虑到个人的特殊情况和政策 管理的规定等，这些约束要想考虑的面面俱到是一件很困难的事；另一方面课表 问题的复杂度特别大，再加上各高校的教学模式和资源不同，约束也存在很大的 差异，自动排课软件针对性都较强，无法普遍适应于各个高校。同时，调度过程 中的一个很小的变动，都可能会引起全部课程安排结果的大调整，这意味着全校 课程大变动，在实际的应用中这是很难实现的事。这些难点说明，别人的成功案 例只是较好解决了他们特定情况下的某一类问题而已，研究高效的、灵活的符合 l 【i 东大学硕士学位论文 我校实际情况的排课系统是具有现实意义的。 1 3 本文主要工作 本文通过对排课问题的分析，得到问题的复杂因素和约束条件，并在比较了 目前存