School timetable construction : algorithms and complexity

Abstract

the subject group.Note that we only assign a student to subject groups corresponding to the subjects in the student's curriculum.Nowadays, many teachers do not have full timetables.That is, the number of lessons they teach is much less than the total number of time slots in a week.This implies that teachers have idle time in their timetables.Since labor agreements require that timetables for these part-time teachers are compact, their idle time may not be spread randomly over all days of the week.Restrictions of the sort that every teacher that teaches x lessons should have y parts of days off introduce new decisions in the timetabling problem.In upper years, students have much freedom in composing their curricula.Having no restriction on the subject selection might lead to a large number of different curricula.Also, it may imply many conflict constraints as no two lessons for the same student can be taught at the same time.Therefore, exotic subject combinations are often ruled out by school management.Conditions.Some combinations of assignments lead to acceptable timetables, others do not.Such restrictions follow from conditions imposed by rooms, students or teachers.We distinguish two types of conditions: conditions that must be met (requirements) and conditions that should be fulfilled as well as possible (desires).Requirements.It is impossible for a teacher or student to attend more than one lesson simultaneously.Therefore, every teacher or student can have at most one lesson at the same time.We call these requirements teacher constraints and student constraints.Similarly, room constraints are only satisfied if each room is used for only one lesson at a time.Teachers can be unavailable for teaching lessons at some time slots.It is clear that a lesson can only be taught at a time the teacher is available.Teacher availability constraints force us to find time slot assignments that satisfy these requirements.At many schools, rooms are dedicated to specific subjects.For example, language rooms are equipped with headsets and physics rooms with water taps, electricity sockets and gas.Moreover, there are large gymnastics halls in which only physical education lessons can be given.Of course, lessons can only be taught in rooms that are suitable.We can group rooms that are equipped for the same set of lessons and say that they have the same room type.By means of room compatibility constraints, we require that only rooms of a suitable type are assigned to each lesson.There are two requirements that restrict the possible assignments of different lessons for the same subject group.The first requirement forces a spread of lessons for educational reasons.Lessons of the same subject group must be assigned to different days such that students can absorb the material and are able to do homework for the next lesson.We take educational constraints that forbid assignment of lessons of the same subject group to the same day into account.The other requirement type enforces two or more lessons to be assigned to consecutive time slots on the same day.For example, two crafts or drawing lessons for Solving the core problemIn Chapter 5, we describe the solution approach we adopted for TSSGAP and the algorithm we implemented.The main idea is that we extend the subject group assignment step by step while maintaining a feasible timetable.So, we iterate over the subject group assignment and time slot assignment sub-problems.The algorithm is a hybrid, since we assign students to subject groups by means of a tree search algorithm and use a tabu search algorithm to repair the current timetable if it has become infeasible.We give the main procedures of the algorithm in pseudocode and discuss how we try to improve the performance of the tree search and tabu search algorithm by using problem-specific knowledge.The algorithm contains a number of parameters for variable and value selection, dead end handling, and the tabu search routine.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 89 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.