An efficient and exact algorithm for military timetabling and trainee assignment problems. (July 2022)
- Record Type:
- Journal Article
- Title:
- An efficient and exact algorithm for military timetabling and trainee assignment problems. (July 2022)
- Main Title:
- An efficient and exact algorithm for military timetabling and trainee assignment problems
- Authors:
- Nguyen, Vivian
Mak-Hau, Vicky
Moran, Bill
Novak, Ana - Abstract:
- Highlights: Unique nature of military timetabling necessitates cost-effective solutions. Integration of Dancing Links with A* search for optimal timetabling. Scheduling problem solved using DLX as a min-cost covering problem. Assignment of trainees to min-cost schedules using A* search algorithm. Computational results are compared against a number of MILP formulations. Abstract: 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.
- Is Part Of:
- Computers & industrial engineering. Volume 169(2022)
- Journal:
- Computers & industrial engineering
- Issue:
- Volume 169(2022)
- Issue Display:
- Volume 169, Issue 2022 (2022)
- Year:
- 2022
- Volume:
- 169
- Issue:
- 2022
- Issue Sort Value:
- 2022-0169-2022-0000
- Page Start:
- Page End:
- Publication Date:
- 2022-07
- Subjects:
- Scheduling -- Timetabling -- Dancing Links -- Assignment
Engineering -- Data processing -- Periodicals
Industrial engineering -- Periodicals
620.00285 - Journal URLs:
- http://www.sciencedirect.com/science/journal/03608352 ↗
http://www.elsevier.com/journals ↗ - DOI:
- 10.1016/j.cie.2022.108192 ↗
- Languages:
- English
- ISSNs:
- 0360-8352
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.713000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 22092.xml