Here are 2 examples of the same database, the difference is the weight of min days between activities.
the first;
weight = 100%;
production time = 2H 6min 54s,
number of conflicts = 0
random seed: X=105528721, Y=662445328
the second;
weight = 95%,
production time= 5min 33s.
number of conflicts = 9;
random seed: X=2105598204, Y=300887750
in the 2 examples FET has produced very good timetables. but the difference is the time!
to you to make the conclusion?
(the version used is the Moroccan version)
yes. that is ok.
I will run them as well.
Would you like me to add them to the next Morocco version, as example files?
Quote from: Liviu Lalescu on April 14, 2018, 08:28:57 PM
I will run them as well.
Would you like me to add them to the next Morocco version, as example files?
I agree :)
For the file which has weights under 100% you can try starting with X=123, Y=123. It took 30 minutes 12 seconds on my computer, which seems similar to your computer (because starting with X=2105598204, Y=300887750 it took ~5 minutes).
It is sometimes luck.
Quote from: Liviu Lalescu on April 14, 2018, 09:10:04 PM
For the file which has weights under 100% you can try starting with X=123, Y=123. It took 30 minutes 12 seconds on my computer, which seems similar to your computer (because starting with X=2105598204, Y=300887750 it took ~5 minutes).
It is sometimes luck.
your computer is faster than mine, it took 32 min.
yes the time is relative, and it appears that we can not control it. it depends on luck!!! :(
I did another test with the first file weight = 100%. the result is surprising, the time is 43min.
I used the same random seed of the second file cited above.
Conclusion: the random seed has an impact on the speed of generation.
That's for sure, Benahmed.
As far as I understand:
1. the algorithm randomly places an activity in the timetable,
2. then checks if there is any constraint conflict;
3. if a constraint is broken, it randomly chooses to remove one of conflicting activities
Corrections:
1. It places recursively an activity so that the conflicts with the already added activities are minimum (but at level 0 of placing it might break this rule, to avoid cycling).
3. It removes ALL conflicting activities.
Thank you for clarifications, Liviu.
surprise or good news, the first file with 100% weight is resolved in record time; 12 min 43s.
same random seeds of the second file cited above :
X=2105598204,
Y=300887750
only one small change: the activity ID = 533 and ID = 534 fixed in time by the constraint: acttivity has a preferred starting time instead of the constraint: activity has a set of preferred starting time.
I attach below the file and a screenshot of FET showing the end of generation
1) I examined the previous file and this file. The activities 533 and 534 have the same constraint for them, activity preferred starting time.
2) It is only luck. You can start the generation with any random seed, obtaining any generation time. If the file is only slightly different, you will obtain very different running behaviors even with the same random seed.
I am sorry that I cannot explain better.
Quote from: Liviu Lalescu on April 16, 2018, 08:11:07 PM
1) I examined the previous file and this file. The activities 533 and 534 have the same constraint for them, activity preferred starting time.
in the previous file the constraint used is: activity has a set of preferred starting time.
in this last file the constraint used is: acttivity has a preferred starting time.
I think that the two constraints are different.
the first constraint provides several time intervals for 533 and 534, however, the second provides only one interval for each activity. :)
Oh, indeed, sorry! :-[
So, you are saying that even if the file is more constrained, it is solved faster. There are two reasons:
1) It is easier. Think of a solution file (totally locked file). It solves instantly. It might be helpful to FET to only place this activity in a single slot.
2) It might be just luck.
I think he has a third possibility, maybe it's fiction but it exists (I think); to find the right combination of random seeds for each file? an equation of chance ?!
Quote from: Benahmed Abdelkrim on April 16, 2018, 09:14:44 PM
I think he has a third possibility, maybe it's fiction but it exists (I think); to find the right combination of random seeds for each file? an equation of chance ?!
Absolutely not. That is why the random number generator should be good. And it is.
Quote from: Liviu Lalescu on April 16, 2018, 09:18:13 PM
Absolutely not. That is why the random number generator should be good. And it is.
maybe I'm wrong?
can we know how this generator works?
It is from Knuth TAOCP Vol. 2. See timetable_defs.cpp, search randomKnuth for the implementation.
For us, all that matters is that you give it an initial number (X and Y) and it generates a series of numbers in the range 1..2147483647, updating X and Y at each step (the random number at each step is equivalent to |X-Y|).
Edited to add: The numbers should be without connection one with the next one. And we use them in two ways: a random number between 0 and n-1 (making modulo n) or a real number between 0% and 100% to know if to skip a constraint or not.
i fear that is impossible, if you are able to find such an relation then:
a) i think you also proved at the same time that the random number generator is bad.
and also
b) in that case there should be an alorithm oder trick to do that without beeing "random"
Quote from: Benahmed Abdelkrim on April 16, 2018, 07:42:33 PM
surprise or good news, the first file with 100% weight is resolved in record time; 12 min 43s.
same random seeds of the second file cited above :
X=2105598204,
Y=300887750
only one small change: the activity ID = 533 and ID = 534 fixed in time by the constraint: acttivity has a preferred starting time instead of the constraint: activity has a set of preferred starting time.
I attach below the file and a screenshot of FET showing the end of generation
another tests with the last file cited above (no changes in the file);
characteristics:
generation time =
9min 15s;Random seeds:
X = 1830718095;
Y = 870582853OS: windows 8.1 , 64 bits , processor x64 ;
processor: Intel(R) Core(TM) i3-4150 CPU @ 3.50Ghz 3.50Ghz ;
RAM 4.00Go
cache memory:
L1 Data Cache Size 2 x 32 KBytes
L1 Instructions Cache Size 2 x 32 KBytes
L2 Unified Cache Size 2 x 256 KBytes
L3 Unified Cache Size 3072 KBytes
another tests with the last file cited above
generation time: 24min 21s
same last random seeds
X=2105598204,
Y=300887750
OS: windows 7 64bits x64
processor: Pentium Dual-Core CPU T4400 @ 2.20GHz
RAM 4.00Go
memory caches:
L1 Data Cache Size 2 x 32 Ko
L1 Instructions Cache Size 2 x 32 Ko
L2 Unified Cache Size 1024 Ko
yes. that is normal.
you can also check the single core (SC) speed of that CPUs here:
http://cpu.userbenchmark.com/Compare/Intel-Core-i3-4150-vs-Intel-Pentium-T4400/2309vsm1886
So you can expect around 170% speedup. (of course they don't do a "timetabling" test, but the SC speed will be pretty similar to timetabling with FET.)
I did a test and here is the result attached bellow: