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?