4
$\begingroup$

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

enter image description here

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?

$\endgroup$
7
  • $\begingroup$ Welcome to OR.SE. It might be modelled as a GAP (Generalized assignment problem) and exact/heuristic methods could be applied to solve that. $\endgroup$ – A.Omidi Feb 17 at 19:48
  • $\begingroup$ 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. $\endgroup$ – prubin Feb 17 at 22:34
  • $\begingroup$ @newhere Is the number of tasks equal to the number of workers? both mentioned in the question using $n$. $\endgroup$ – Oguz Toragay Feb 18 at 1:20
  • $\begingroup$ 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? $\endgroup$ – Mostafa Feb 18 at 2:50
  • $\begingroup$ @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. $\endgroup$ – Oguz Toragay Feb 18 at 3:09
4
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.