FFD算法的研究与应用

• 作者: 曹敬 邓志杰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: FFD 贪婪法 排课问题 教室分配
• 年，卷（期）: 2013,（12）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 116-119
• 页数: 4页
• 分类号: TP301.6
• 字数: 4239字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2013.12.028

摘要

排课问题是一个有约束的、多目标的组合优化问题,而FFD( First Fit Decreasing)算法是计算机数学组合优化的近似算法。文中针对排课中教室分配问题,引入FFD算法,采用首次适应贪婪思想,先将教室和课程按容量和上课人数从大到小排序,然后依次从前往后选择最先适合教室分配给课程。以国际自动排课问题研究团队( WATT)组织的第二次国际竞赛数据和规则为基准,通过与二部匹配算法、NFD( Next Fit Decreasing)和NF( Next Fit)策略进行比较,FFD算法能在最优安排全部课程的上课教室前提下,对于竞赛给定的惩罚函数,所得惩罚值最小,并且教室利用率最高。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曹敬	河海大学计算机与信息学院	11	61	4.0	7.0
2	邓志杰	河海大学计算机与信息学院	2	10	2.0	2.0