基于贪心法的排课算法

《基于贪心法的排课算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于贪心法的排课算法第25卷第3期云南师范大学学报Vol.25No.3　2005年5月JournalofYunnanNormalUniversityMay2005　基于贪心法的排课算法3梁　立,　陈玉华,　徐　敏关　键　词:　排课算法;贪心法;最优解中图分类号:　TP392　　文献标识码:　A　　文章编号:　1007-9793(2005)03-0009-04(云南师范大学计算机科学与信息技术学院,云南昆明650092)摘　要:　一直以来,最优解的排课算法的时间复杂度大多是排课规模的指数阶。文章把贪心法应用于排课算法中,得到排课最优解的多项式算法。　　排课是脑力劳动强度较高的工作。尽管

2、不同学校的教学管理模式存在差异,对排课结果的形式也有所不同,但其共同的目标都是对教学任务进行合理的时空分配。国内外大多数排课算法基本上是基于回溯的二部图匹配算法[1][2]。到目前为止,组合最优化算法研究几乎都得到最优解的排课算法的时间复杂度是排课规模的指数阶[2][3]。尽管如此,为了充分利用教学资源,也只能追求排课最优解。本文把贪心算法应用于排课算法中[4],得到易于实现最优解的多项式排课算法。1　数据结构排课的资源数据可分为三个数据集合:(1)课程元集合K,其属性主要有课程名(含班级信息)、周学时、上课人数和授课教师,每个元素称为课程元;(2)教学场地集合D,其属性主要是教学场

3、地名、容量和类别(或用途,比如普通教室、多媒体教室、某种实验室等等);(3)时间元集合T,其属性是上课时间片。T是有限时间序列,每天分为6个时间片(见图1),则T有30个元素,如356是T的一个元素,表示星期三56节。三种约束条件(称为软约束条件):(1)对集合K和D的限制条件或特殊要求,是不定型的多维约束,比如对某课程的时间元要求、场地要求等,实际实现时可以作为集合K的一个属性;(2)因为资源的独占性,时间元约束,即必须解决的课程-时间冲突、教师-时间冲突及场地-时间冲突。(3)把T中的时间元给一个分配优先顺序(一般应为上午、下午、晚上)。下面简单介绍几个集合及软约束条件的示例。表

4、1列出了集合K的主要属性及示例。其中“00A,00B”“表示两个班合班上课;张三(讲师),李四(助教)”表示多个授课教师;课程要求用编码形式给出软约束条件,为了软件实现的实用性,用图3的用户界面生成软约束条件编码。排课结果可以是手工录入(软约束条件选择“本课程手工已排好”,则固定排课结果,可以处理计算机难以解决的特殊要求)或算法自动生成,其格式为{时间元,单双周标志,场地收稿日期:2004-12-20作者简介:梁立(1965—),男,重庆市潼南县人,副教授,研究方向:算法分析,并行计算.排课结果·10·云南师范大学学报(自然科学版)　第25卷　名;},单双周标志取值{0,1,2},0

5、表示每周都上课,1表示只单周上课,2表示只双周上课,如“1567,0,明析楼101;”。表1　集合K示例Tab.1　sampleofsetK班级课程名周学时上课人数授课教师课程要求01A,01B多媒体技术4118张三(讲师),李四(助教)(编码)01A计算方法360王五(副教授)(编码)1567,0,明析楼101;01B图形学358邱六(教授)(编码)　　表2给出了集合D的主要属性及示例。其中场地类别用于课程要求的软约束。“场地使用情况”是为了便于统计场地的使用,主要用于掌握空闲场地,由排课程序自动生成,其格式为{时间元,单双周标志,班级,课程名;}表2　集合D示例Tab.2　sam

6、pleofsetD场地名容量类别场地使用情况明睿楼301120多媒体教室明析楼10160普通教室1567,0,01A,计算方法;134,0,01B,图形学;312,1,01B,图形学;图1　软约束条件示例Fig.1　selectableconditions2　数学模型排课实际上是作满足约束条件的K×D×T的关系运算,其结果为三维表。满足约束条件的解只是可行解。由于软约束条件的限制,可行解的最优情况只取决于场地的分配。使剩余场地的容量总和最大的可行解即为最优解,换言之,最优解是使分配的场地容量之和最小的可行解。　第3期　梁　立,等:　基于贪心法的排课算法··11假设

7、K

8、=n,

9、D

10、=

11、m,形式描述如下:nmminΣΣxijwj　　s.t.　viFwj,i=1,2,.,n,j=1,2,.,mi=1=1其中,vi是第i个课程的上(j)课人数,wj是第j个场地的容量;xij=1表示第j个场地成功分配给第i个课程,xij=0表示未分配。3　排课算法3.1算法思想两次贪心选择:先在K中选未处理且上课人数最大的课程,再在D中选min{场地容量:场地容量≥上课人数}且符合课程要求(软约束条件)的教学场地。3.2辅助空间①二维数组mat1(n,30):