A Two-Stage Optimization Framework for Real-World Large-Scale University Course Timetabling Based on Orthogonalized Hierarchical Modeling and Conflict-Driven ALNS Repair
Abstract
University course timetabling is a large-scale combinatorial optimization problem involving strongly coupled temporal and resource constraints. This paper proposes a two-stage optimization framework for real-world large-scale university course timetabling, integrating orthogonalized hierarchical modeling with conflict-driven adaptive large neighborhood search (ALNS) repair. The first stage performs global course-level optimization, while the second identifies residual conflicts through a conflict graph and localizes them into connected conflict regions. The Course--Occurrence--Session representation provides the structural basis for multi-granularity repair, which employs Cluster-, Course-, Occurrence-, and Session-level destroy operators within the ALNS framework, followed by fine-grained greedy repair. The framework is evaluated on a real-world university timetabling instance involving 3,073 course groups, 8,015 scheduling events, 998 student classes, and 1,511 instructors. Ablation experiments demonstrate the effectiveness of hierarchical repair granularity and adaptive operator selection. Across ten independent runs, the ALNS + Greedy framework achieves a mean residual conflict count of 18.50, compared with 172 for deterministic Greedy-only repair under the same initial scheduling conditions, representing an 89.24\% reduction. These results support the effectiveness of the proposed conflict-driven hierarchical repair framework for large-scale university course timetabling.
Related
- Infeasible Momentum Orthogonalized Methods for Optimization on the Stiefel Manifold
- Nonsmooth Optimization via Orthogonalized Momentum
- Not All Objectives Are Born Equal: Priority-Constrained Descent for Hierarchical Multi-Objective Optimization
- Thermal management optimization of Battery Electric Vehicles via hierarchical NMPC with CMO-trained Neural Models
- HALO: Hierarchical Evidence Selection and Reinforcement Learning for Allocating Budgeted Label Optimization from Longitudinal Clinical Records
BibTeX
@misc{liu2026twostage,
title = {{A Two-Stage Optimization Framework for Real-World Large-Scale University Course Timetabling Based on Orthogonalized Hierarchical Modeling and Conflict-Driven ALNS Repair}},
author = {Han-Bin Liu and Huayi Wei and Yanlin Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37100},
eprint = {2610.37100},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37100},
}
RIS
TY - UNPB
TI - A Two-Stage Optimization Framework for Real-World Large-Scale University Course Timetabling Based on Orthogonalized Hierarchical Modeling and Conflict-Driven ALNS Repair
AU - Han-Bin Liu
AU - Huayi Wei
AU - Yanlin Li
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37100
UR - https://arxiv.org/abs/2610.37100
AB - University course timetabling is a large-scale combinatorial optimization problem involving strongly coupled temporal and resource constraints. This paper proposes a two-stage optimization framework for real-world large-scale university course timetabling, integrating orthogonalized hierarchical modeling with conflict-driven adaptive large neighborhood search (ALNS) repair. The first stage performs global course-level optimization, while the second identifies residual conflicts through a conflict graph and localizes them into connected conflict regions. The Course--Occurrence--Session representation provides the structural basis for multi-granularity repair, which employs Cluster-, Course-, Occurrence-, and Session-level destroy operators within the ALNS framework, followed by fine-grained greedy repair. The framework is evaluated on a real-world university timetabling instance involving 3,073 course groups, 8,015 scheduling events, 998 student classes, and 1,511 instructors. Ablation experiments demonstrate the effectiveness of hierarchical repair granularity and adaptive operator selection. Across ten independent runs, the ALNS + Greedy framework achieves a mean residual conflict count of 18.50, compared with 172 for deterministic Greedy-only repair under the same initial scheduling conditions, representing an 89.24\% reduction. These results support the effectiveness of the proposed conflict-driven hierarchical repair framework for large-scale university course timetabling.
ER -