affinity based static load balancing

Question

I am trying to find a good model the following problem:

Given a collection of work packets x, y, z, ..., and a collection of worker nodes A, B, C, ..., assign packets to nodes.

Each work packet has an affinity per worker-node, shown as a cost-value for how long a packet takes to process on a specific node. For example, packet x runs twice as fast on node B, and packet z cannot run on node C at all. We get an affinity table like this:

\begin{array}{c|c|c|c|} & A & B & C \\ \hline x& 1& 0.5& 1\\ \hline y& 1& 1& 1\\ \hline z& 1& 1& \infty\\ \hline \end{array}

Now I want to distribute all packets across all available nodes with the best total affinity possible. If each node would take any number of work packets, this is trivial, as each packet would just get assigned to the node it has the best affinity on. However, nodes process their work in parallel, and therefore I primarily want to minimize the maximum cost across all nodes.

For the example above, the solution looks like this:

A: z  cost: 1
B: x  cost: 0.5
C: y  cost: 1
      ----------
      max:  1    <-- needs to be minimized, primarily
      sum:  2.5  <-- should also be minimized

I could just brute-force a solution by permutating all possible combinations, but that isn't feasible for a larger number of nodes and/or packets.

Is there a model for this, which I can research into to find a good algorithm to solve this problem?

Answer 1

Yes, this can be solved efficiently using standard methods for bipartite matching and the assignment problem. Let me build up to a solution, so you can see the ideas underpinning it.

If you want to minimize the maximum affinity, you can do that with binary search. Pick a threshold $t$, and check whether there is a valid solution using only assignments that have an affinity $\le t$. That check can be done by looking for a perfect matching in a bipartite graph, which can be done in polynomial time for a single value of $t$. (The graph has an edge from a packet to a node if their affinity is $\le t$, otherwise the edge is absent.) Now do binary search over $t$ to find the smallest $t$ for which such an assignment exists.

If you want to minimize the sum of the affinities, this is an instance of the assignment problem. There are polynomial-time algorithms for the assignment problem, which you can use directly.

If you want to minimize the max of the affinities, but break ties by choosing the one with the lowest sum, then you can combine above two methods. First, find the smallest $t$ such that there exists an assignment using only affinities $\le t$. Then, create an instance of the assignment problem, using only affinities that are $\le t$, and solve the corresponding assignment problem. This gives an efficient algorithm to solve your problem.