期刊
COMPUTERS & INDUSTRIAL ENGINEERING
卷 169, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2022.108192
关键词
Scheduling; Timetabling; Dancing Links; Assignment
The algorithm efficiently and accurately schedules and optimally assigns military trainees to classes, respecting domain constraints. It shows significant computational benefit compared to other methods and can handle larger-scale problems effectively.
We present an efficient and exact algorithm for timetabling military training - a novel integration of Knuth's efficient Dancing Links indexing scheme with A* search that allows us to simultaneously schedule and optimally assign military trainees to classes while respecting domain constraints. We show that our Simultaneous Sequencing and Assignment Solver (SSAS) is able to handle cohort sizes appropriate to the requirements of the Australian Defence Force under a complex prerequisite structure for the courses. Comparisons using real-life parameters with the best known integer programming approach (a column generation-based heuristic) has showed a significant computational benefit from using SSAS. We further tested our method on larger problem instances that might arise in larger training schools. Our SSAS was able to optimally solve such larger-scale problems or prove the problem infeasible in a reasonable computation time.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据