Need help with university scheduling using Genetic Algorithm

[nizam27391]

Hi. I am to develop a Smart Scheduling System using Genetic Algorithm for my final year project.

But I don't quiet know where to start. I already red a lot of article about genetic algorithm but don't know how can I implement it into my project. I'm getting really frustrated with that.

So anybody can help guide me through this? I'm not hoping for codes ( seriously.. I know we all hate people asking for code )..

If there are any resources that I can use as my reference it will help.
Or is there anybody who can guide me by telling me what to do exactly..

p/s : yes. I did Mr.Google and understand some. But most of it are in form of research papers that strangled me more.

[gusano79]

To start with, you'll need a good idea of what a solution to the scheduling problem might look like. Do you have more requirements than "develop a smart scheduling system" for this project?

Once you know the basic "shape" of a solution, the important things to determine are

1. how to evaluate the effectiveness of a given solution (i.e., fitness function), and

2. how to encode a scheduling solution into "DNA" (i.e., genetic representation).

It's essential to get these two things right (or close enough) for a genetic algorithm to work well.

[nizam27391]

nice gusano! thanx for the tips. For the fitness function, that is one thing I don't quite understand. How to evaluate that the timetable is the most effective. Any idea?

Btw. for the second one, I encode it using ID of each element. I make as for example the first 2 digit is for the student, next 2 is the lecturer. Do you think it will work? Because I had an example from codeproject that use something like that,haven't code it yet but thats what in my mind.

[mike_2000_17]

How to evaluate that the timetable is the most effective. Any idea?

Well, you described your problem as a "smart scheduler". So, you must have some idea of the difference between a schedule produced by a stupid scheduler and one produced by a smart one. But, to create a working genetic algorithm, you need to transform that vague concept into an actual function that produces one number that describes that "fitness".

There are two things to consider here: validity and value. There is, of course, a possibility that a schedule in invalid, like having the same lecturer teaching two classes at the same time, or a student having to attend two classes on overlapping times. This is not easy to deal with in the case of genetic algorithms (or any other optimization algorithm for that matter). Ideally, what you should do is create a representation for your genes (DNA) that makes it impossible to produce invalid schedules, but that might be difficult. As much as possible, try to parametrize your system such that a "random" schedule is most likely a valid one. If random schedules are far more likely to be invalid, applying a genetic algorithm will be very difficult (i.e., it's like simulating evolution of a species with an extremely high mortality rate).

Now, for value, you have to figure out what are the things that are preferable for students and lecturers. Things like fullfilling all the credits, i.e., in a given candidate schedule, how many students end up with a time-conflict and how many lost credits does that represent (assuming the student has to attend one of the conflicting classes and drop the other and take it in another semester). Or maybe a measure of how spread out the classes are, e.g., students being stuck doing 6 hours of calculus on Monday only is worse than if they do 2 hours on Monday / Wednesday / Friday. You see, these things can be quantified, and then it is just a matter of putting reasonable "weights" to the different criteria (i.e., how important is loss credits vs. even load distribution).

If you have to deal with possible impossible schedules as part of the fitness function, you have to put a high negative value on any infraction of the "validity" rule. And then, require that the final solution does not contain any infractions at all.

I encode it using ID of each element. I make as for example the first 2 digit is for the student, next 2 is the lecturer. Do you think it will work?

I'm not sure I understand. It would be useful to have a more precise definition of what kind of schedule you are doing, and what assumption you are making. For example, a high-school schedule is very different from a University schedule. Remembering high-school, each teacher taught 1-3 different courses with a number of different groups of student (about 30) for each course, and each student had to get a complete curriculum. At University, each professor teaches 1 (maybe 2) courses for one group of students (sometimes as much as 300 students), and if students have time conflicts, they can just take the course at later term instead. That makes a big difference in the way you schedule things, for instance, in the University, they schedule courses based on the "average" student who is following the planned curriculum, and any student not falling in that category has to piece together his own schedule and deal with time-conflicts on his own. So, tell us more about what kind of schedule you need?

[SakuraCindy]

Hi Mike.. I dealt with the same system with nizam27391 here! Also using GA.

I'm building a automated timetable system for university. As you mention about the curriculum. I've detailed that out. But what about the encoding of data? The data consist of :
-groups -> keeps all the groups that will attend the event
-lecturer
-course -> list of course
-coursegroup ->list of course to be taken by a certain group

I keep it in database..so there is ID generated for each table.
Same question like nizam28391.. can I use the ID to represent the data to be use in GA?

Btw. If you have pseudocode for the university timetabling in GA, it will be much more appreciated!

Thanx
-Cindy-