This content has been marked as final. Show 110 replies
I have no code. I have a only hand wave of an algorithm.
I believe that a simple GA would deal with this: The only thing interesting I would do with the GA is that instead of having the genome encode room assignments and forcing the objective function to detect and punish overlap, I would instead have the genome encode a permutation of (a shuffle) of the rooms and then make assignments directly from the shuffled list of rooms. This way the constraint that assignments are unique is automatically met by any shuffle that the GA produces. The objective function, freed from detecting and eliminating overlap just encodes all the other random requirements and preferences for the assignment.
I think the more interesting thing here is less the algorithm that grovels over all the possibilities, but rather a way that something like this could be deployed.
Imagine a system that works like this. The school publishes the course listings. They publish a tentative list of courses to be taught. The professors log in, list the courses that they are capable of teaching. They also list their preferences. What they would like to teach, when they would like to have office hours, what they would like for free time. They also decide on course requirement like that this chemistry class requires a lab with Bunsen burners, that English class requires access to a Nuclear Reactor or Audio visual equipment. The GA starts hacking on the room and teacher assignments.
Students log in and sign up for classes. As courses fill up, new Sections are opened up, Teachers are found to cover these sections, rooms are shuffled around. The GA is just sitting there in the background day and night groveling over all the data trying to do the ideal assignment. Not so many people in that once popular Marxist Poetry class; move it to a smaller room.
At the start of all this all students and all professors are given points (based on seniority of course! Seniors get more points than juniors, full tenured professors got more than quiz section leaders) You, the chair of the philosophy department, actually likes to teach the Logic class, but really would prefer it on M W rather than T Th (because that is when you play racquetball) start spending your points to buy that class away from the jr faculty guy that it was first assigned to.
You are allowed at any time to move your allocated points around to support your preferences. This is like defining your character attributes in a D&D game. By default all your �preferences� get one point and your "rather nots" get minus one. These will just be added into the score of the objective function. If you didn't like some outcome, you start spending your points to increase how preferable or how disgusting you find something. The GA continues to grovel and shuffle, optimizing the objective function even as people keep changing it. You'd really rather teach only 2 classes this quarter instead of 5 so you can work on publication, pity you are only jr faculty, you get 5 anyway!
Students really DON'T want to take Calculus in the AM, the freak who usually teaches it really does prefer the morning. Everyone votes their points. If the market pressure is sufficient maybe Dr. John will come out of retirement and do an evening section.
No one likes a long jog all the way across campus between two back to back classes. You got stuck with a bad jog, well spend some of your funny money against it. Maybe the room will change, maybe the time. The GA is simultaneously trying to minimize all bad jogs for students and professors alike.
You really wanted to take Introduction to Drama taught by Prof Fox cause she is such a babe, but yesterday it changed (dramatically!) and now it looks like it will be taught at 6 AM by Prof Old, so you drop that and sign up for Political Philosophy of the Antarctic. You can log in any day and see what the current best assignment is, what you will be teaching or attending and when and where.
What you have here is a market place. Sections opening and closing based on demand. And presumably as you head toward the cut off date, the system will have converged (convergence can be forced in a couple ways either by limiting point motion in the last few days or by the gradual freezing of essentially stable choices - like the GA is forced to pay an increasing penalty for changing something that has been stable for days.) and then by the deadline, there you are, everybody assigned, and everyone just as happy as they can possibly be based on their point allocations and the trade offs on their conflicting desires.
Might I suggest that you future CS professors get right to work on this. After all, you do want the academic world to have adopted your open source version of this Genetic Course Selection software by the time you are through with graduate school. I mean you really do want them to adopt the course software that gives just a few extra allocation points to any professor that just happens to share your exact name.
After all, it is open source, I am sure that most CS types that bother to take a look would agree with your decision to give any CS faculty a few extra points and save the really big point allotment for those that can correctly answer the "Are you a Wizard?" question.
Yeah, send me a copy too while you're at it. Also could you super size mine and hold the pickle.
BTW, I especially like the security feature where you just guess where to send it to so that I don't have to reveal my mail address in a public space. That is so cool!!! Do you like have ESP or something. Can you teach me?
Oh, yeah, I need it written in Scheme with the source code comments all in urdu so my staff can work on it and the documentation written in nihongo so that I can sell it in my target market.
Let's see, am I forgetting anything? Oh yeah, all caps. THIS IS TOTALLY URGENT AND I NEED IT BY TOMORROW FOR THIS CLASS IM IN. SO PLS KIN U SND IT RITE NOW. :) 8-)
I'm still waiting.
Anyway, for those of you still interested in the design rather than the source code I have yet another suggestion.
Imagine that you have a magic random number generator that just always makes the right guesses.
Based on student demand, and the minimum and maximum number of students that are allowed in a calculus class you can calculate the minimum and maximum number of calculus sections that you would need, but how many should you open up?
Just use the magic random number generator
Open up that many sections. Now each one needs a prof that does that course so choose one at random
numberOfSections = min + rnd.nextInt(max-min);
and every time you change something, you test for badness and tell the random number generator how bad that decision was
// assign professor qualified to teach the course to the section section.prof = section.course.qualifiedProfs[rnd.nextInt(section.course.qualifiedProfs.length)]; // add that section to the professors course load section.prof.addSection(section);
moving right along assign a room/time to the section and test and severly penalize if you have double booked a professor. If you did double book a professor, don't worry about it. At some point the cumulative penalty cost for this assignement will be so bad that you will get a yerScrewed exception thrown and you can just abort the entire assignment process, create a new instance of the random number generator and try again.
If you are going on to also assign students to classes do so following the same methodology. Use the magic random number generator whenever you need to make a decision and penalize anything that looks bad.
When you are all done, you can see the total score and determine how bad or how good the final assignment was.
What this structure does for you is it allows you to write pretty straight forward code to generate an assignment. You write as much code as you can to make intelligent assignments but whenever you need to make a choice and you don't know what is right, you just use the random number generator to tell you the right course of action. You don't really look ahead and you don't backtrack, you just guess, assign, and score.
And the way the magic works is like this: The random number generator is of course not really a random number generator at all. Instead it is just a list of integers that is the genome for a single individual in a genetic algorithm pool. nextInt, just fetches out the next integer in the genome and mods it by the nextInt argument. When you create a new Rnd, you breed two members of the gene pool using the standard crossover and mutattion. Thus a given rnd is actually not random at all, it is a deterministic list that is breeding to be the right answers to the choices that are strewn all through the assignment code.
The addPenalty is just keeping the score for this one individual, so that you can compare him to the other members of the gene pool. This is the routine that knows the fitness of the stupidest individual in the gene pool and as it is accumulating a score for the latest rnd, it will pull the plug (throw the exception) if your current individual is lamer than the lamest of the lame.
So you structure your room assignment code however you wish. It matches all the things that you consider important. If you want to penalize awkward jogs between classes, you include x,y,z components for your rooms and you make an estimate of jog times, and you check how bad it is for each student and professor. If your campus is small you blow that all off.
What I am suggesting here is a method of using a GA that allows you to keep your assignment code as directly focused on the assignment problem as possible. When you are finished, your assignment code just assigns people to classes and room numbers to sections, consulting the oracle when necessary and by magic all the right decisions get made at just the right time.
You can't eliminate the interaction between the genomes and the problem solution, because they are essentially one and the same, but while it is difficult to see exactly how you would cross breed two different room assignments, it is easy to see how to crossbreed two oracles. The key is in recognizing that your assignment code that looked like it was consulting a magic random number generator is actually just decoding a genome into a set of room assignments.
One last comment - while it may be tempting to let the GA do all the work, it will work better the more you do to help it out. For example, I could just assign a random room to a section and if I am double booked stuff in a big penalty and waid for the GA to sort it all out. On the other hand if the oracle told me to stuff it into room 17, and I discover that room 17 is already booked, I could just treat 17 as the starting point for a search for an empty room, looking in 18, then 19 until I find one. It should be clear that the more you can do do avoid major problems up front, the more you can do to trim your search space so that you are not searching among absurd solutions, the sooner you will reach acceptable solutions.
So now that I has esplained you how easy am this code, y'all can quit asking us to mail it to ya, eh? This is an ALGORITHMS section, we don't write code here. We tell you how to write it and then you write it and send it to ME. GOT THAT! RIGHT NOW I AM NEEDING IT IN THE VERY SOON.
The 'classical' way of solving such a roster problem is model it as a
linear programming problem, solve the relaxation (no integer values
required) and continue using a branch-and-bound algorithm.
The first step is easy and very fast to solve (either by a simplex or interior
point algorithm) because there are almost no cost factors; teachers have
'preferred' hours and some classrooms are more 'suitable' than others given
the type of lecture to be given there.
Most if not all constraints are 0-1 constraints: one either allocates a
teacher and a classroom for some lecture or one doesn't. In this stage
the simple, sparse cost vector works against you because one solution
is as good as another causing the 'bound' step to fail on almost every
node of that giant tree to be examined. A feasible solution is often found
early in the 'branch' phase though.
It helps a lot if you define artificial cost factors on the infeasibilities, e.g.
a classroom allocated to a lot of teachers is worse than a classroom
allocated to just 1.4 teachers.
Sometimes this problem falls apart in two or more disjunct subproblems.
Bender's decomposition (sorry, no link) can be used then to optimise
those subproblems (which are smaller of course) further.
My personal experience is that simulated annealing and/or genetic
programming have a very slow convergence; but maybe I just goofed
while experimenting ;-)
I wonder if you obtained any good results in research for timetabling problem.
I am working on creating a course timetable for the University as my master's thesis. Barely started actually. Could you share the materials you gained with me? May be you have some basic algorithms, descriptions, examples of code.