李 睿，楊子蘭，楊惠娟

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

FFD算法的研究及其在高校排考中的應(yīng)用

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

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

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

考試安排；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］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20（5）:177-179.

［5］王卿，張亞文，張偉.高等學(xué)校排考染色 -匹配算法［J］.上海理工大學(xué)學(xué)報(bào)，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-），男，云南麗江人，云南大學(xué)旅游文化學(xué)院講師，碩士。主要研究方向：組合最優(yōu)化。

云南省教育廳科學(xué)研究基金項(xiàng)目（2017ZDX270）、云南大學(xué)旅游文化學(xué)院院級(jí)項(xiàng)目（2015XY08）。

［責(zé)任編輯］張琴芳