Issues with single resource flowtime optimizer
dreinon opened this issue · 59 comments
The first issue I have ran into by trying out multiple single resource flowtime objectives is that the value of all of them is the same. For instance, I get the following values:
->Objective values:
->FlowtimeSingleResource(min objective): 9
->FlowtimeSingleResource(min objective): 9
for this result:
where I'm optimizing flowtime between time intervals (11, 20) and (21, 34), so total in-interval flowtime is 0. I implemented a way to calculate this total value that doesn't rely on indicator values though.
I have made a test where I have found multiple single resource flowtime objectives don't work as expected. Check test_indicator_flowtime_single_resource_6 in file test_indicator @ master of my fork
Can you please test the latest master branch, especially commit a136fe8
I planned to push this commit, this might solve this issue, not sure about that not tested
Your issue comes from the fact that many variables have the same name, the solver does not make the difference between all those variables. Adding a unique id to the variable names should fix it
Can you please test the latest master branch, especially commit a136fe8
I planned to push this commit, this might solve this issue, not sure about that not tested
I'll do that and come back :)
Working fine for 3 time intervals [(0, 10), (10, 20), (20, 30)], although flowtimes are the following:
->FlowtimeSingleResourceWorker1_4496c5ac0df5459bbeb9e39fa9f9b286(min objective): 5
->FlowtimeSingleResourceWorker1_a81b0b79d89f4bd5b68f4007eef6d698(min objective): 7
->FlowtimeSingleResourceWorker1_5c30474727ca47379e237f82aa96b51e(min objective): 6
for this solution:
Shouldn't it be 0 for each, since all tasks are followed one by another in all intervals?
Might there be a bottleneck in single resource flowtime objective creation and solver initialization?
For a problem with
time_intervals = [(0, 7), (7, 14), (14, 21), (21, 28), (28, 35), (35, 42), (42, 49), (49, 56), (56, 63), (63, 70), (70, 77), (77, 84), (84, 91), (91, 98), (98, 105), (105, 112), (112, 119), (119, 126), (126, 133), (133, 140)]
I tried creating 20 of these objectives (one for each interval), and got aprox ellapsed time of 1 sec for each. Then, the following line takes 9 seconds:
solver = ps.SchedulingSolver(problem)
These 2 times are independent of the number of tasks I create in the problem.
Then, the solver correctly solver this problem in 15.7751 sec, very good mark!
The flowtime for one interval is defined as the difference between max_end and min_start, so 5, 7 and 6 are ok
Last commit changes my tests implementation for one using sum_durations as you did in your tests (I first didn't understand what flowtime really meant). I also added timing to measure performance.
Which kind of solver did you use? The usual one? The new multi to single objective?
I think it was the usual one, since I just followed the regular steps (added objectives and solve). Although I'm not so worried about performance of optimizer for now, because you have implemented the new incremental one. The main reason I reported the issue was SchedulingSolver instance performance and adding single resource flowtime objective performance.
Awesome! Thanks :)
No solution can be found for problem IndicatorFlowtimeSingleResource4.
Reason: Unsatisfiable problem: no solution exists
I get this for all tests with the most recent changes, but tests pass, so solution is truthy and flowtime is sum_durations.
"No solution can be found" means that the optimum has been found: looking for a better value does not return any answer. The output of the IncrementalSolver is not clear about that
Awesome! Congrats for its performance!! Great job!
What does weight parameter do in add_objective_flowtime_single_resource?
Each objective comes with its own weight parameter. By default set to 1. If you want an objective to be considered with a higher priority, just increase its weight. For information, the solver searches the optimum O of Sum(Wi*Oi), Wi being the weight of objective Oi
Nice
If I always want resourceUtilization to be the priority, I guess I have to set an upper bound for the number of flowtime objectives and set the weight of the resourceUtilization object to that bound, so the sum of weights of flowtime objectives doesn't overcome resourceUtilization, right?
I run your test with up to 40 intervals, it gives a solution in a reasonable time
Nice! I tested it for a variable number of intervals and interval lengths to see how it scaled wrt these parameters.
Now, I have to test it in a way that approaches my problem more closely, since I'll just need a max of 7 intervals (days of the week) and a max of 15/18 number of slots per interval, which is very easy for the solver to deal with.
Although, the difficulty is not the number of intervals, but I think it is the number of resources (≈ 20), and therefore, the number of objectives, which would grow up to around 20*(7 intervals) ≈ 140 objectives. Also, the mixture of maximizing occupation and then, minimizing all these objectives, might be hard (?) So far, I have tested it in my real problem (both with all 1 weights and setting utilization weigth to 2*(number of flowtime objectives)) and I have got 0 utilization in both scenarios.
Any ideas of how to priorize utilization? Maybe its weight is not big enough, or maybe I will have to test it for simpler scenarios but adding both utilization and flowtime objectives.
What do you think?
I run your test with up to 40 intervals, it gives a solution in a reasonable time
I understand print(weighted_objectives) in method create_objective from SchedulingSolver class in solver.py might be a mistake (?)
You need to increase the weight for resource utilization. Both flowtime and resource utilization objectives should have the same order of magnitude (use 10 or 100 for the resource utilization). print(weighted_objectives) is just a debug line, should be commented out
Getting 0 utilization using 2000 weight in the objective
I dont understand
ah ok the result of the optimization is 0% for the resource utilization, right ?
Right, sorry, I was editting my comment since it wasn't much clear, sorry. :)
It's also weird that even though I'm getting no tasks scheduled, some flowtime indicators are 1.
a short example that reproduces the issue?
Let me work on it. I'll be back when I have something.
perfect
If the weight for flowtime is 0, is the utilization maximized ?
No, it isn't
ok I understand where the issue comes from, some code has disappeared, certainly an aggressive git rebase
Oh, at least it was easy to find! haha.
Another doubt I have is that, if the solver looks for the optimum O of Sum(Wi*Oi), is the solver aknowledged about which O has to be maximized or minimize?
Each objective comes with its own weight parameter. By default set to 1. If you want an objective to be considered with a higher priority, just increase its weight. For information, the solver searches the optimum O of Sum(Wi*Oi), Wi being the weight of objective Oi
All maximization objectives are multplied by -1 and turned into a minimization objective
Perfect!
All maximization objectives are multplied by -1 and turned into a minimization objective
Mistake in line 180 of solver.py
Nice commit name haha
Fixed. I'm currently doing several things at the same time, hard to get fully focused!
Totally understandable! Thanks always Thomas!
Results from having tried it deeply in my problem:
- Without any flowtime optimization, I get 100% utilization in 0.00 secs (Awesome performamce!!!), but not many tasks are followed one by another (as expected)
- With flowtime optimization for all resources (but general one), I get 94% utilization but more flowtime optimized.
Looking into why it didn't achieve 100% utilization in (2), I realized that a side effect of minimizing flowtime might be that the solver is trying to minimize the number of resources that have any task scheduled, because if it scheduled one tasks to them, global flowtime would increase. Expected behaviour is reaching 100% utilization and optimize as much as possible (but no more) flowtime. I though it could be the weight, but I tried with 10, 100, 1000, 2000 weights for utilization, but always getting 94% utilization.
Any ideas?
Is the value 94 identified as the optimum by the solver? If not, increasing the max_time could let the solver a bit more time to find a better solution
How do I know if it's identified as optimum?
I don't think increasing max_time would do any better, since I set max_time to 1200, and I waited until the value didn't change for 5 minutes, and then stopped it myself.
It should be reported "Found optimum" or something like that
Even though max_time is big, when it finds optimum it stops?
It should. You can also try to add a constraint such that utilization is 100 and use the optimization for flowtime only.
I don't get any found optimum, I just get
Found better value: -8552 elapsed time:179.280s
Checking better value <-8552
I'll leave it for 1200 sec (20 min) and see if it gets any better.
I could also add the constraint for debugging but in real life I would need it to be automatic.
Output is:
/xxxx/ProcessScheduler/processscheduler/solver.py:434: UserWarning: time may exceed max time. Stopping iteration.
warnings.warn('time may exceed max time. Stopping iteration.')
total number of iterations: 139
value: -8830
XXXXXXXXXXXXX satisfiability checked in 953.49s
with occupation of 97
Maybe the solver is lost into some kind of local optimum. You can try other logics to see if it is better ("QF_IDL", "QF_UFIDL" or others)
Okay, thanks!
I have tried solving first for utilization objective only and then, solving again, but with a constraint that utilization indicator has to be equal to the previously found value, and with single resource flowtime objectives, and I get a solution with 100% occupation and pretty flowtime optimized :)
Maybe an option for multiobjective incremental optimizer would be to solve for objectives in creation order (equivalent to 'lexicon' option).
I agree, that's something I think about.