I'm writing a scheduler of long-lived Processors which execute long-lived Tasks. Processors and Tasks may each come and go over time, at any time (when a Processor departs, its assigned Tasks now become available for other Processors). Additional constraints exist which can be modeled as a flow network (eg, Tasks can desire multiple distinct assigned Processors, which must also be balanced across racks/regions).
At time{0}
and all future time{N}
's a feasible maximal assignment can be induced by solving the max-flow problem. That much seems clear.
However "handing off" a task from one Processor to another incurs (sometimes significant) startup cost. Therefore at time{N}
, the solution would ideally deviate as little as possible from that of time{N-1}
to minimize incurred cost. Intuitively, I seek to minimize something like the "edit distance" of the two solutions (with full knowledge that the structure of the graph itself has likely changed).
One approach would be to model this as a min-cost max-flow problem, where costs between Tasks and Processors at time{N}
encode the assignments of time{N-1}
. This would work, but I do worry about scaling (scheduler iterations should be fast), and about code complexity & correctness (targeting Golang, and no implementation appears readily available).
I'm thinking of another approach which I'd appreciate feedback on, which would be to slightly tweak the push/relabel algorithm for max-flow by using the following selection criteria:
- Where there is an applicable arc "push" operation such that the directed arc also had non-zero flow at
time{N-1}
, that operation is preferred.- Where multiple such arcs exist, further rank them by the degree of flow at
time{N-1}
(the intuition is to saturate arcs having higher flow attime{N-1}
, first).
- Where multiple such arcs exist, further rank them by the degree of flow at
- If no such applicable arc exists, use the common FIFO selection rule with discharge.
My intuition is that:
As the generic form of the push/relabel algorithm doesn't depend on any particular operation order for correctness, this selection criteria cannot break the algorithm; and
Applying this criteria will greedily lead to a pre-flow best matching the
time{N-1}
assignment, from which it will induce a maximum flow using a minimal number of additional push/relabel operations.
Questions:
Is 2) above approximately true, in that it may not be minimal but will be close? Any sense of what bounds, if any, might exist ?
Any other research avenues I should be looking down, or prior work of this kind?
Thanks!