大学课程表问题的模型与算法

1、第 28 卷 第 1 期2005 年 2 月鞍 山 科 技 大 学 学 报jo ur nal of anshan u niversit y of science and technologyvol . 28 no . 1feb. ,2005大学课程表问题的模型与算法焱1 ,2 ,王莉1 ,李大卫1 ,张庆灵2熊( 1 . 鞍山科技大学 理学院 ,辽宁 鞍山 114044 ;2 . 东北大学 理学院 ,辽宁 沈阳 1110006)摘要 :课程表问题 ( timetabling p roblem ,简称 t tp) 是时间表问题之一 ,也是 n p 难问题 。根据大学授课形式的特点建立了大学课程表

2、问题的数学模型 ,并给出了求解该问题的遗传算法 。为了提高解的质量和加快收 敛速度 ,当相同时间段内班级重复出现时 ,给出了寻找可能的新位置的方法 ,并将其嵌入遗传算法 ,实验结果表明该方法是可行和有效的 。关键词 :课程表问题 ;模型 ;遗传算法 ; n p 难问题中图分类号 :o22114 文献标识码 :a 文章编号 :167224410 (2005) 0120026204课程表编排问题是 t tp 问题之一 , even 等人1 证明了 t tp 问题是 n p 难问题 。课程表编排问题是一个解决时间和空间资源矛盾的多因素优化决策问题 ,即对班级 、教师 、时间 、课程 、教室等五个相互

3、 制约的基本因素进行时空安排问题 。这种安排问题需要满足一定的约束条件集 ,如关于教室的位置与 容量 、时间间隔 、特定课程承接关系等方面的约束条件 。目前各类学校都存在着学生数量 、课程设置增 多 ,而相应的配套硬件资源没有太大变化的情况 。这就要求能利用已有的资源 ,选择最合理的课程表编排方案 。近 40 年来 ,人们尝试着用各种方法求解此问题 ,如整数规划 ( integer linear p ro gramming) 2 、图着色 ( grap h coo ring) 3 、各种推理搜索方法4 、进化算法 ( evolutio nary co mp utatio n) 5 ,等等 。本

4、文针对大学课程表编排问题的特点建立了问题模型 ,并引入文献 6 中方法求解 。在求解过程中 为了提高解的质量和加快收敛速度提出了最佳时段2查找法 ,实验结果说明了该方法的可行和有效 。1 大学课程表编排问题111问题的描述本文讨论的大学课程表问题描述如下 : 设有 m 位教师 , n 个班级 , p 门课程 , t 个允许上课的时间 段 。课程表问题就是将这 p 门课程安排到 t 个允许上课的时间段上 , 并使 m 位教师 , n 个班级满足如下约束 。“硬”约束 ,即可行课程表必须满足的约束条件 ,如果某个约束不能满足则不能作为可行的课程表 : (1) 一个教室不能同时安排两个以上的教师上课

5、 ; ( 2) 一个教师不能同时上两门课 ; ( 3) 一个班级不能同时上两门课 。“软”约束 ,即希望所采用的课程表编排方案尽可能多的满足约束 ,虽然这些约束不满足时仍是可实 行的课程表 。但满足“软”约束条件越多则课程表编排越合理 。满足所有“软”约束课程表编排方案是最 优方案 。不同类型的学校对各种“软”约束条件的要求各不相同 ,其中最基本的是对上课密度的要求 ,即 同一天或相邻天不上相同课程 。112问题的数学模型大学课程表问题具有如下特点 :上课时间长 (两小节合为一大节) ;允许上合班课 ( 多个班级参加同收稿日期 :2004211212 。作者简介 :熊焱 ( 1973 - )

6、,女 ,辽宁辽阳人 ,讲师 。一门课的学习) ;同一位教师可以担任多门课的教学任务 ,也可以给多个班级上课 ;每门课程有固定的周上课次数 。建模时将不同教师上的相同名称课程记为两门课 ;同一位教师在不同时间上的相同名称课 程记为两门课 。为了便于建立问题数学模型定义如下记号 : (1) 教师集合 f = f 1 , f 2 , f m ; ( 2) 班级集合 c =, cn ; ( 3) 课程集合 l = l 1 , l 2 , l p , 不同教师上相同名称课程记为两门课 , 同一位教师 c1 , c2 ,给不同合班上的相同课程记为两门课程 , n ( l ) 表示 l 课的上课次数 ; (

7、 4) 一星期内可上课的天数集合 d, t r ; ( 6) ( d k ) 表示 d k 天的起始时间段数 ,( d k )= d1 , d2 , d k ; ( 5) 时间段集合 t= t 1 , t 2 ,表示 d k 天的终止时间段数 。引入变量 x f lct 取值如下10f 教师在 t 时间段给 c 班级上 l 课其他x f lct=以各班级每门课的上课时间安排具有足够的分散度为优化目标建立数学模型( dk)mpknmin 1 ( x f m l p n r x f m l p n rc t )+c tm = 1 p = 1 k = 1 r r =( dk) n = 1( d )(

8、 d )kk +1mp k- 1n2 ( x f m l p n r x f m l p n rc t )( 1)c tm = 1 p = 1 k = 1 r =( dk) r=( dk +1) n = 1pmx f m l p c t( 2)s. t.1 c tctm = 1 p = 1pnx f l pcnt1 f f t t( 3)p = 1 n = 1mrnx f m lcnt r l mc c=n ( l ) lt t( 4)m = 1 r = 1 n = 1= 0 , 1f fl lx f lct式 (1) 中第一个加和因子表示同一天中同一门课重复上的次数的总和 ;第二个加和因子表

9、示相邻天中同一课重复上的次数总和 ;式 (2) 表示任何时间段内每个班级最多只能上一门课 ;式 (3) 表示任何时间段内 每位教师最多只能上一门课 ;式 (4) 表示有同一门课的班级能同时上课 ,每门课的周上课次数符合规定次数 ,即没有漏排课程 。其中 1 、2 为惩罚系数 , 因邻天上课效果好于同天上课效果 , 故 1 2 。2 遗传算法求解课程表问题211遗传算法的基本原理7(1) 随机产生一个由确定长度的特征串组成的初始群体 ; (2) 对串群体迭代地执行 : 计算群体中 每个个体的适应值 ; 应用复制 、交换和变异算子产生下一代群体 ,直到满足停止准则 ; ( 3) 把在任何 一代中出

10、现的最好的个体串指定为遗传算法的执行结果 。212编码及染色体表示采有文献 7 中编码表示 。213初始群体的产生随机的将每一位教师所上的课程安排到所在的行中 ,然后组合为二维表 x m , r , 这样就生成了 一个个体 。重复操作 , 直到达到群体规模 f 。所生成的个体包含了全部班级的所有课程 , 每位教师所上课1, 其中 0 ,3同时段内教师重复出现的次数总和 , 适应值函数 f ( x i ) =g ( x i ) + 3 ( q1 i + q2 i ) + 1为惩罚系数 , 若 f ( x 3 ) = 则找到了优化过程的最优值 x 3 。215遗传操作( 1) 复制算子 :采取轮盘

11、选择 。设复制概率为 p r 。( 2) 交叉算子 :采取多行交叉 。设交换概率为 pc 。具体步骤如下 : 随机的选择轮盘选择中产生两 个体 ; 随机的产生 1 , m 之间的随机数确定交换点 ; 交换交换点以下 j 行 , 其中 j 为取定数值 1 j m 。若随机点以下行数小于 j , 则全部交换 。( 3) 变异算子 :设变异概率为 p m 。具体步骤如下 : 随机的取 4 个随机数 i 1 , m , j 1 , j 2 1 ,r , k 1 , f 分别表示行值 、时间段 、个体位置 ; 交换个体 k 中第 i 行以下的 j 1 、j 2 时间段的位置 。216最佳时段2查找法为了

12、提高解的质量和加快收敛速度提出了最佳时段2查找法 ,即为每个时间段内重复出现的班级及 每天重复出现的课程寻找可能的新位置 ,使得课表编排的更加合理 。具体步骤如下 。(1) 同时段内矛盾班级最佳时段2查找法 : 选定执行操作个体 。 逐行向下查找重复上课的课程位置 ,如果找到执行 到 。 选定其中没执行过 课程位置执行 为其查找新位置 。 在选定 课程所在位置的同行上寻找即没有该门课程 ,又没有该课程班级矛盾的时间段 ;如果找到了新的时间段执行 ,否则返回 。 将选定课程移到新的时间段所在的同行位置上 ,返回 。(2) 同一天内矛盾课程最佳时段2查找法 : 选定执行操作个体 ; 在同一天内逐行

13、查找重复上课 的课程 ,如果找到执行 到 ; 在隔一天的时间段以后的时间段查找没有参加该谭程班级上课的时间段 ; 交换选定时间段与原时间段的课程位置 。3 实验结果依据上述算法 ,用 tc + + 310 编写了相应的程序 。实验中取 1 = 10 ,2 = 1 ,3 = 100 , = 0101 ; r = 15 。应用文献 7 中数据对同一系中由 15 位教师担任的 10 个班级的 6 类 30 门课教学任务求解 , 即 m= 15 , n = 10 , p = 30 。群体规模为 f = 20 时 , 选定参数 p r = 011 , pc = 018 , p m = 0102 作实验对

14、比 ,结果如表 1 。表 1 实验结果对比表tab. 1co mpared table of result s迭代次数050150200250300350400450500遗传算法 + 查找遗传算法01013 201010 301027 001049 901027 001066 601032 301066 601035 701090 801035 701099 901058 801111 001058 801199 601058 801249 401058 801249 4(1) 通过运行结果对比可知加入最佳时段2查找过程确定提高了遗传算法的求解质量和加快收敛速度 ; (2) 本文提出的遗传算

15、法嵌入最佳时段2查找法的遗传算法确定能求解所建模型问题的解 。4结语从实验结果来看 ,本文所建立的模型及求解办法能解决课表编排问题中的上课密度矛盾 。最佳时段2查找过程确定提高解的质量和加快收敛速度 。通过验证一些其他实例也取得了令人满意的结果 。课程表问题的“软”约束条件多种多样 ,相信本文算法对相关问题解决也有一定的借鉴作用 。参 考 文 献 :1 ev en s , i tal a ,sham ir a. on t he co mplexit y of timetable and multi2co mmodity flow p roblems j . siam journal o nco

16、 mp uting ,1976 ,5 (4) :691 - 703 .tr ipa t h y a. school timetabling2a case in large binary integer linear p rogramming j . discrete a pplied mat h ematics ,1984 ,35 (3) :313 - 323 .bu r k e k , ell iman d g , w ear e r f. a university timetabling system based o n grap h coloring and ocnst raint ma

17、nip u2latio n j . journal of research o n co m p uting in educatio n ,1994 ,27 (1) :1 - 18 .kowal czyk r. co mbining co nst raint p rogramming and evolutio nary algorit hms in co nst rained decisio n op tim izatio n p roblemsc . proceedin g of t he 1997 internatio nal coference o n neut ral informai

18、to n processing and intelligent informatio n systemsa . new zealand :dunedin ,1997 :826 - 829 .si geru o. incorporating co nst raint p ropagatio n in genetic algorit hm for university timetable planningj . en gineering ap2plicatio n of aritificial intelingence ,1999 :241 - 253 .熊焱 ,李大卫 ,张庆灵 . 用遗传算法求

19、解课程表问题 j . 鞍山钢铁学院学报 ,2002 ,25 (6) :415 - 418 .刘勇 ,康立山 ,陈毓屏 . 非数值并行算法 遗传算法 m . 北京 :科学出版社 ,1998 :12 .234567model an d al gorithm f or un iversity t imeta bl ing problemx i o n g y a n1 , 2 , w a n g l i1 , l i d a2w ei1 , z ha n g q i n g2l i n g2 ( 1 . facult y of science ,anshan u niversit y of scie

20、nce and technology ,anshan 114044 ,china ;2 . facult y of science ,no rt heasteren u niversit y ,shengyang 110006 ,china)abstract :timetabling p ro blem is not o nly o ne of t he timetable p ro blems but also a kind of n p2co mplete p ro blem . acco rding to t he characteristics of lect uring met ho

21、 d in universit y ,a mat hematical mo del was set up and a genetic algo rit hm fo r t he p ro blem was int ro duced. to imp rove solutio n qualit y and accelerate co nver2 gence speed ,a met ho d of loo king fo r new po ssible po sitio n was p rovided and was embedded in genetic algo2 rit hm w hen t

22、 he same classes o r co urses appear repeatedly at t he same time . the experiment result show s t hat t he met ho d is feasible and effective .key words :universit y timetabling p ro blem ; mo del ;genetic algo rit hm ; n p2co mplete p ro blem( received november 12 , 2004) 上接第 25 页approach to model reduct ion f or complex systemsm a l i a n2z en g1 , ko n g x i a n g2hon g2 , c h en x ue2bo1( 1 . school of elect ro nics and info r matio n