Integrated and Decomposition-Based Solution Approaches for Project-Oriented School Timetabling

Abstract This paper investigates the timetabling problem in project-oriented schools and is based on the real-world setting of the Universitätsschule Dresden, an experimental school organized around interdisciplinary project work. In project-oriented schools, traditional subject-based instruction is replaced by flexible learning structures that enable individualized learning pathways. However, individual schedules and short project cycles increase the need for efficient planning tools to coordinate resources effectively. Therefore, a mixed-integer linear programming model is proposed to generate such individualized timetables that account for student preferences, the number of opened project sections, room resources, and supervision requirements. These objectives are combined using a weighted-sum approach, enabling decision-makers to balance pedagogical and operational considerations. To address computational scalability, four solution approaches with different degrees of decomposition are examined: a fully integrated model, an optimized post-enrollment strategy, a sequential decomposition, and a decomposition approach enhanced by an improvement step based on partial variable fixing and re-optimization. Computational experiments show that the integrated model becomes intractable for larger instances, while especially the decomposition approach with the improvement step offers a favorable balance between solution quality and computation time. The proposed solution approaches provide insights that may support decision-making in schools with comparable project-based structures.