Assignment Problem With Weighted Bipartite Graph

Question

I have the following problem:

Given $n$ workers and $n$ tasks I have to assign a worker to each task where each worker has a time to get to the task, and each task has a preparation time. for example, task 1 preparation time is 10 minutes, it will take worker A 2 minutes to get there, 5 minutes for worker B, and 7 minutes for worker C.

My objective is to assign workers such that the waiting time is minimised.

I modelled it to a Weighted Bipartite Graph

Where each edge has a weight and each blue node (task) has a negative weight and we need to assign a worker such that the total cost will be as close to zero

Which algorithms should I look into to solve this?

Answer 1

From the comments I found that your problem can be described by

• a setup time $s_j$ for process $j$
• a travel time $c_{ij}$ for worker $i$ to process $j$

Then the waiting time that we get when assigning worker $i$ to process $j$ is given by $w_{ij}:=|s_j-c_{ij}|$.

Using $w_{ij}$ as your new weights of the assignments you can use any classic assignement algorithm you want to solve this. For example you could use the following LP, which happens to always have an integral optimal solution.

\begin{align} \min \sum_{i,j} w_{ij}x_{ij}\\ \sum_i x_{ij} &= 1 &\forall j\\ \sum_j x_{ij} &=1 &\forall i \\ 0\leq x_{ij} &\leq 1 \end{align}

If this turns out to be too slow you could look into min cost flows on bipartite graphs.