2

I have the following problem to solve, perhaps you could give me some ideas regarding the problem - solving approach:

There are:

  • 8 classrooms
  • 16 teachers
  • 201 students
  • 149 parents
  • 241 appointments (most of the parents need to see multiple teachers, either because the have more than one child or because one child is being taught by two or more teachers)
  • 2 days.

  • For each day:

    • 7 classrooms are available for 20 hours per day.
    • 1 classroom is available for 10 hours per day.
  • Each teacher occupies one classroom

  • Each appointment lasts for one hour

Further constrains: - For each parent, all appointments must be sequential (having at maximum 1 hour pause) - Each parent should have to visit the school one day only. - For each teacher, all appointments within the day must be sequential (having at maximum 2 hours pause) - Out of the 16 teachers, 3 can only be present one of the two days.

I'm trying to find an approach to produce the appointments schedule, obviously without having to calculate all possible variations until all the requirements are met. Any ideas?

0

2 Answers 2

1

You need to define your constraints a bit more; i.e., what is the relationship between students and teachers? What is the relationship between students and parents? Do parents have to have individual appointments, or are the parents of a single student allowed to meet with a single teacher together?

I'd approach this with an initial (in testing) naive approach; just pick your highest constrained resource (looks like the teachers that can only be present for one of the two days), schedule those using the first available resources, and then continue through the set of resources, scheduling them using the first available resources that match their constraints and see if you can schedule the entire set. If not, you need to find your limiting resource(s), and apply some heuristics to your matching to find the best way to optimize those limited resources.

It's a bit of a tricky problem; have fun!

3
  • Regarding your questions, my data is spread into four tables: teachers (id, name), parents (id, name), students (id, name, parent_id) and students_teachers (student_id, parent_id). I don't think I can approach the problem as you suggest, simply because there's no free time available at all: the total hours for all teachers appointments equals to the total hours of classrooms availability.
    – Anax
    Nov 11, 2010 at 17:40
  • @anax: then it just sounds like your teachers are the place where you have to start your optimization. Allocate teachers to rooms, then allocate appointments to teachers using a recursive algorithm; when you come across a "cannot schedule" condition, back up the recursion tree until you come to a free path, then iterate down that one. Nov 11, 2010 at 18:13
  • That's what I had in mind. I only hope this darn thing finishes in "reasonable" time.
    – Anax
    Nov 11, 2010 at 21:18
0

Take a look at the curriculum course track of ITC2007 and it's implementation in Drools Planner or unitime. Both of them use meta-heuristics such as tabu search and simulated annealing.

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