0
$\begingroup$

Can anyone suggest an approach, literature like a paper or book that I can use in order to model the problem herein and solve it?

Assume that there are 4 workers $\left\{W_1, W_2, W_3, W_4\right\}$ and 20 tasks $\left\{T_1, T_2, ..., T_{20}\right\}$. These 20 tasks are divided into 4 groups $\left\{S_1, S_2, S_3, S_4\right\}$ such that

$S_1 = \left\{T_1, T_2, T_3, T_4, T_5\right\}$,

$S_2 = \left\{T_6, T_7, T_8, T_9, T_{10}\right\}$,

$S_3 = \left\{T_{11}, T_{12}, T_{13}, T_{14}, T_{15}\right\}$,

$S_4 = \left\{T_{16}, T_{17}, T_{18}, T_{19}, T_{20}\right\}$,

Then, any worker is able to do any of the 20 tasks. Each, task has a difficulty for each worker. The assignment should be done such that no two workers are assigned tasks in the same group. For example, $W_1 \rightarrow T_3$, $W_2 \rightarrow T_{11}$, $W_3 \rightarrow T_5$, $W_4 \rightarrow T_{19}$ is not acceptable because $W_1$ and $W_3$ have been assigned tasks in the same group.

  • The objective is to assign each worker a different task such that the total difficulty (or effort) to accomplish them is minimized. As mentioned before, the only restriction is that no two workers can be assigned tasks in the same group.

I have tried with a greedy approach but I would like to find the optimal solution without doing exhaustive search. I know that the Hungarian method or its equivalent using bipartite graphs will not do the job here. So, are you aware of any similar problems that have been solved in the past? I will much appreciate any support.

$\endgroup$
2
  • $\begingroup$ What's your objection to the Hungarian method? Also, what is the goal: to pick a task for each worker (and each worker can do one task), or to pick a worker for each task (and each worker can do multiple tasks)? $\endgroup$ Commented Apr 12, 2017 at 20:06
  • $\begingroup$ Thank you for your reply. (1) The 4 workers must be assigned any 4 tasks such that no two workers will do tasks in the same group. The objective is to minimize the total effort involved in accomplishing the assigned tasks. (2) As far as I know, the Hungarian method cannot be used here because the assignment has a restriction not so easy to overcome. For example, once a worker is assigned a task from a group, this group is banned for other workers. $\endgroup$ Commented Apr 13, 2017 at 4:39

1 Answer 1

Reset to default
1
$\begingroup$

If you're assigning each worker a single task, and two workers cannot be assigned tasks from the same group, that's the same as assigning a group of tasks to each worker (and then letting the worker pick the least-effort task from that group).

Formally, if $c(W_i, T_j)$ is the cost of assigning task $T_j$ to worker $W_i$, then let $$c(W_i, S_k) = \min \{ c(W_i, T_j) \mid T_j \in S_k\}.$$ We can solve the assignment problem of $\{W_1, W_2, W_3, W_4\}$ to $\{S_1, S_2, S_3, S_4\}$ using standard methods, using this $c$ as the cost function. Given such an assignment, if $W_i$ is assigned to $S_k$, we can get a solution to the original problem with the same cost by assigning $W_i$ the task $T_j \in S_k$ that achieves the minimum defining $c(W_i, S_k)$.

(Conversely, given any feasible solution to the original problem, we can get a solution of equal or smaller cost to the group-assignment problem by changing the assignment $W_i \mapsto T_j$ to $W_i \mapsto S_k$ where $S_k$ contains $T_j$.)

$\endgroup$
2
  • $\begingroup$ Your reasoning seems to be correct Misha. Thank you very much for your answer. $\endgroup$ Commented Apr 13, 2017 at 4:46
  • $\begingroup$ In this case, clustering tantamounts to dealing with restrictions. Misha, would you please recommend any references where similar problems with constraints can be approached via graphs? $\endgroup$ Commented Apr 28, 2017 at 20:25

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.