6

I'm considering a hypothetical problem, and looking for guidance on how to approach solving the problem, from an algorithmic point of view.

The Problem:

Consider a university. You have the following objects:

  • Teaching staff. Each staff member teaches one or more papers.
  • Students. Each student takes one or more papers.
  • Rooms. Rooms hold a certain number of students, and contain certain types of equipment.
  • Papers. Require a certain type of equipment, and a certain amount of time each week.

Given information about enrollments (i.e.- how many students are enrolled in each paper, and what staff are allocated to teach each paper), how can I compute a timetable that obeys the following restrictions:

  1. Staff can only teach one thing at once.
  2. Students can only attend one paper at once.
  3. Rooms can only hold a certain number of students.
  4. Papers that require a certain type of equipment can only be held in in a room that provides that type of equipment.
  5. Hours of operation are Monday to Friday, 8-12 and 1-5.

Discussion:

In reality I'm not too concerned with the situation outlined above - it's the general class of problem that I'm curious about. At first glance It seems to me like a good fit for a genetic algorithm, but the fitness function for such an algorithm would be incredibly complex.

What's a good approach for trying to solve this kind of constraint-satisfying problem?

I guess there's probably no way to solve this perfectly, since students may well take a combination of papers that leads to impossible situations, especially as the number of students & papers grows.

Thomi
  • 11,647
  • 13
  • 72
  • 110

2 Answers2

3

Staying on genetic algorithms, I don't think the fitness function for this would be very complex, quite the opposite.

You basically just check your candidate solution (whatever the encoding) for each of the constraints (you only have 5) and assign a weight to them so that when a constraint is not satisfied the weight is added to a total score that could represent fitness.

In such a scenario you just minimize the fitness function (because best fitness possible is 0, meaning all the constraints are satisfied) and let the GA crunch the numbers.

The encoding will take a bit of figuring out, but once that's done it should be straightforward, unless I am missing something, of course :)

JohnIdol
  • 48,899
  • 61
  • 158
  • 242
  • ...you may be. While there are only 5 constraints, there are potentially thousands of students, hundreds of papers, hundreds of rooms, and hundreds of staff. The complexity of checking all those constraints against each other is, I think, the original problem - we've now just moved it along. – Thomi Jan 30 '11 at 18:54
  • My point is that I wouldn't discard GAs simply because the fitness function is complex, since you'll have to work that complexity either way (by leveraging given formal methods or whatever), GAs or not. – JohnIdol Jan 31 '11 at 11:59
2

A very restricted version of this problem is NP-Complete.

Consider the case when exactly one student can take a paper.

Now for a given time slot (say the paper is taught all day), you can construct a 3-partite graph, with Rooms, Papers and Students, with an edge between a paper and a student if that student wants to take it. Also add edges between a paper and it's possible rooms.

We now see that the 3 Dimensional matching problem is an instance of your problem: you need to pick a non-overlapping (student, paper, room) combination for that particular timeslot.

You are probably better off with some heuristics for the general problem. Sorry, I can't help you there.

Hope that helps.