Scheduling algorithm/problem

I'm bored, and this problem just haunted me again. Back at university, I used to always wonder how they schedule exams. The ability to schedule 10k student to do exams in 2 weeks and guarantee that no student will have an exam in two consecutive periods. I'm assuming some form of heuristics be applied.

I'm bored tonight, and if you give me the right tools, I'll work on it tonight and up to the weekend

cheer开发者_StackOverflow中文版s, dassouki

EDIT 1: I guess the assumption would be that all we know is the following:

1. Number of students and the courses that they're each enrolled in
2. Number of exam period spots

This is a famous computer science problem (the exam scheduling problem) which is known to be NP-hard. You might not be able to solve it over a weekend.

I know this is off-topic for SO, but my university simply scheduled the exams in blocks that matched the class times. So, everyone who had a class MWF at 1:20pm was in an exam on the 15th at 1:00pm. Since you can't take two classes at the same time, it was impossible to have exam conflicts.

This is an example of a constraint satisfaction problem, which is a difficult class of problems. Some of them are in the class NP. Large commercial software packages exist for trying to solve problems like these (eg CPLEX) - and in general, they use some mathematics and lots of heuristics.

I used the tabu search during my master. The idea is not too complicated:

1. start from one possible solution (anyone) and pounder the it (e.g. give -1000 points if one student has two exams at the same time)
2. change that solution by just changing a few assignments and recalculate the ponderation
3. if 2. is better than 1. and repeat starting with 2. as the root solution

if you're blocked, you can "visit" other solutions by making important changes to the initial solution.

It's expensive, but I've seen CPLEX used for similar types of problems.

The problem can actually be a bit more general than that. For instance, at my school, exams are scheduled by when the class is scheduled - i.e. all classes which meet at the same time normally during the semester, have an exam scheduled in a certain block of the exam week (not necessarily the same time as the regular class meeting, however). Thus, conflicts generally don't exist since students wouldn't be attending two classes in the same meeting time for obvious reasons, and thus wouldn't have two exams at the same time.

However, this means that then you still need to schedule classes so that they don't conflict. :)

When I was a senior in college, we did a final project in our AI class similar to this. We wrote a (barely) working system to schedule classes in buildings at appropriate times. Certain rules could not be violated: if the prof. needed a multimedia classroom, he got one. If it was a CS class, then it shouldn't be scheduled in the Art building. Profs shoulnd't have more than 2 hours between a class, etc.

We used a genetic algorithm.

A few things to make the problem simpler. You can probably shrink the number of "units to schedule" down from tens of thousands to a few hundred, by looking at people who are sitting the same set of exams. If you have 300 people who all are sitting "Introduction to Computer Science" and "Maths for CS students", you can schedule all 300 as a single unit, because they will all have the same constraints and you (probably) do not want identical exams to be given in multiple slots.

Drools Planner has an exam scheduling example (called examination, see download and reference manual). The problem is specified in the ITC2007 competition track 1.

This is an application of the graph coloring problem. This problem can be represented as a graph where every vertex is a course and an edge between two vertices mean there is a common student enrolled in both courses. So this is a graph coloring problem where minimum number of time slots is equal to the minimum number of color required for coloring the vertices of the graph such way that no two adjacent vertices share the same color.