Optimize flowtime of specific resource in certain period

[dreinon]

I'm willing to optimize flowtime of a specific resource in a certain period. That means that if a resource is going to be assigned 3 tasks between 4 and 10, then try these tasks to be followed one by another.

Any ideas? Thank you!

[tpaviot]

ok I understand your need. I don't see how to do it using the current implementation, I think it will require another constraint (is it a constraint over a resource or a task?)

[dreinon]

I think a resource one, since we are trying all tasks of that resource that are scheduled in a certain period of time to be followed one by another. The idea is that, since students are resources, try students to do as many continued tasks as possible in a day (period).

Note that in my problem, only a max of 3 tasks can be scheduled for a student in a day, so the objective would be that in a certain resource, if more than one task is scheduled in a certain period of time, try to make them one followed by another, but since we are optimizing utilization, the scheduler shouldn't be stopped to schedule the tasks if they cannot be followed. It's something that ideally has to happen as much as possible, but it doesn't have to happen always.

[tpaviot]

Got it, a resource constraint. I'm trying to figure out what has to be minimized or maximized in terms of an optimization problem. I could surely do it easily for the whole schedule. For instance, by minimizing the difference between the greatest end time and the smallest start time. It would reduce the "non-productive time" between two tasks, then lead to "contiguous tasks". But there also could be another constraint that forces two or more tasks to be contiguous as possible.

I have the feeling it is independent of the WorkLoad constraint though.

[dreinon]

I also think it's independent.

[dreinon]

I impelemented a new objective that minimizes flowtime from a list of tasks, but I'm not achieving any results since, as you said, what we want is to reduce the difference between start time and end time, but not reduce all end times.

[dreinon]

I was also thinking if it makes sense to call it constraint since it's more like an objective to optimize as much as possible. However, the use of a constraint would be handier, since if it's another objective, the solver would use regular (multiobjective) optimization instead of incremental. I guess it also depends on how it could be modelled in the Z3 solver.

[tpaviot]

Yes, right, an optimized objective is more suitable. In the first step, the flow time of a single resource could be optimized during the whole schedule (from 0 to horizon). I think it can be achieved in a short time. Then, we'll see how to do it for a restricted period. I will create a dedicated branch and push code, I have an idea about how to do that.

[dreinon]

Perfect!

[tpaviot]

Commit 07b9e70 introduces a new optimization objective for single resource flowtime. You can pass an interval range to the method but it won't work. So far, it is only tested for the whole schedule, from 0 to the horizon.

[tpaviot]

Not sure that this first commit does the job actually. I ran a few tests, the output schedules not always minimize the number of discontinuities between tasks. Indeed, I think that is what you want: whatever the number of scheduled tasks, you want those tasks to be as "contiguous" as possible, am I right? I try to express this constraint using different words, to be sure I understand your need. This can lead to different constraints and optimization rules.

[dreinon]

Yes, exactly. Imagine a utilization maximization problem with an horizon of 4 and 3 workers. Then 4 optional tasks, 2 of them assigned to worker1, 1 to worker 2 and 1 to worker 3. Worker1 is always available, worker 2 is not available in (3-4) and worker3 is not available in (2-3). Let's imagine there's another worker who is assigned all tasks just so we can target it to maximize its utilization. Let TiWj be task i of worker j. Then, a solution like this sol1 = (T1W1,T1W2,T2W1,T1W3) would be possible, although the perfect solution would be sol2 = (T1W1,T2W1,T1W2,T1W3).

Now imagine worker 2 is ONLY available in (1-2). Then, our perfect solution would be sol1, since we are priorizing utilization, and if we force TiW1 tasks together, utilization wouldn't be maximum.

I hope this could explain the problem well :smile:

[tpaviot]

With commit c9b3dddb this should work

[dreinon]

Awesome!