CAJ | 학술논문

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