TL;DR
This paper presents a successful deployment of a constraint-based timetabling system for a dental school, addressing the unique challenges of scheduling clinical sessions and maximizing resource utilization. The system has allowed the dental school to increase student intake significantly while maintaining educational quality, demonstrating the power of constraint programming in real-world, complex scheduling problems.
What Problem Does This Paper Address?
Traditional university timetabling often focuses on avoiding "event clashes" – ensuring a student isn't scheduled for two lectures simultaneously. However, dental school timetabling presents a different beast. The core challenge lies in efficiently utilizing expensive and limited resources like dental chairs and specialized equipment. Unlike typical university courses, dental clinics can accommodate multiple groups from different years simultaneously, provided room capacity isn't exceeded and a suitable student-to-teacher ratio is maintained. This transforms the problem from a simple graph coloring exercise into a complex "bin packing" problem, where the goal is to pack as many students as possible into available slots without idle resources. The dental school at Cork University Hospital faced this issue acutely when student numbers increased, making their manual timetabling process unsustainable and leading to resource bottlenecks.
Methods
The authors developed a constraint-based timetabling system that evolved over three years. Initially, they used a constraint programming (CP) solver with a web interface. This approach, while capable of finding feasible solutions, struggled with proving optimality or infeasibility and handling multiple objectives. To address this, they transitioned to a mixed-integer programming (MIP) model using the CPLEX solver, which proved more adept at identifying infeasible scenarios.
A significant evolution was the development of a dedicated Java application with a graphical user interface (GUI). This provided a more flexible and user-friendly environment for creating and modifying timetables. The system's core decision variables are binary, indicating whether a group is assigned to a subject in a specific time slot, with an additional index to denote if "doubling up" (two students sharing a treatment chair) is used. The system also incorporates variables to track the use of non-preferred time slots and the utilization of extra capacity.
The objective function is multi-faceted, aiming to minimize:
- Instrument cleaning effort: Accounting for the time required to sterilize instruments between uses.
- Doubled-up sessions: Penalizing the use of "doubling up" to maintain teaching quality.
- Non-preferred time periods: Encouraging the use of more desirable time slots.
- Extra capacity usage: Minimizing the use of additional resources, which may come with associated costs or supervision challenges.
The system employs various constraints to model the problem, including:
- Capacity constraints: Ensuring the number of students in a session does not exceed room capacity.
- Demand constraints: Meeting the required number of sessions for each subject and group.
- Incompatibility constraints: Preventing groups from being scheduled in the same time slot if they share students or if a teaching assistant is handling both.
- Occurrence constraints: Limiting the number of sessions a group can attend on a given day.
- Allocation constraints: Allowing for user-defined preferences to force, forbid, or restrict specific assignments.
Datasets
The paper does not explicitly mention a distinct dataset for training or evaluation. Instead, it describes the real-world data from the Cork University Hospital Dental School, which was used to develop and deploy the system. The "dataset" consists of the curriculum, student group sizes, subject demands, room capacities, and various constraints specific to the dental school's operations. The system was used to generate timetables for the years 2010, 2011, and 2012.
Key Insights and Ideas
- Dental timetabling is a bin-packing problem, not just graph coloring: This is a crucial distinction. The primary difficulty lies in resource utilization and capacity management, not just avoiding direct conflicts.
- "Doubling up" as a flexible resource management tool: The system's ability to model and manage "doubling up" (two students sharing a chair) was essential for handling increased student numbers and tight resource constraints. This feature allows for a trade-off between resource utilization and teaching quality.
- The importance of a user-friendly interface for complex optimization: The evolution from a web interface to a dedicated Java application highlights how crucial an intuitive GUI is for stakeholders to interact with, understand, and refine complex optimization solutions.
- Iterative development and stakeholder collaboration are key: The system's development involved close collaboration with the dental school, leading to the incorporation of new requirements (like instrument cleaning) and refinements over time.
- Constraint programming and MIP offer complementary strengths: The initial CP approach was good for finding solutions, while the MIP approach excelled at proving infeasibility, a critical aspect for over-constrained problems.
Key Results
The deployed system has been successfully used to generate timetables for the Cork University Hospital Dental School for the years 2010, 2011, and 2012. This automated system replaced a manual process that could no longer cope with increasing student numbers. The system enabled the dental school to:
- Increase student numbers to the maximum possible given the available resources.
- Provide a valuable "what-if" analysis tool for exploring different scenarios and resource allocations.
- Significantly reduce the time needed to build the final timetable.
While specific quantitative metrics like "accuracy" or "speedup" are not presented in terms of traditional benchmarks, the qualitative results of successful deployment and increased student intake are significant.
Limitations and Future Work
- Over-constrained problems: The paper notes that dealing with systematically over-constrained problems was a significant challenge, requiring extensions like "doubling up" and the use of extra capacity. While solutions were found, the optimal balance between these strategies and their impact on teaching quality is an ongoing consideration.
- Personalized costs: The authors mention that personalized costs for groups or subjects could be introduced (e.g., if cleaning time is more acceptable for Year 4 than Year 5 students), but this would require more user input and is not currently implemented.
- Future work: The paper doesn't explicitly detail future work, but the iterative nature of the system's development suggests ongoing refinement and adaptation to new requirements. The potential for personalized costs is a clear avenue for future exploration.
Summary updated