Assignment Problem With Weighted Bipartite Graph

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?

• Welcome to OR.SE. It might be modelled as a GAP (Generalized assignment problem) and exact/heuristic methods could be applied to solve that. Feb 17, 2021 at 19:48
• Why is this not just a plain assignment problem? Assuming that task preparation requires that the worker be present,the weight of arc (i,j) would be the sum of travel time for worker i to reach task j plus prep time of task j.
– prubin
Feb 17, 2021 at 22:34
• @newhere Is the number of tasks equal to the number of workers? both mentioned in the question using $n$. Feb 18, 2021 at 1:20
• What I understand is that preparation times are fixed, no matter which worker is assigned. So what is the benefit of including the preparation times into the model, if all of them are to be done? Feb 18, 2021 at 2:50
• @Mostafa what I understand is either task is waiting for the worker or the worker waits for the task to be prepared. The summation of all these waiting times needs to be minimized. Feb 18, 2021 at 3:09

1 Answer

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.