Time table Generation using Genetic Algorithms in java

Question

I am trying to seek a solution for timetable generation using Genetic Algorithms(GA). In my scenario i view a timetable of 6 days. Monday to Saturday.

Each day is divided into number of lectures/Time slots.(maximum no. of lectures are 6 in a day/Each time slot if 1 hr so that means 6 hours for a day)

I have tried to represent a Class consisting of Teacher,Student Group(set), and a lecture. I maintain a pool of possible teachers,possible subjects and possible student groups. And i randomly assign them to these Class.

so a Class is collection of all these references. so for each time slot we have the Class object representation in it. similarly a day is made up of number of lectures Class object representation. and so on with the week making up of 6 days.

A set of possible constraints that i have is:

1.A teacher can take only one lecture in one time slot
2.A teacher can take a set of subjects(finite)
3.A teacher can be unavailable on a certain day
4.A teacher can be unavailable on a certain timeslot

And other constraints as it may be included lately.

Can anyone give me a idea about how to represent these constraints or handle these constraints? and how to calculate the fitness scores depending on constraints?

EDIT : The implementation is here https://github.com/shridattz/dynamicTimeTable

Answer 1

UPDATE:

The code can be found here

github.com/shridattz/dynamicTimeTable

In my TimeTable Generation I have used A timetable object. This object consists of ClassRoom objects and the timetable schedule for each them also a fittness score for the timetable. Fittness score corresponds to the number of clashes the timetable has with respect to the other schedules for various classes.

ClassRoom object consists of week objects.Week objects consist of Days. and Days consists of Timeslots. TimeSlot has a lecture in which a subject,student group attending the lecture and professor teaching the subject is associated

This way I have represented the timetable as a chromosome.

And further on talking about the constraints, I have used composite design pattern, which make it well extendable to add or remove as many constraints.

in each constraint class the condition as specified in my question is checked between two timetable objects. If condition is satisfied i.e there is a clash is present then the score is incremented by one.

This way the timetable with the least Score is the Best we can get.

Answer 2

For this problem ther is no efficint solution. I think you got that too because you use genetic algorithms. I wrote some month ago a framework for genetic algorithm myself.
I think you missed: every class has a list of lessons per week and only one lesson can happen at a time. Now you can combine randomly teachers and classes for the timeslots.
In the fitnes function I'd give a huge plus if a class has all lessons to do a week. A big minus would be if teachers haven't simmilar load (teacher a has two lessons a week and teacher b 12 for example). This you might relativate if a teacher has to work just 20 hours a week (use %).
All in all it is not that trivial and you might look for an experienced co-worker or mentor to help you with this topic.
If you want more specific advises, please specify your question.