A Hybrid Algorithm for the Examination Timetabling Problem
A Hybrid Algorithm for the Examination Timetabling Problem
复制标题
DOI：
10.1007/978-3-540-45157-0_14
复制
发表时间：
2002-08
期刊：
影响因子：
--
通讯作者：
Liam T. G. Merlot;N. Boland;B. Hughes;Peter James Stuckey
中科院分区：
文献类型：
--
作者：
Liam T. G. Merlot;N. Boland;B. Hughes;Peter James Stuckey
考试时间表是一个经过充分研究的组合优化问题。我们提出了一种用于检查时间表的新混合算法，由三个阶段组成：用于开发初始解决方案的约束规划阶段、用于提高解决方案质量的模拟退火阶段以及用于进一步改进的爬山阶段。介绍了墨尔本大学的考试时间表问题，并证明混合方法优于该大学目前采用的方法。最后，将混合方法与公开数据集上的既定方法进行比较，发现其表现良好。
Examination timetabling is a well-studied combinatorial optimization problem. We present a new hybrid algorithm for examination timetabling, consisting of three phases: a constraint programming phase to develop an initial solution, a simulated annealing phase to improve the quality of solution, and a hill climbing phase for further improvement. The examination timetabling problem at the University of Melbourne is introduced, and the hybrid method is proved to be superior to the current method employed by the University. Finally, the hybrid method is compared to established methods on the publicly available data sets, and found to perform well in comparison.