FFD算法的研究与应用

摘要：

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

关键词：FFD、贪婪法、排课问题、教室分配

分类号：TP301.6(计算技术、计算机技术)

资助基金：“十五”国家重大863专项“苏州市水环境质量改善与综合示范项目”2003AA601070

在线出版日期：2013-12-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：116-119