FFD算法的研究与应用  

Research and Application of FFD Algorithm

作　　者：邓志杰[1] 曹敬[1] 

机构地区：[1]河海大学计算机与信息学院,江苏南京211100

出　　处：《计算机技术与发展》2013年第12期116-119,共4页Computer Technology and Development

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

摘　　要：排课问题是一个有约束的、多目标的组合优化问题,而FFD(First Fit Decreasing)算法是计算机数学组合优化的近似算法。文中针对排课中教室分配问题,引入FFD算法,采用首次适应贪婪思想,先将教室和课程按容量和上课人数从大到小排序,然后依次从前往后选择最先适合教室分配给课程。以国际自动排课问题研究团队(WATT)组织的第二次国际竞赛数据和规则为基准,通过与二部匹配算法、NFD(Next Fit Decreasing)和NF(Next Fit)策略进行比较,FFD算法能在最优安排全部课程的上课教室前提下,对于竞赛给定的惩罚函数,所得惩罚值最小,并且教室利用率最高。Timetabling problem is a multi-objective combination optimization problem with constrains, and FFD （First Fit Decreasing） is the approximate algorithm of the computer mathematics combinatorial optimization problem. Apply the FFD algorithm to the classroom allocation problem,using the first fit greedy method,first classrooms and courses are sorted from big to small,and then select the In＇st fit classroom by the order. Based on the data and rule of the second international timetabling competition sponsored by Working Group on Automated Timetabling （WATT） ,the method can get the minimum penalty cost and the highest utilization rate of classroom after beastly allocating all these courses compared with bipartite matching algorithrn,NFD（ Next Fit Decreasing） strategy and NF（ Next Fit ） strategy.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]