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

排课问题是一个具有多因素的优化决策问题,是组合规划中的典型问题,属于NP完全类问题。为了能够有效地抑制排课中的"组合爆炸"现象,提高排课速度,根据高校课表的特点,本文针对周课时的离散化分布提出了时间模式概念,设计了时间贪婪准则和教室贪婪准则。测试结果表明,本文算法不但能简化排课过程,提高排课效率,同时也提高了排课的满意度。

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

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.