Assume that you have a pool of $N$ workers and $M$ tasks. The tasks are initially distributed among workers, the $i$-th worker has $x_i \geq 0$ tasks. All tasks are distributed, so $M = \sum_{i=1}^N x_i$. The initial distribution is unfair and I would like to make it as fair as possible, by limiting the number of reassignings.
The reassigning procedure is very simple: the task is removed from a worker and assigned in a round-robin fashion to one of the $N$ workers (maybe even back to him). Let $y_i$ be the number of tasks that are unassigned from $i$-th worker. Then after the reassigning procedure each worker has $$ x_i' = x_i - y_i + \frac{1}{N} \sum_{k=1}^N y_k $$ tasks. The $M$ is very big, so discrete nature of the problem is unimportant, so $x_i$ and $y_i$ can be treated as real numbers and the redistribution can be considered as equal.
The objective function is the deviation of $x'$ which is $$ \operatorname{dev} x' = \max_i x_i' - \min_i x_i'. $$ If it makes the problem simplier, different similar objective functions are acceptable, for example the standard deviation is ok too.
The $y_i$ are subjected to natural limitations $0 \leq y_i \leq x_i$. Also I would like to bound the number of reassignments: $\sum_{i=1}^N y_i \leq R$. Otherwise the solution would be as simple as reassign all the tasks.
Summarizing the above we have the following problem $$ \max_i (x_i - y_i) - \min_i (x_i - y_i) \to \min_{y_i}\\ \operatorname{subject to} \quad 0 \leq y_i \leq x_i, \quad \sum_{i=1}^N y_i \leq R\\ $$
Here a simplification $\operatorname{dev}_i x_i = \operatorname{dev}_i (x_i + c)$ was used to eliminate the $\frac{1}{N} \sum_{i=1}^N y_i$ term. If there are many solutions of the problem, I'm interested in one with the minimal $\sum_{i=1}^N y_i$ value, so probably that might be added as a penalty term to the objective function.
My questions are:
- Which class does this problem belong to? Can it be reduced to a linear programming one?
- What numerical methods are suitable for the problem? Probably this question can be answered after the previous one.
Any suggestions are welcome.
Yes, it can be formulated as linear programming problem, but it's not the simplest way.
Sort $x_i$ s.t. $x_1 \geq x_2 \geq x_n$.
Claim: there is an optimal solution in which 1) $x_1 - y_1 \geq x_i - y_i$ for any $i$, and 2) $x_n - y_n \leq x_i - y_i$ for any $i$.
If $x_1 - y_1 < x_i - y_i$ for some $i$, replace $y_1$ with $x_1 - \max_i (x_i - y_i)$ - i.e. reduce amount taken from $x_1$ s.t. the first worker stays (one of) the richest. It will neither violate restriction nor increase objective.
Replace each $y_i$ for which $x_i - y_i < x_n - y_n$ with $x_i - (x_n - y_n)$ - i.e. reduce amount taken from workers who become poorer than initially poorest one.
So, there is an optimal solution in which the initially richest stays richest, and initially poorest stays poorest. We need to add such restrictions to the problem: $x_1 - y_1 \geq x_i - y_i \geq x_n - y_n$, and out objective becomes $x_1 - y_1 - x_n + y_n \to \min$.
However, from such formulation it becomes obvious that there is an optimal solution in which $y_n = 0$ (just reduce amount taken from everyone who became poorer than $n$-th worker initially was). So, our new minimum will be $x_n$, and we want to make our new maximum as low as possible.
If our new maximum is $t$, we need to take $\max(0, x_i - t)$ work from $i$-th worker. We can do binary search on $t$, but it's easy to find it exactly: first, take work from the first worker until we either got to restriction or the first worker has the same amount of work as the second one. Then, take work from the first two workers in equal amount until we either got to restriction or to the amount of work the third has. Repeat for every worker. If we got to the last without getting to restriction - we can make everyone equal.