李 睿，楊子蘭，楊惠娟

（1.云南大學旅游文化學院 信息科學與技術系，云南 麗江 674199；2.昭通學院 數(shù)學與統(tǒng)計學院，云南 昭通 657000）

FFD算法的研究及其在高校排考中的應用

李 睿1，楊子蘭1，楊惠娟2

（1.云南大學旅游文化學院 信息科學與技術系，云南 麗江 674199；2.昭通學院 數(shù)學與統(tǒng)計學院，云南 昭通 657000）

考試安排問題是一個著名的NP-完備問題，目前尚無標準的方法，大多根據(jù)自動排考算法再結合高校自身的特點修改為滿意的排考方案。由裝箱算法的思想，提出一種帶有沖突關系的裝箱算法來實現(xiàn)排考，將沖突條件直接加入裝箱算法中，即在判斷能否裝箱時可以在更大的范圍內(nèi)尋找排課方案，以保證得到更優(yōu)的解，最后給出了一個算例說明該算法的實用性。

考試安排；FFD算法；裝箱

［1］Carter M W.A Survey of Practical Applications of Examination Timetabling Algorithms ［J］.Operations Research，1986，34（2）:193-202.

［2］Qu R，Burke E K，McCollum B.A survey of search methodologies and automated system development for examination timetabling［J］.Journal of scheduling，2009，12（1）:55-89.

［3］Boeck L D，Beli?n J，Creemers S.A column generation approach for solving the examination-timetabling problem Author-Name:Woumans，Gert［J］.European Journal of Operational Research，2016，253（1）:178-194.

［4］董健興，欒勇，閆君政.基于圖論的高校排考算法［J］.計算機系統(tǒng)應用，2011，20（5）:177-179.

［5］王卿，張亞文，張偉.高等學校排考染色 -匹配算法［J］.上海理工大學學報，2005，27（2）:157-161.

［6］Simchi-Levi D.New worst-case results for the bin-packing problem［J］.Naval Research Logistics，1994，41（4）:579–585.

［7］Murgolo F D.Anomalous behavior in bin packing algorithms［J］.Discrete Applied Mathematics，1988，21（3）:229-243.

［8］Correia I，Gouveia L，Saldanha-Da-Gama F.Solving the variable size bin packing problem with discretized formulations［J］.Computers&Operations Research，2008，35（6）:2103-2113.

The Research of FFD Algorithm and Application in College Examination Timetabling

LI Rui1，YANG Zi-lan1，YANG Hui-juan2
（1.Tourism and Culture College of Yunnan University，Lijiang Yunnan 674199；2.School of Mathematic and Statistics，Zhaotong University，Zhaotong Yunnan 657000）

The examination timetabling problem is a famous NP-complete problem.Most colleges and universities using the computer to arrange the test timetable coarsely，and then manually adjusted into the final exam schedule.Similar to the idea of bin packing problem algorithm，present an algorithm of bin packing problem with conflicts to solve examination timetabling，the algorithm puts the conflicts directly into the bin packing problem algorithm，which can find the scheduling scheme in the greater scope，and then get a better solution，an example is given to illustrate the practicability of the algorithm.

examination timetabling；FFD algorithm；bin packing

O224

A

1673—8861（2017）03—0147—04

2017-06-01

李睿（1983-），男，云南麗江人，云南大學旅游文化學院講師，碩士。主要研究方向：組合最優(yōu)化。

云南省教育廳科學研究基金項目（2017ZDX270）、云南大學旅游文化學院院級項目（2015XY08）。

［責任編輯］張琴芳