Is there an algorithm that creates of university timetable for the whole semester?

Question

Hi All,

I have to implement an algorithm that generates a timetable for a university. I've searched and found a lot of algorithms. But here is the problem. I need an algorithm that generates a timetable for the whole semester, not on a weekly base. It should also consider the predefined order of the course's parts, e.g. exercise 1 should be after lecture 2 and before lecture 3. Do you have any suggestions?

Thanks.

UPDATE:
I have the following hard constraints:
H1: Only one course part is assigned to each room at any time slot.
H2: The room can host all attending students and satisfies all features required by the event.
H3: No student attends mode than one course at the same time (at least the obligatory courses)
H4: No teacher teaches more than one course part at the same time.

The soft constraints are:
S1: A course part should be not allocated to a time slot inconvenient for a lecturer.
S2: There should be a minimal number of gaps between classes of a teacher.
S3: There should be a minimal number of gaps between classes for student.
S4: Classes should satisfy lecturer preferences - days and time slots.
S5: Course parts should be scheduled to predefine order.

Example:
Course "Software architecture"

Week No   Course    Room    Course Part   Day       Time
--------+---------+-------+--------------+----------+-----
Week 1:   SA        435     Lecture 1     Wednesday  8.15-11
Week 2:   SA        435     Lecture 2     Wednesday  8.15-11
Week 3:   SA        47      Lab 1         Monday     13-15
Week 3:   SA        436     Lecture 3     Wednesday  11-14
Week 4:   SA        243     Exercise 1    Monday     13-15
Week 5:   SA        436     Lecture 4     Wednesday  8.15-11

Answer 1

You might want to look into interval scheduling. It sounds like you would need a modified version that added some constraints such as where the exercises are allowed to be placed. Greedy algorithms are usually rather easy to modify, and there's a whole bunch of already modified versions of the basic IS algorithm.

Answer 2

IIRC such a problem is not entirely solveable by algorithm.

Answer 3

I ended up with a modified algorithm of the one suggested here. I used the Iterative Forward Algorithm and then applied the simulated annealing for the soft constraints. I changed the timeslots set, so that it contains the whole set of timeslots for the semester without the weekends and the holidays. For example, if the semester has 6 weeks and for each week I have 40 hours, then my set of timeslots will contain the whole 240 timeslots.

I also added a constraint for the order. When this constraint is not satisfied then it put a high weight for the current solution. In this way I prevent the algorithm to choose a solution with courses that are not in the with order.