Journal
COMPUTERS & INDUSTRIAL ENGINEERING
Volume 169, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2022.108192
Keywords
Scheduling; Timetabling; Dancing Links; Assignment
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available