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

J4 ›› 2011, Vol. 33 ›› Issue (6): 125-129.

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

肖杰，崔韶刚，蔡放

(长沙大学计算机科学与技术系，湖南长沙 410003)

收稿日期:2010-07-13 修回日期:2010-10-24 出版日期:2011-06-25 发布日期:2011-06-25
作者简介:肖杰(1976),男,湖南娄底人，硕士，讲师，研究方向为分布式软件工程、数据仓库和数据挖掘。
基金资助:
湖南省科技计划项目（2010FJ011）;湖南省教育厅科学研究资助项目（08C136）

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

XIAO Jie,CUI Shaogang,CAI Fang

(Department of Computer Science and Technology,Changsha University,Changsha 410003,China)

Received:2010-07-13 Revised:2010-10-24 Online:2011-06-25 Published:2011-06-25

摘要/Abstract

摘要：

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

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

Abstract:

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.

Key words: course scheduling；time pattern；greedy criterion

肖杰，崔韶刚，蔡放. 组合时间模式与贪婪准则的排课方法[J]. J4, 2011, 33(6): 125-129.

XIAO Jie,CUI Shaogang,CAI Fang. A Course Scheduling Method Based on the Time Pattern and the Greedy Criterion[J]. J4, 2011, 33(6): 125-129.