0
$\begingroup$

I have $n$ tasks that I wish to delegate to $m$ independent individuals, where $m$ is a factor or divisor of $n$. Each of the tasks $T_{1} ... T_{n}$ is independent. From the following two extremes, which or what in between, is the optimal solution?

1) Highest quality, least efficient: assign $T_{1}$ to all $I_{j}$ (where $j = 1, 2, 3,..., m$) and choose the best result; move onto $T_{2}$ and do similarly; repeat for all $T_{i}$ (where $i = 1, 2, 3,..., n$).

2) Most efficient, lowest quality: assign $T_{1}$ to $I_{1}$, $T_{2}$ to $I_{2}$, and so on for $T_{m}$ to $I_{m}$. Decide which results are of sufficient quality, then assign $T_{m+1}$ to $I_{1}$, $T_{m+2}$ to $I_{2}$ and so on until $T_{n}$ is assigned to $I_{n}$

The primary objective is to get as many $T$ finished and of satisfactory quality in a given time $t$.

  • 0
    It looks to me like this may be rather different from an assignment problem: in version 1 you end up assigning every task to every worker. Apparently there is some element of chance involved, in that you only find out the quality of the work after the task is completed.2012-06-11

1 Answers 1

0

I hope this reformulation of your problem is close to what you meant. You have $n$ tasks $T_1,\ldots,T_n$ and $m$ workers $I_1,\ldots,I_m$. Worker $I_i$ will perform task $T_j$ in time $t_{ij}$ (which is known in advance), but the result may or may not be of sufficient quality: the probability that it is of sufficient quality is $p_{ij}$, independent of the results of other workers on this task and this worker on other tasks (and of the assignments that are made). Let $X_{ij}$ be the decision variable, $1$ if worker $I_i$ is assigned task $T_j$, $0$ otherwise. Then the probability that at least one worker completes task $T_j$ with sufficient quality is $1 - \prod_{i}(1 - p_{ij} X_{ij})$. The objective is to maximize the expected number of tasks completed with sufficient quality, which is $ \sum_{j} \left(1 - \prod_{i} (1 - p_{ij} X_{ij})\right)$ In order for everything to be completed by time $t$, you have the constraints $\sum_j t_{ij} X_{ij} \le t$ for every $i$.

This problem is a nonlinear integer programming problem. It may be quite difficult to find an optimal solution, but methods to get nearly-optimal solutions (e.g. simulated annealing or tabu search) may be useful.

  • 0
    As I said: "It may be quite difficult to find an optimal solution, but methods to get nearly-optimal solutions (e.g. simulated annealing or tabu search) may be useful."2012-06-24