Hi again!
I'm using the MAPR version to help with my scheduling, but I'm using it in a slightly different way than it is designed to be used.
In my school, when students enter year 10, they choose some of their courses. Specifically, they get 5 choices. The choices can be biology, chemistry, physics, gym, drama, music, history, geography, graphic design, computer science, etc. All choices meet for the same number of periods per week. Some choices have multiple sections. For example, one section of biology is taught by Mrs. X, and another by Mrs. Y; each section is its own set of activities in "normal" FET terms. Some choices only have one section, e.g. drama is only taught by Mr. Z, and there is only one set of activities (normal FET).
The goal is to arrange courses such that the correct combinations of courses are taught simultaneously to maximize student happiness. These simultaneous groupings are called "blocks." For example, maybe it works out that a good pattern is like this:
Block A: chemistry (Mr. A), history (Mr. B), design technology, graphic design, economics
Block B: PE (Mrs. L), physics (Mr. S), economics, combined science
Block C: computer science, business, geography, biology (Mrs. Y), art
Block D: ICT, biology (Mrs. X), PE
Block E: chemistry (Mr. C), drama, geography, physics (Mr. R), music
Each student ends up taking one class in each block, and, ideally, students end up being able to take all of the classes they want. It is very, very unlikely that a solution is possible with 100% student happiness, but assume for a moment that it is possible for a set of data. Here's how I configured FET:
General structure: 1 day per week, 5 periods per day
Students: year groups are real students, e.g. Alan, Bob, Carl, etc.
Subjects: real subjects
Rooms: individual meetings of classes. For example, if a course is taught only by one staff member, and there's only one section of the course, then I call the room "Mr. Q - economics." If there are multiple teachers, say for biology, each one gets its own FET room: "Mrs. X - biology" and "Mrs. Y - biology."
Activities: each student chooses 5 activities by subject, e.g. Alan has one activity with biology, one with drama, etc.
I used the constraint "a subject has a preferred room" if there is only one section of the course, and I used "a subject has a set of preferred rooms" if there are multiple sections. For example, subject "biology" has multiple "rooms": "Mrs. X - biology" and "Mrs. Y - biology."
I also used the constraint "a room's max occupied slots" and set it equal to 1.
This setup works. If there exists a PERFECT solution, FET will find it.
I want to come up with a method for the real-world case when there is NO perfect solution. How can I get FET to generate the "best" timetable possible without getting hung up on trying to schedule EVERY activity? I know that I can try "allow skipping of activities," but in that case, FET doesn't try very hard to schedule an activity. Ideally, I want FET to try to schedule each activity for "n" minutes, and then after "n" minutes, skip that activity and move on. Or try for "m" attempts, or something like that. I will have a total of ~500 activities. If FET can place 490 of them, I can look at the remaining 10 and speak with those students and see if they are willing to change some of their choices.
Is there a way to make this happen?
I would be willing to send my data, but it is not anonymous at the moment, therefore I ask you not to post it.
Liviu is in charge with the MAPR version, I think he can answer your questions. But Liviu isn't available by Internet at the moment. So please wait a few days.
hmmm... maybe i am wrong. please check carefully.
Why not this:
You modify the "a subject has a preferred room" and just lower the weight to 99,9...%.
Maybe a pseudo room is needed to avoid to many impossible rooms/choices?
So adding a pseudo room and also adding some more constraint. Similar to the above one, just with a "a subject has a preferred roomS" with your normal room and the pseudo room (weight 100%).
Hi Volker, thanks for your reply. Your suggestion sounds good. I will try it.
If FET finds a conflict for subject has a preferred room (or set of preferred rooms), does it simply assign that activity to a time but not a space?
If you do it with lower then 100% room constraint? yes.
If you do it with 100% room constraint? no.
(That's why it is maybe better to add 2 constraints. One with 100% and one with a lower value.)
I don't think I understand.
First, I tried to run without pseudo rooms, just selecting a subject has a preferred room/set of rooms at 99%. Things were working as anticipated. I am familiar with how FET deals with constraints based on the general FET help file. With the 99% set, FET runs and then reaches a difficult (impossible?) activity and tries for n attempts before moving on. So maybe it reaches the first difficult attempt after running for 1 minute. By minute 2, FET identifies that activity as difficult and moves on. But then it reaches another difficult one and doesn't move on until minute 4. Then another difficult one, and it takes until minute 8. Then 16. Then 32. Then 64. At the moment, my simulation has been running for 4.5 hours (still going). FET "got stuck" at 4 minutes, 8 minutes, 15 minutes, 30 minutes, 1 hour, and 2 hours, just like I said above. I can sort of understand why, but I don't think this is a good solution.
Can you please explain more how pseudo rooms solves the problem? Specifically, how does FET know NOT to assign an activity to a pseudo room unless it can't assign that activity to a MAPR-"real"-room, which in itself is a meeting of an activity?
Quote from: ChicagoPianoTuner on May 01, 2015, 08:10:19 PM... but I don't think this is a good solution.
Why do you think that?
Because of time (to slow?) -> maybe use a lower value then 99%.
Because of to many conflicts? -> maybe increase the weight. (Or use a pseudo room.)
Quote from: ChicagoPianoTuner on May 01, 2015, 08:10:19 PMCan you please explain more how pseudo rooms solves the problem? Specifically, how does FET know NOT to assign an activity to a pseudo room unless it can't assign that activity to a MAPR-"real"-room, which in itself is a meeting of an activity?
I didn't tried yet. I was just thinking. Maybe I am wrong.
But if you use only one room with 99% weight, then it might happen then that many activities get conflicts.
So my idea is to add 100% constraints. By adding a constraint with the "normal" room and a pseudo room with 100%, there shouldn't be so many conflicts (students that doesn't get their choice). Of course this mean it will take longer to generate. So you won't speed up the algorithm by that, you will max improve the quality of the result.
Maybe I am overreacting about the time taking too long. The idea of 99% weight might work just fine, or I'll adjust it as necessary. But I've found another problem.
I let FET run overnight and it completed the timetable in 14 hours, which is fine. But in looking at the solution, there are some errors. I must not have a constraint set correctly. For example, a student has NO activities assigned to a "room", yet there is available space in a "room" at the same time the student is scheduled to take a subject that is assigned to that "room." Any ideas why this may be happening?
That is sadly a behaviour that happen sometimes; even with normal FET version if you use room constraints lower then 100%.
Maybe Liviu can check one more time how to avoid that, but he isn't available at the moment.
I just arrived home. I am sorry, I was away. Please let me read, then I'll answer more (tonight or tomorrow).
Quote from: ChicagoPianoTuner on May 02, 2015, 01:07:11 PM
Maybe I am overreacting about the time taking too long. The idea of 99% weight might work just fine, or I'll adjust it as necessary. But I've found another problem.
I let FET run overnight and it completed the timetable in 14 hours, which is fine. But in looking at the solution, there are some errors. I must not have a constraint set correctly. For example, a student has NO activities assigned to a "room", yet there is available space in a "room" at the same time the student is scheduled to take a subject that is assigned to that "room." Any ideas why this may be happening?
Quote from: Volker Dirr on May 02, 2015, 08:48:07 PM
That is sadly a behaviour that happen sometimes; even with normal FET version if you use room constraints lower then 100%.
Maybe Liviu can check one more time how to avoid that, but he isn't available at the moment.
Yes, if I understand correctly (I am tired), it is a normal behaviour even to official FET. A way to improve/solve it: Open the _data_and_timetable.fet and generate again on it, and maybe again. The unoccupied rooms will be probably occupied now.
About modifying the custom mapr-asa version to make it skip more rarely (less) than the mapr-asa version, I think it might be possible.
if you open the _data_and_timetable.data (so with fixed rooms and times), you can also increase that 99% values up to 99,99...%. So you (maybe) need to run it only a single time.