Issues with single resource flowtime optimizer

[dreinon]

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.

[dreinon]

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

[tpaviot]

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

[tpaviot]

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

[dreinon]

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 :)

[dreinon]

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?

[dreinon]

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!

[tpaviot]

The flowtime for one interval is defined as the difference between max_end and min_start, so 5, 7 and 6 are ok

[dreinon]

I understand.

The flowtime for one interval is defined as the difference between max_end and min_start, so 5, 7 and 6 are ok — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub , or unsubscribe .

[dreinon]

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.

[tpaviot]

Which kind of solver did you use? The usual one? The new multi to single objective?

[dreinon]

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.

[tpaviot]

@dreinon I added your 2 tests to the test_indicator.py suite, see commit 07cb1af93a4def3aea5cf8b6cfe3a179e84308c1

[dreinon]

Awesome! Thanks :)

[dreinon]

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.

[tpaviot]

"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

[dreinon]

Awesome! Congrats for its performance!! Great job!

[dreinon]

What does weight parameter do in add_objective_flowtime_single_resource?

[tpaviot]

Commit a0c2053a8e2b87f1ba5a433794dc58df2b090080 should improve solver report accuracy

[tpaviot]

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

[dreinon]

Nice

[dreinon]

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?

[tpaviot]

I run your test with up to 40 intervals, it gives a solution in a reasonable time

[dreinon]

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

[dreinon]

I understand print(weighted_objectives) in method create_objective from SchedulingSolver class in solver.py might be a mistake (?)

[tpaviot]

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

[dreinon]

Getting 0 utilization using 2000 weight in the objective

[tpaviot]

I dont understand

[tpaviot]

ah ok the result of the optimization is 0% for the resource utilization, right ?

[dreinon]

Right, sorry, I was editting my comment since it wasn't much clear, sorry. :)

[dreinon]

It's also weird that even though I'm getting no tasks scheduled, some flowtime indicators are 1.

[tpaviot]

a short example that reproduces the issue?

[dreinon]

Let me work on it. I'll be back when I have something.

[tpaviot]

perfect

[tpaviot]

If the weight for flowtime is 0, is the utilization maximized ?

[dreinon]

No, it isn't

[tpaviot]

ok I understand where the issue comes from, some code has disappeared, certainly an aggressive git rebase

[dreinon]

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

[tpaviot]

can you try with commit 08201de88b97beb5c8e0798a7da803fc579a18d4

[tpaviot]

All maximization objectives are multplied by -1 and turned into a minimization objective

[dreinon]

Perfect!

All maximization objectives are multplied by -1 and turned into a minimization objective

[dreinon]

Mistake in line 180 of solver.py

[dreinon]

Nice commit name haha

[tpaviot]

Fixed. I'm currently doing several things at the same time, hard to get fully focused!

[dreinon]

Totally understandable! Thanks always Thomas!

[dreinon]

Results from having tried it deeply in my problem:

1. 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)
2. 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?

[tpaviot]

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

[dreinon]

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.

[tpaviot]

It should be reported "Found optimum" or something like that

[dreinon]

Even though max_time is big, when it finds optimum it stops?

[tpaviot]

It should. You can also try to add a constraint such that utilization is 100 and use the optimization for flowtime only.