1

Consider there is amount of work $W$ to be done and set of $N$ workers who has different performance: $p=\{p_1,p_2,\dots,p_N\}$. Consider that the work is divisable and can be distributed among the workers: $W=w_1+w_2+\dots+w_N$. Let $w=\{w_1,w_2,\dots,w_N\}$ be the distribution of work.

How can one choose the optimal work distribution $w_{opt}$ so that the work is completed in least time: $max_i (\frac{w_{{opt}_i}}{p_i}) \rightarrow min$ ?

mbaitoff
  • 853

1 Answers1

1

This is a minimax optimization problem: $$ \min_{p_i} \max_{i}\frac{w_i}{p_i} $$ subject to $$ \sum_{i=1}^{n}{w_i}=W. $$ First consider the maximum between $\frac{w_i}{p_i}$ and $\frac{w_j}{p_j}$ and suppose that the sum of $w_i$ and $w_j$ is fixed. Minimum of the maximum of $\frac{w_i}{p_i}$ and $\frac{w_j}{p_j}$ is obtained for $ \frac{w_i}{p_i}=\frac{w_j}{p_j}$. To see this, suppose that the minimum of maximum is obtained for $ \frac{w_i}{p_i} > \frac{w_j}{p_j}$. Then you can always decrease $ \frac{w_i}{p_i}$ by $\delta>0$ and yet keeping it as maximum while the minimum of maximum is decreased.

Now suppose that the minimum of maximum is obtained by choosing $(w_1,...,w_n)$. If for $w_i$ and $w_j$, $\frac{w_i}{p_i}$ is not equal to $ \frac{w_j}{p_j}$. Suppose w.l.g. $\frac{w_i}{p_i} > \frac{w_j}{p_j}$. Then using same procedure as before, you can find a new sequence $(w_1,..,w_i-\delta,...,w_j+\delta,w_n)$ such that the minimum of maximum decreases or does not change.

Therefore the minimum of maximum is obtained for $\frac{w_i}{p_i} = \frac{w_j}{p_j}$ for all $i,j$ which gives the following solution: $$ \displaystyle w_i=W\frac{p_i}{\displaystyle\sum_{j=1}^n p_j} $$

Arash
  • 11,131
  • So, the idea is that all the workers must finish at the same time. Otherwise, at any given time work that is performed by busy workers could have been distributed between currenty idle workers, reducing the finish (minimax) time. Sounds legit. – mbaitoff Sep 19 '13 at 03:37
  • That's a nice interpretation indeed. – Arash Sep 19 '13 at 10:42