I have a typical timetabling problem, but that some courses are offered more than once. Each student that want to take the course has to make the course exactly once.
Does anyone know a timetabling software that can handle this special timetabling problem?
i am not sure if i understand correct. maybe you can explain more detailed with an example?
Do you mean something like this?
Example:
In Year 1 are 500 students.
Only 100 of that students must have (want to have) activity (subject) "english".
But of course 100 students in a single activity are to much. So you want to splitt this into maybe 4 different courses.
So there are 4 courses (activity) with subject english (each with around 25 students.)
And you want to know how to do this courses (groups/subgroups) and activities?
... yes, you are exactly right.
And we use the flexibility that we have 4 different "English"-courses to avoid conflicts.
My setting is roughly as follows:
Each student (say about 100) selects 4 subjects out of a list of about 20 subjects.
Some subjects are chosen quite frequently, others only rarely.
Then, for each subject a number of offers (courses) is determined (roughly one course for every 20 students).
This is done by hand.
There are only 5 time-slots to schedule the courses.
The goal is that all (or at least as many as possible) choices of the students can be satisfied (without time conflicts).
There is no room- or teacher-planning.
There are some side constraints (like that the courses should have between 15 and 25 students).
Hope the problem becomes more clear now.
I am sorry to say, but that is a lesson planning problem and FET can't help you with that. You need to tell FET the lesson planning, because FET "only" generate the scheduling of your lesson planning.
You have a very complex problem. It's very difficult to solve your problem, because there is much more information needed. (How many teachers can teach subject X, ...).
Even without that Information your problem is very complex and even maybe unsolvable.
so i fear your manually prearrangement is still needed.
i guess you already care about this:
if maybe 80 students choose english and 20 of this students also choose biology, then you set of course 20 english students that have also biology in the same course and you don't "split" that.
Of course that is pretty difficult, because the students choose 4 subjects.
so i guess you start with the subject that got the most votes. Then you have a closer look to that guys and try to find a subject that is always selected by that guys. Then you set that guys to a single activity. Maybe you also do that with the 3th voted subject.
Maybe you already know better how to do that. Please just write me how you did it, because i am intressted to know how you do it.
i can just tell you this "hint".
First of all you should (must) solve your course problem. That is most imported. We also to that first, but our "problem" is much much more easy. You don't need to start adding "the other activities" if you didn't solve that problem.
So you can set constraint "beak" to nearly all time slots in FET. Just keep 5 time slots empty.
Now start thinking/adding your activities like you always did it manually. After adding a few activities try to generate a timetable. Hope FET is able to solve it. If FET fails, you must put the students into other courses or they must choose an other subject :-(.
This is very similar to the grouping problem which I attack before I actually start scheduling...
If you examine the shc file you will note there are core courses in each form...
and then there are variations in third and fourth form.
In order to do this we do a pre-registration survey of students in second to see what they would
like in third and then schedule based on the prereg... then when registration comes along there
are restrictions implemented... ie. only one class is allowed for History (35 max students)...
This does not force a student to sign up for what they signed up for in the prereg,
but the limitations are adopted from the prereg. So, if someone decides to sign up for Art even though
in the prereg they signed for Geography ... they need to sign up early or they are likely not to be
able to sign (first come first served)
regards,
les
QuoteThis is very similar to the grouping problem which I attack before I actually start scheduling...
If you examine the shc file you will note there are core courses in each form...
and then there are variations in third and fourth form.
In order to do this we do a pre-registration survey of students in second to see what they would
like in third and then schedule based on the prereg... then when registration comes along there
are restrictions implemented... ie. only one class is allowed for History (35 max students)...
This does not force a student to sign up for what they signed up for in the prereg,
but the limitations are adopted from the prereg. So, if someone decides to sign up for Art even though
in the prereg they signed for Geography ... they need to sign up early or they are likely not to be
able to sign (first come first served)
regards,
les
You could mention, Les (donjon), that you successfully solved your timetabling problem this way with FET, so that the user ah will know that he might be able to use FET with success. In fact, there are a few samples from Sacred Heart College into FET distribution, these are Les's files, which are solved correctly and fast enough.
QuoteYou could mention, Les (donjon), that you successfully solved your timetabling problem this way with FET, so that the user ah will know that he might be able to use FET with success. In fact, there are a few samples from Sacred Heart College into FET distribution, these are Les's files, which are solved correctly and fast enough.
Yes, I suppose I could :)
Before using FET, I was just using Mimosa and spent roughly three months working on the next school schedule (not full time, I'm a teacher too) With FET I now, spend about a week working on the def file, then add restrictions one at a time (to be sure that they do not cause insoluble problems) and then finally when all restrictions which can be placed are. I run 20 gens... choose the best rated, push it into Mimosa, then try and solve the little violations which are present.
Basically it takes me about two weeks to do what I used to spend 12 weeks working on :)
FET is an excellent tool for arriving at a fair schedule for all concerned.
regards,
Les
Thank you for your suggestions, but I can't change the system. The students select their courses and I have to schedule them.
I formulated the problem as an integer linear program and then solved it with standard software.
I was able to solve my problem in about 15min. But I think, this is only as a "perfect" solution (every student can get all selected courses) was found. If the problem has no perfect solution, the integer programming approach will fail to find a good solution
I still wonder, whether there is a timetabling-software where I can directly formulate my problem.
QuoteI still wonder, whether there is a timetabling-software where I can directly formulate my problem.
Many commercial timetabling software can't do that by default. You need to buy a "course planning" for that.
i currently know only one free (not open source) course planning software. But it has 1 or 2 problems:
1. The algorithm is not very good. Experienced humans can optimize the solutions (sometimes) very fast.
2. it's available only in German language
-Can you please name the tool (I am German)?
-Do you also know non-free tools (which have good algorithms)?
Thanks,
ah
Quote-Can you please name the tool (I am German)?
http://www.svws.nrw.de/html/kurs42.html
Quote-Do you also know non-free tools (which have good algorithms)?
Like i told: Our course planning is so easy that we don't need a course planning software for that. So i don't know if they are good or not.
But you can have a look into this forum and maybe also ask there, because there are more experienced guys that do course planning.
http://www.svws.nrw.de/cgi-bin/yabb2/YaBB.pl?board=kurs42;action=display;num=1210432364
Maybe also have a closer look to this. Here you can read (and ask) more about the quality of the course planning algorithm. Someone wrote more about the quality of the algorithm in that message:
http://www.svws.nrw.de/cgi-bin/yabb2/YaBB.pl?board=kurs42;action=display;num=1210432364
(There are also much more guys writing about the (bad) quality, but you can search yourself in that forum.)
I can only compare the timetabling algorithm. That author also wrote a free (not open source) timetabling software. But that algorithm is much more worse then the FET algorithm, so i fear even the course planning software is as bad as the timetabling algorithm, but there are schools working with that.
Unfortunately, I have this problem too. I have a bunch of people with pre-existing not-available times, and I'm trying to find the minimum set of meetings, so that each of them can go to one meeting.
I'm trying to define each person's attendance as a separate activity, and use the 'Activities must have the same starting time' constraint.
As long as there is a single meeting for everyone, FET finds it quickly, even breaking another 50% constraint. If there is not one meeting for everyone, it does not know what I want.
I am imagining extending the 'Activities must have the same starting time' constraint, to have a field for the maximum number of starting times, and the minimum number of students at each starting time, but I suspect that there are many things that I don't know, which would make this hard.
I am attaching my (non-solvable) definition file. Remove student 'john' to make it solvable.
QuoteUnfortunately, I have this problem too. I have a bunch of people with pre-existing not-available times, and I'm trying to find the minimum set of meetings, so that each of them can go to one meeting.
I'm trying to define each person's attendance as a separate activity, and use the 'Activities must have the same starting time' constraint.
As long as there is a single meeting for everyone, FET finds it quickly, even breaking another 50% constraint. If there is not one meeting for everyone, it does not know what I want.
I am imagining extending the 'Activities must have the same starting time' constraint, to have a field for the maximum number of starting times, and the minimum number of students at each starting time, but I suspect that there are many things that I don't know, which would make this hard.
I am attaching my (non-solvable) definition file. Remove student 'john' to make it solvable.
Your file is solvable if you reduce the weight for constraint acts same starting time to 99% or 95%.
When FET puts an activity, it checks that this activity can be put at the same starting time as the first activity in the constraint. In 0.01% of cases (when you have 99.99%), it skips this constraint and puts your activity in another slot.
If you have for instance A1 (slot x), A2 (slot x) and A3 (slot x) and must place A4, in 0.01%*0.01%*0.01% of cases it can put A4 in other slot than x.
If you have for instance A1 (slot x), A2 (slot x) and A3 (slot y) and must place A4, in 0.01%*0.01% of cases it can put A4 in slot y (skips x) and in 0.01% of cases it can put A4 in slot x (skips y) and in 0.01%*0.01%*0.01% of cases it can put A4 in other slot than x or y.
I'll think of your suggestion for extension, but it seems very difficult.
Your problem represents a different timetabling problem and probably another new program (an interesting program, possibly easier than FET).
I'll think of your problem. Meanwhile, I have a possible solution for you: suppose you have maximum 3 meetings possible. These meetings will be on 3 hours. You have 45 hours per week. You have 45 take 3 possibilities to choose these 3 slots. 45 take 3 = 45*44*43/6=14190 variants. Generate automatically all these 14190 possibilities (files) and give FET about 1 second per test or more to see if this test is possible. You could start in the order you prefer (leaving the solutions which use first or last slots of the day to be tried at last). You can exclude impossible cases, in which a student is not available in any of the three slots.
You could automatically generate these 14190 files, using different constraint break or activities preferred time slots, then run FET from command line, restricting the time to 1 or more seconds.
I could help you some more with some tweaks to FET, to implement this algorithm without the need to generate explicitly all the files, but only if the above procedure does not work and if I will have the time.
QuoteUnfortunately, I have this problem too. I have a bunch of people with pre-existing not-available times, and I'm trying to find the minimum set of meetings, so that each of them can go to one meeting.
I'm trying to define each person's attendance as a separate activity, and use the 'Activities must have the same starting time' constraint.
As long as there is a single meeting for everyone, FET finds it quickly, even breaking another 50% constraint. If there is not one meeting for everyone, it does not know what I want.
I am imagining extending the 'Activities must have the same starting time' constraint, to have a field for the maximum number of starting times, and the minimum number of students at each starting time, but I suspect that there are many things that I don't know, which would make this hard.
I am attaching my (non-solvable) definition file. Remove student 'john' to make it solvable.
I thought some more. It is a bit difficult, but not impossible, to add a constraint "all activities max hours per week" or similar, to restrict the number of all occupied slots to say x per week, to solve your problem by progressively reducing these slots with 1. Also, min activities per slot might be doable, I am not sure.
Reviving an old topic: please see http://lalescu.ro/liviu/fet/forum/index.php?topic=1633.0