Author Topic: My input file which need more than 20 hours to get a result (using the mapr_zt3)  (Read 285 times)

0 Members and 1 Guest are viewing this topic.

bin_wang

  • Level 1
  • *
  • Posts: 5
    • View Profile
Hello, All

     Here is my input file, which is used to do the course plan in A Chinese high school. Basically, I have 12 classes(or groups) and each class has more the 40 students. 
 
     every student has some required courses in his class, which he need to learn with his classmate. And he has some elective courses which he need to learn with other students in other classes.

     So I used the MAPR_ZT3 custom version to solve the problem. it worked out but it takes too much time.
 
     I attached the .fet file , it needs 25 or more hours to get a time table on my pc (i3 cpu + 8G ram) .

     I don't know if it's normal or not to take so many hours. So pls give me some advise or suggestions.

     Thanks a lot.



Volker Dirr

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 1863
    • View Profile
I didn't checked you file yet.

If you have got very difficult timetables, you might change your way of timetabling.

So far (if i have got dataset that solve in around 24 hours) i always just waited.

My current dataset is very difficult (even didn't solved after a week). So i changed my way of timetabling. Run generating multiple timetables. Each with ~20 minutes time limit. I done that on 4 cores at the same time (of course each one with a different file name). I got some results by that (and of course a lot of unsolved timetables). You might try that also.

An other variant for MAPR guys is to solve the elective courses first (so of course a very simplified timetable, just one hour per course). As soon as you got a result for that you can add the "correct" students set manualy to the activities (or better/faster: you know now which activities must be as the same time. so just place them at the same time and set the whole your into one activity). That will simplify the dataset; but it also mean a lot of manual (not automatic) work.

bin_wang

  • Level 1
  • *
  • Posts: 5
    • View Profile
Thanks Mr. Volker, I'll try the way you point out.

And I have another question ,  in the Activities I tried Equivalences setting but I found it doesn't help the result.

In fact whether or not I have the Equivalence set, the generation time is still long and the result looks like no change.

If the setting is no use in this new custom version 5.22 ? Because I found the help file is written in 2014.

Thanks!


Liviu Lalescu

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5107
  • FET author and forum moderator
    • View Profile
    • Homepage
I do not remember exactly what was the use of equivalences, but I think it was if the user had same starting hour constraints.

I think you need to leave your FET compute the result for a long time, I think you cannot let it only for a few minutes (Volker, I think your idea does not apply here).

Everything in the Help for mapr is still needed. You can also download the newer version, which has a new sentence in the Help for mapr: "Also, if you have not available times constraints for teachers, you need to add redundant not available times constraints for each of their proper rooms."

Remember to add redundant constraints. If some activities have same starting time constraints, other logical implications should be written.

FET-mapr is a very tricky version. Sometimes it works, sometimes it does not work, unfortunately. I added this information in the readme.txt file ( http://lalescu.ro/liviu/fet/download/custom/mapr/newer-mapr-asa10-zt3/readme-mapr-asa10-zt3.txt ) :
Quote
This is a slightly modified version of the older mapr-asa10. It is made for the user zt3 from the forum.

Please note that zt3's final file (which is not included in this package, and which requested that each split activity should be placed in the same room)
did not converge. Your success with the mapr version includes also a bit of luck.
« Last Edit: May 08, 2017, 04:28:01 AM by Liviu Lalescu »

Liviu Lalescu

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5107
  • FET author and forum moderator
    • View Profile
    • Homepage
I saw something which might help a bit: Isn't possible to add (redundant) same starting day for 10146 and 10156 (because you have same starting day 10141 with 10151, and same starting time 10141 with 10146 and 10151 with 10156)? And more constraints to add, similarly.

bin_wang

  • Level 1
  • *
  • Posts: 5
    • View Profile
Let me explain it:
10141 and 10151 are taught by same teacher and they must by taught on same day.
10141 and 10146 are set to same start time because I need to schedule 10141 to a real room.
And  for the same purpose  I add the constraint to 10151 and 10156.

Mr.Liviu, You mean if I add a constraint to 10146 and 10156, obviously it is redundant, it will be easier to get the timetable generated?
But why?

And actually I didn't set the equivalence activities , but the result looks no different.
Even I tried on the example file example-mapr-1-modified-liviu6.fet, I delete all the equivalence constrains, the generation is good too.


I saw something which might help a bit: Isn't possible to add (redundant) same starting day for 10146 and 10156 (because you have same starting day 10141 with 10151, and same starting time 10141 with 10146 and 10151 with 10156)? And more constraints to add, similarly.

Liviu Lalescu

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5107
  • FET author and forum moderator
    • View Profile
    • Homepage
Let me explain it:
10141 and 10151 are taught by same teacher and they must by taught on same day.
10141 and 10146 are set to same start time because I need to schedule 10141 to a real room.
And  for the same purpose  I add the constraint to 10151 and 10156.

Mr.Liviu, You mean if I add a constraint to 10146 and 10156, obviously it is redundant, it will be easier to get the timetable generated?
But why?


Because of the way the algorithm works. Say FET will firstly put 10146, then 10156 on another day. Then FET arrives at 10141 and 10151 and realizes that 10156 is on a wrong day, different from 10146, and needs to displace it. It is easier to go with a feasible timetable from the beginning, than to displace the activities after many other activities were placed.

For other input files which were impossible, adding all kinds of redundant constraints showed a clear improvement.

The best way to find out if it helps is to try.

Quote

And actually I didn't set the equivalence activities , but the result looks no different.
Even I tried on the example file example-mapr-1-modified-liviu6.fet, I delete all the equivalence constrains, the generation is good too.


I don't remember if using equivalence constraints helps, in your case. I think they are mainly useful if you allow skipping of activities (which you don't). Anyway, I saw you have activities split into 2,1,1,1,1, in which case you cannot add equivalences (or only for 1,1,1,1). Or, if I remember correctly, I added these equivalences for a file of jimmyjim which had all activities starting at the same hour.