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

The Research of FFD Algorithm and Application in College Examination Timetabling

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

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.