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

李 睿，杨子兰，杨惠娟

（1.云南大学旅游文化学院 信息科学与技术系，云南 丽江 674199；2.昭通学院 数学与统计学院，云南 昭通 657000）

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

李 睿1，杨子兰1，杨惠娟2

（1.云南大学旅游文化学院 信息科学与技术系，云南 丽江 674199；2.昭通学院 数学与统计学院，云南 昭通 657000）

考试安排问题是一个著名的NP-完备问题，目前尚无标准的方法，大多根据自动排考算法再结合高校自身的特点修改为满意的排考方案。由装箱算法的思想，提出一种带有冲突关系的装箱算法来实现排考，将冲突条件直接加入装箱算法中，即在判断能否装箱时可以在更大的范围内寻找排课方案，以保证得到更优的解，最后给出了一个算例说明该算法的实用性。

考试安排；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］.计算机系统应用，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-），男，云南丽江人，云南大学旅游文化学院讲师，硕士。主要研究方向：组合最优化。

云南省教育厅科学研究基金项目（2017ZDX270）、云南大学旅游文化学院院级项目（2015XY08）。

［责任编辑］张琴芳