0
$\begingroup$

I am creating a timetabling software for a school, which given parameters for teachers/class sizes will output a timetable. There will be a list of classrooms per subject and a list of teachers per subject and I'll divide the students between the teachers.

The main focus is creating timetables for teachers, as opposed to the students, since the teachers will teach only one/two subjects so I believe it is a simper problem.

I aim to have a certain number of classes, which account for optimally ~20 students per class. Each class will require a teacher and each teacher can only be in one place at a time. Additionally, each subject will have a list of available rooms which they could take place in - e.g Computing cannot take place in a History classroom. As well as that, I hope to optimise the timetable so that a teacher is not forced to run across the whole school to get to their next lesson.

I have read a bit about Linear Programming, but I don't fully understand it all. Is it the best way to approach this problem, or should I use another algorithm? I will be using Python, combined with the use of an SQL database if that has any affect.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Linear Programming is a technique to model continuous optimization problems. Since a student cannot be divided in half (or a classroom shared by two half teachers at a time), this problem is not continuous and modelling it as a Linear Program does not appear possible.

What you might consider is modelling this problem as an Integer Linear Program (ILP). However, in contrast to Linear Programs, there are no algorithms with good worst-case running time for solving ILPs. There are good heuristic algorithms, which are good at solving many ILPs, but come without guarantee. You could try modelling your problem as ILP and feeding it to an ILP solver. If you are lucky it will turn out to be a feasible approach, if you are unlucky you will have to consider another approach (e.g., a heuristic such as simulated annealing).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.