Time blocks allocation Algorithm, Private Teacher->Student relationship, maximize number of classes to be given

Question

Hello guys!

The situation is the following.

I'm a private teacher with dozens of students. I have some restrictions on my time (for example I can't teach at friday afternoons) and students also have many restrictions on their time. Based on that, I'm trying to create my agenda in a way that I can do as many private lessons as possible and optimize my time at the same time. Ideally it would even take into consideration the distance from me to the students (some of them are in another city). Classes also have variable durations. Ideally I want to be able to set the time (each day of the week) I can teach and set the time (each day of the week) each student can have lessons, for how long does he want a lesson to last and frequency (i.e. 2x per week).

I believe there is already an algorithm, but I can't find the name of this problem. I believe it's not the case of the stable marriage and it's not the case of this one either: http://stackoverflow.com/questions/210635/teacher-time-schedule-algorithm

I would appreciate a lot if someone could point me to an algorithm or to material I can study in order to try to elaborate one if it does not exist.

Thank you very much and have a nice day!

Answer 1

The problem seems to be too complicated in order to apply some nice polynomial time solution. For example, you could solve it using some maximum-flow algorithm if you did not care about where the students are located, did not care about time fragmentations, etc. However, this will probably not result in the schedule you are most happy with. If you want to model the real world situation, assuming that you have small number of students (e.g. < 10) and you are available small number of hours (e.g. < 40), you should just do backtracking, (that is, brute force) in order to try different assignments and optimize whatever constraints you have. Since the run-time is exponential, you may eventually have to do some Branch and Bound optimizations.

No matter what approach you take, you will have to simplify or specify the problem in more concrete way. For example, if you decide that classes always starts at 2, 4, 6, or 8 o'clock, solving the problem will be much easier. You will also need to define a formula that gives the quality of the solution (e.g. total time teaching minus total time travelling). Modelling problems like this and writing solutions is usually fun, especially if you are programming or algorithmic enthusiast.