This discussion is archived
1 2 3 4 5 6 8 Previous Next 110 Replies Latest reply: Jan 31, 2011 12:45 AM by PhHein Go to original post RSS
  • 45. Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    thanx for the suggestion prometheuzz.
    i too am trying for the same.,i asked the code so that i can get some references from that.

    Anyway,can anybody help in giving idea as to how to allocate timetable automatically for the faculties in acollege given faulties,courses,departments,subjects....
    conditions would be lik:
    "No lecturers should have the classes at the same time in two diffrent sections or semestres."
    "No lectureres should have continuous two or three classes and each should be given a break of atleat one hour"
    "Each faculties should have maximum of 5 classes a day"


    my mailid is frailcanoe_sea@yahoo.com
  • 46. Re: Time table generator algorithm
    800282 Newbie
    Currently Being Moderated
    > thanx for the suggestion prometheuzz.
    i too am trying for the same.,i asked the code so
    that i can get some references from that.

    marlin314 should be the one you're thanking; he contributed the most valuable posts in this thread. Read them if you're really interested in creating a time table generator.


    > Anyway,can anybody help in giving idea as to
    ...

    Again: there are a lot of valuable posts in this thread already. Is there something in particular you don't understand about them?


    > my mailid is frailcanoe_sea@yahoo.com

    Sorry, but this is a public forum. I don't think anyone is interested in personally e-mailing you about your assignment.
  • 47. Re: Optimized Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    Thanx merlin..

    Actually,i am trying to mak it as simple as possible..
    To avoid more complexities,i am designing it only by taking faculties,departments,subjects,because,we hav no idea to release dat in the market,just as an assignment dats al..!!

    I have already designed front end for the proj,whch vl tak Subjects,faculties,new courses and departments and store those in respective databases.

    I am now tryng to allocate timetable faculties by myself manully and store it in a database.
    then,retrieving al those,details from the database which were stored, along with the time(pre stored database) in which they vl teach.

    I am facing difficulties in this part actually..!!
    "No faculty should hav the classes at diff semesters at the same time"
    "Every faculty should hav atleast some break period after each class"
    "Not max of 5 clsses to a faculty per day"
    etc............
  • 48. Re: Optimized Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    Build a roster, a large array something like this

    Mtg[iRoom][iDay][iTime] roster;

    Every single course will have some number of meetings and each mtg must be assigned to the roster. The roster will have nulls that represent at time and a day when a given room is empty. You can just put all your meeting for all your classes into the roster in any random order at all and you now have a solution that complies with the constraints that each class has the right number of meetings and there is no overlap.

    You do as little or as much modeling of real concerns as pleases you. For example in the real schools that I know, you do not put a Chem lab of 20 people into a lecture hall that seats 300. Rooms have capacities and facilities and they should be properly matched.

    Once you have all mtgs in the roster, you have a potential solution. That solution may be quite bad - a class that was supposed to meet 5 days a week has all 5 of those meetings on Monday - you may have professors double booked for their time - you may have all 5 meetings for a single class correctly done on different days, but they are all in different rooms and at different times.

    So you also need a notion of score, how bad a solution really is. You could rip through all the meetings once you have them assigned and give a penalty for anything that you don't like.

    Once you have a score functions, the important thing to note is that you can swap any two elements in the roster and get another possible solution. You can do these swaps semi-intellegently if you wish. What I mean is that while you are calculating your score, you may note that a particular mtg does not match the room requirement, or it leads to a professor being double booked or something. That room should be swapped out. Furthermore you may know better places for that thing (if you are dealing with capacity, and you have a course of 200, you don't waste time trying to swap that mtg into a small room, you restrict your swap sites to rooms that match the constraints)

    In any case the observation is that you have a roster, which represents a solution, you have a score, which grovels over your roster and checks for every violated constraint and assignes a penalty for that violation (some things are bad and others are REALLY bad) and you can swap roster elements to generate a new potential solution.

    Now you have something toward which you can apply a genetic algorithm or a simulated anealing to do the groveling about looking for solutions.

    I will describe simulated anealing because it is fairly straight forward. You have a working copy of your roster and its score and you also have a saved copy of the roster which is the best that you have yet seen. You perform a swap (intelligent or random) in your working copy and score the results. If what you have is better than your best so far, you save it. Otherwise you make another swap. You count how many swaps you make and at some point, your swap limit, you decide you have made too many random changes and so you reload your working copy from your saved - best so far - copy. What you are doing is taking random walks away from your best solution and seeing if you can't find a series of swaps that improves it.

    The anealing comes from one other thing that you do. It is observed that in the early stages when your solutions are bad that you may need to take large random walks to get an improvement. As your solutions become more refined, you want to do more short searches right around the best so far. So you start with a large swap limit (before you reload) and over time you decrease the swap limit.

    The primary chunk of work that you need to do is to build your data structures and score function. I can not tell you how to grovel over your data structures in an efficient manner so that you can determine that you have a double booked professor. I don't know what data structures you have and I don't know what constraints you are trying to match. A partial list of a few constraints is not a design.

    In all optimization problems you must:

    1) Define the buckets that hold the fixed data. That design should allow you easily get from one required chunk of information to another.
    2) You must render all constraints into a score function that measures whether a constraint is being met by a potential solution. Ideally that score function is quick to compute (otherwise - you won't be able to grovel of millions of potential solutions).
    3) You define some buckets to hold the proto-solution. Ideally this data structure is defined in such a way that it forces as many constraints to be satisfied as is possible. Generally you choose something like the hardest constraint to measure or the hardest one to meet. Assigning rooms to classes at certain times of the day with no overlap strikes me as the hardest problem and is thus the reason for building the roster structure that I suggested.

    Then using your favorite optimization technique, linear programming, simulated anealing, genetic algorithms, etc. you grovel over as many feasible solutions as you can as quickly as you can looking for the one with the best score. In the fastest methods, you will be able to take incremental steps (like doing a swap in the roster) you will be able to computer incremental scores (so computation after a single step is potentially fast) and if possible you can see some gradients (meaning that sometimes you can even know which direction to take a step to improve a score - like knowing that a swap will improve a match.)

    You will note that my roster design does nothing to assign professors to classes. This is the reason that I keep re-iterating that there is NO time table code. Are professors already assigned to classes? Then you must move classes around to prevent double booking them. Are the classes already assigned rooms and you are moving professors around to prevent double booking them? Can any professor teach any class? Do you have extra contraints that a professor only teaches classes for which he is qualified? Does your system model assigning teachers to classes or not? Do your teachers have seniority and class preferences? If you need to do this, then you need to do this, but I can't help in the design of a system when the goals of that system are not defined.

    In fact, you should note that there is nothing magic about my roster data structure. It is there becasue I assumed that one of the assignements that you are trying to do is get all classes into rooms without having two classes in the same room at the same time. I just assumed that this is the major constraint. But of course I have no reason to make that assumption because there is NO problem that has actually been defined anywhere in this thread by any writer.

    Defining you data model and your constraints IS the definition of your problem. Once you have that, right or wrong it will be possible for others to comment on it and refine it and improve it. But without that ...
  • 49. Re: Optimized Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    hi i am doing a project almost same of urs. if u find out the solutions until now pls send it to me also
    my mail is : cyberturk01@yahoo.com
    thank u very much
  • 50. Re: Optimized Time table generator algorithm
    800282 Newbie
    Currently Being Moderated
    > hi i am doing a project almost same of urs.

    Who is urs, or better yet: who is yours?
  • 51. Re: Optimized Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    I also need this code very badly. I am not a student and this is not a homework assignemt, but I've been telling people for months that I can help them write this code and I've been waiting and waiting but no one posts anything I can use so I still don't have any code yet. If you could please post it here, I can claim that I did it.

    Thanks ever so much!
  • 52. Re: Optimized Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    Hi,
    Please sene me the optimized time table generator algorithm.
  • 53. Re: Optimized Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    ya i am in need for an algorithm or code for school time table generation
    it is required as
    classes
    labs
    time table for teacher
  • 54. Re: Optimized Time table generator algorithm
    800282 Newbie
    Currently Being Moderated
    Hi,
    Please sene me the optimized time table generator
    algorithm.
    I�ve sent it to you. Have fun with it.
  • 55. Re: Optimized Time table generator algorithm
    800282 Newbie
    Currently Being Moderated
    ya i am in need for an algorithm or code for school
    time table generation
    it is required as
    classes
    labs
    time table for teacher
    I�ve just sent it to DileepBellamkonda and removed my local copy of it. Ask him for the code.
  • 56. Re: Optimized Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    time table algorithms
  • 57. Re: Optimized Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    guys i've seen all the postings ... we are currently devoloping the same project using DB2 ... the algo given by u people use the standard arrays ... can u people please guide me as to what is to be done using this database... and how to link the front end and backe end
  • 58. Re: Optimized Time table generator algorithm
    800282 Newbie
    Currently Being Moderated
    can u people please guide me as to what is to be done using
    this database... and how to link the front end and
    backe end
    I doubt you will get help here on implementing this with DB2. This is the algorithms forum, and DB2 has little to do with Java.

    I suggest going to: http://www-128.ibm.com/developerworks/forums/db2_forums.jsp

    Of course, someone may be willing to help you here, but I doubt it.
  • 59. Re: Optimized Time table generator algorithm
    843853 Newbie
    Currently Being Moderated
    Hi marlin,
    first of al,thanx for everything..

    I have done with the timetable generation algorithm......
    But, the only thing is i dint made it automated completely..
    At first, actually,i dint got the correct idea and i started blindly.,that resulted in the Unautomated algorithm.

    I wrote the algorithm in which we have to assign the timings and days for the faculties. I know this is not the automated generation but, initially
    i got only this idea.. and its working fine too.
    Now am trying to make it completely Automated, that is without assigning times and days for the lecturers..

    One more thing i have considered only theory classes and nothing else....! i know this is not right, but to start from the stage of beginner it will be very difficult. thats y i started it like that.

    Now i got the confidence that i can do that....
    and i am considering all the constraints like sections, class rooms, labs etc....... but, i am finding bit complexity in that..
    So, can u help me with respect to that..??!!
1 2 3 4 5 6 8 Previous Next