A constructive approach to examination timetabling based on adaptive decomposition and ordering
A constructive approach to examination timetabling based on adaptive decomposition and ordering
复制标题
DOI：
10.1007/s10479-011-0999-8
复制
发表时间：
2011-10
影响因子：
4.8
通讯作者：
S. A. Rahman;E. Burke;A. Bargiela;B. McCollum;E. Özcan
中科院分区：
文献类型：
--
作者：
S. A. Rahman;E. Burke;A. Bargiela;B. McCollum;E. Özcan
在这项研究中，我们研究了一个自适应的分解和排序策略，自动将考试分为困难和容易的集合，以构建考试时间表。困难组中的检查被认为是难以放置的，因此在构建过程中被列在容易组中的检查之前。此外，每个集合内的检查使用基于图着色算法的不同策略进行排序。最初，考试被放置在简单的集合中。在施工过程中，无法安排的检查被确定为造成不可行性的检查，并在困难的设置中向前移动，以确保在随后的尝试中提前分配。另一方面，可以安排的检查仍然是容易的。在简单集内，引入了一个称为边界集的新子集，以适应洗牌策略来改变给定的考试顺序。所提出的方法，其中包括不同的订购和洗牌策略，探讨卡特基准问题。实证结果表明，我们的算法的性能是广泛的现有建设性的方法相媲美。
In this study, we investigate an adaptive decomposition and ordering strategy that automatically divides examinations into difficult and easy sets for constructing an examination timetable. The examinations in the difficult set are considered to be hard to place and hence are listed before the ones in the easy set in the construction process. Moreover, the examinations within each set are ordered using different strategies based on graph colouring heuristics. Initially, the examinations are placed into the easy set. During the construction process, examinations that cannot be scheduled are identified as the ones causing infeasibility and are moved forward in the difficult set to ensure earlier assignment in subsequent attempts. On the other hand, the examinations that can be scheduled remain in the easy set. Within the easy set, a new subset called the boundary set is introduced to accommodate shuffling strategies to change the given ordering of examinations. The proposed approach, which incorporates different ordering and shuffling strategies, is explored on the Carter benchmark problems. The empirical results show that the performance of our algorithm is broadly comparable to existing constructive approaches.