组合时间模式与贪婪准则的排课方法  

A Course Scheduling Method Based on the Time Pattern and the Greedy Criterion

作　　者：肖杰[1] 崔韶刚[1] 蔡放[1] 

机构地区：[1]长沙大学计算机科学与技术系,湖南长沙410003

出　　处：《计算机工程与科学》2011年第6期125-129,共5页Computer Engineering & Science

基　　金：湖南省科技计划项目(2010FJ011);湖南省教育厅科学研究资助项目(08C136)

摘　　要：排课问题是一个具有多因素的优化决策问题,是组合规划中的典型问题,属于NP完全类问题。为了能够有效地抑制排课中的"组合爆炸"现象,提高排课速度,根据高校课表的特点,本文针对周课时的离散化分布提出了时间模式概念,设计了时间贪婪准则和教室贪婪准则。测试结果表明,本文算法不但能简化排课过程,提高排课效率,同时也提高了排课的满意度。The timetabling problem is a multi-factor optimized decision problem and is typical problem in constitution and planning.It has been proved to be a NP-complete problem.In order to restrain the phenomenon of combination explosion of course scheduling and improve the course scheduling rate,according to the characteristics of course assignment in universities,this paper proposes the concept of time pattern for the discrete and distributed weekly class hours and devises the time greedy criterion and classroom greedy criterion.The test results show that our algorithm can not only simplify the process and improve the efficiency for course scheduling,but also improve the satisfaction with timetabling.

关 键 词：排课 时间模式 贪婪准则 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]