A Constraint-Based Approach to High-School Timetabling Problems: A Case Study

Masazumi Yoshikawa, Kazuya Kaneko, Yuriko Nomura, Masanobu WatanabeAAAI 1994

High-school timetabling is a notoriously difficult administrative task. In Japanese high schools, this process traditionally required up to 100 person-days of manual labor. This paper, originally presented at AAAI-94, introduces COASTOOL, a constraint-based system designed to automate this complex scheduling task, reducing computation time to approximately one hour while maintaining high schedule quality.

The Timetabling Challenge

High-school timetabling is a classic Constraint Relaxation Problem (CRP). It involves thousands of variables and is "tightly constrained," meaning the search space for valid configurations is extremely narrow.

The constraints are categorized into two types:

  • Hard constraints: Fundamental requirements, such as ensuring no teacher or class is scheduled for two places simultaneously and that every class has a complete schedule.
  • Soft constraints: Preferences such as specific days off for teachers, subject sequencing (e.g., avoiding multiple math credits on the same day), and coordinating simultaneous elective courses.

Traditional backtracking methods often fail due to "thrashing" in such large-scale problems, while general optimization techniques like Simulated Annealing (SA) often converge too slowly from random starting points.

The COASTOOL Architecture

COASTOOL addresses these challenges by decoupling the problem description from the solving logic. This separation allows administrators to define the "what" of the problem without needing to program the "how."

The COASTOOL system architecture decouples declarative problem descriptions from the method library.

The system consists of three main components:

  1. Declarative Modeling: A specialized language for defining variables, domains, and penalty-weighted constraints.
  2. RFLG (Really-Full-Lookahead Greedy) Initialization: A novel algorithm that uses arc-consistency to prune variable domains before assignment, preventing the "early mistake" trap common in standard greedy solvers.
  3. MCHC (Min-Conflicts Hill-Climbing): An optimization stage that refines the initial RFLG output by iteratively moving variables to minimize total penalties.

Evaluation and Real-World Datasets

The system was tested on real-world data from two Japanese institutions: Kuki-Hokuyou High School (Kuki92 & Kuki93) and Daito Bunka University Dai-ichi High School (Daito93). These datasets represented large-scale problems with over 800 lessons and complex constraints, such as high teacher absence ratios and simultaneous elective courses.

Performance and Results

The combination of RFLG initialization and MCHC optimization proved highly effective. For the Kuki92 problem, COASTOOL reduced the total effort from 100 person-days to just 3 days of modeling and 1 hour of computation.

Performance comparison showing RFLG-MCHC achieving significantly lower penalty points in less time compared to Simulated Annealing (SA) and standard Greedy-MCHC.

As shown in the performance analysis, RFLG-MCHC reaches a superior solution (penalty of 14) much faster than Simulated Annealing or standard Greedy-MCHC. SA, while eventually capable of finding good solutions, required nearly three days of computation to match the quality COASTOOL achieved in an hour.

Conclusion

COASTOOL demonstrates that for tightly constrained problems, the quality of the initial starting point is critical. By using arc-consistency to guide a greedy initialization (RFLG), the system avoids deep local optima that hinder traditional optimization. While some "global" preferences and extremely complex cases still benefit from human-in-the-loop adjustments via a graphical interface, COASTOOL represents a significant leap in automating school administration.

Summary updated

BibTeX
@inproceedings{yoshikawa1994constraint,
  author = {Masazumi Yoshikawa and Kazuya Kaneko and Yuriko Nomura and Masanobu Watanabe},
  title = {{A Constraint-Based Approach to High-School Timetabling Problems: A Case Study}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure