Students: Anton Bulat, Fatimah Mulan Ahmed, Fred Shen, Maxime Laschet
Supervisor: Dr. Matúš Mihalák
Semester 2015-2016
Problem statement and motivation:
The aim of this work is to compute an optimal schedule for the students and teachers of the Department Data Science of Knowledge Engineering at Maastricht University. The research and the mathematically modeling of a solution take a central aspect of this project.
The work has split into two groups: The Integer Linear Programming and the heuristics group. This report will focus on the work of the heuristics group. It will explain the conceptuation of the model including all constraints, the application of Local search and some heuristics approaches and experiments to improve feasible solutions.
Research questions:
In the present project we aimed at answering the following research questions:
- How an academic timetable can be effectively constructed, using the local search techniques and heuristic approaches?
- How the application can distinct between a good and a worse schedule?
Major outcomes:
- The local search algorithm starts with a given solution. Local movements of not feasible events in relation to new start conditions will lead to a feasible solution step by step. Addtionally the ILP group’s output is parsed and translated as input for our algorithm.
- The second main part is the verification of some rules which are decided to provide a better solution. The algorithm tries to minimize penalty values which are calculated for each event in each possible time point.
- The user has the possibility to make manual changes on the proposed solution and rerun the algorithm until a satisfying solution is generated.
- From the user interface the user is able to generate a PDF output of the timetable.
References:
- Arntzen, Halvard, and Arne Løkketangen. “A local search heuristic for a university timetabling problem.” nine 1.T2 (2003): T45.
- Rossi-Doria, Olivia. “A local search for the timetabling problem.” Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling, PATAT. 2002.
- Müller, Tomáš, Keith Murray, and Stephanie Schluttenhofer. “University course timetabling & student sectioning system.” Space Management and Academic Scheduling, Purdue University (2007).
- Ponnalagu, Karthikeyan, Renuka Sindhgatta Rajan, and Bikram Sengupta. “Automatically generating high quality soa design from business process maps based on specified quality goals.” U.S. Patent Application No. 12/885,870.
Download: report