genetic algorithm for class schedule composition

Question

I'm writing an application for automatic university schedule composition and using for this genetic algorithm. But now I faced some problems with realization.

At the very begining I assumed that we have classes with duration of 1 time slot (time slot = 1 hour) and we can simply put it in array (represents schedule grid: 1-d array with capacity of numberOfRooms*numberOfDays*numberOfTimeslots) and can perform mutation and crossover as well with no problems.

But know I want to improve the application and allow having classes with duration of several time slots. Here comes a lot of problems:

How can we put one class object in an array and fill all the slots (several array cells) which class must occupy (one object - several cells)? And in compliance with how we will put it in the array, how mutation and crossover operation can be performed? Thanks in advance! I really appreciate your help!

Answer 1

A good rule could be crossing over only classes that have equal time slots. For example, you can cross over a class that takes two time slots with two classes that take one time slot.

To represent classes having duration of many time slots, the simplest but tricky way is having a flag that for each time slot will tell you if the time slot is occupied by a new class or just a continuation of a class that started before. When you cross over you will watch that flag to make sure you are not crossing parts of classes.

Another (better) way is creating a more complex data structure: DailyRoomOccupation. This data structure will contain:

• the daily capacity of the room, expressed in number of time slots;
• a (double linked) list of classes scheduled for that day in that room;
• a function that calculates if the classes in the list will fit into the time slots;
• a function that permits to cross-over two different DailyRoomOccupations, taking care of crossing over only equal quantities of time slots.