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 at time{N-1}, first).
  • If no such applicable arc exists, use the common FIFO selection rule with discharge.

My intuition is that:

  1. 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

  2. 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.


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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.