Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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
like image 866
Thea Avatar asked Jun 20 '10 06:06

Thea


1 Answers

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.

like image 183
Kasper Holdum Avatar answered Sep 20 '22 23:09

Kasper Holdum