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
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With