1 2 3 4 Previous Next 110 Replies Latest reply on Jan 31, 2011 8:45 AM by PhHein Go to original post
      • 15. Re: Optimized Time table generator algorithm
        By mind-mail?
        sabre, you're not the only one with the gift.
        ; )
        • 16. Re: Optimized Time table generator algorithm
          By mind-mail?
          sabre, you're not the only one with the gift.
          ; )
          • 17. Re: Optimized Time table generator algorithm
            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.

            • 18. Re: Optimized Time table generator algorithm
              Too bad this wasn't around when I had Physics 100 at 8 am on Saturdays.
              • 19. Re: Optimized Time table generator algorithm
                Please download the automatic timetable generator for schools from http://www.automatictimetable.com.
                This is a complete working program for school and college. This does automatic substitution and has different print options. This is the best time table software to download.
                • 20. Re: Optimized Time table generator algorithm
                  > This is the best time table
                  software to download.

                  Compared to what other applications?
                  I presume you are connected to the company that made that application?
                  Anyway, abuse reported for advertisement.
                  • 21. Re: Optimized Time table generator algorithm
                    please i want source code of school time table using visual basic .net so i need your help if you can tohelp me
                    • 22. Re: Optimized Time table generator algorithm
                      Could you please also send me the timetable generator code and/or algorithm ?
                      Many Thanks
                      • 23. Re: Optimized Time table generator algorithm
                        it would be of great help if u can mail me the timetable generatin algorithm and code .........
                        • 24. Re: Optimized Time table generator algorithm
                          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
                          numberOfSections = min + rnd.nextInt(max-min);
                          Open up that many sections. Now each one needs a prof that does that course so choose one at random
                          // 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
                          and every time you change something, you test for badness and tell the random number generator how bad that decision was
                          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.

                          • 25. Re: Optimized Time table generator algorithm
                            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 ;-)

                            kind regards,

                            • 26. Re: Optimized Time table generator algorithm
                              ps. Have a look here: http://www.aimms.com/aimms/index.cgi
                              I worked for that small company for some time and their modeling
                              system is just great. Together with a cplex problem solving engine
                              most roster problems are solved before you know it ;-)

                              kind regards,

                              • 27. Re: Optimized Time table generator algorithm
                                Yeah, send me a copy too while you're at it. Also
                                could you super size mine and hold the pickle.
                                Oddly enough, Wikipedia doesn't have a page about the phrase "morron magnet". Not even if you spell the first word correctly.
                                • 28. Re: Optimized Time table generator algorithm
                                  Yeah, send me a copy too while you're at it. Also
                                  could you super size mine and hold the pickle.
                                  Oddly enough, Wikipedia doesn't have a page about the
                                  phrase "morron magnet". Not even if you spell the first word correctly.
                                  Maybe 'strange attractor' would do the job? ;-)

                                  kind regards,

                                  • 29. Re: Optimized Time table generator algorithm
                                    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.
                                    Thanks anyway.
                                    1 2 3 4 Previous Next