Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
This is called a "assignment problem". It's a standard problem in Operations Research. You need to explain what the weight W, the efficiency E, and the effectiveness Q are. If $T_i$ is performed by $I_k$, how do these quantities come into play? – Hans Engler Jun 11 '12 at 2:14
@HansEngler perhaps W, E and Q can be ignored for the moment. – Kaleb Jun 11 '12 at 21:43
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. – Robert Israel Jun 11 '12 at 21:58
up vote 0 down vote accepted

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.

share|cite|improve this answer
Thanks. This formulation is what I wanted. I'm not too familiar with optimisation as a subject, so would it be possible to solve numerically (obtaining values for the probabilities, etc.) rather than generally? – Kaleb Jun 23 '12 at 10:29
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." – Robert Israel Jun 24 '12 at 6:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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