# Minimize worker variance assignment problem

I have a problem, which is similar to Assignment Problem, described as follows:

The problem instance has a number of workers and a number of tasks. Any task can only be assigned to a subset of the workers. A task should be assigned to exactly one worker. Each task has a different difficulty, therefore, workers will spend different time to finish each task. It is required to assign tasks as uniformly as possible: all of the workers spent almost the same time to finish assigned tasks.

Translating this problem to an Integer Linear Programming problem and solving it by CoinCbc solver is all I learned from Assignment Problem: the cost function is to minimize the variance of each worker. I searched a lot, assignment problem, balanced assignment problem, constrained assignment problem, quadratic assignment problem, etc. All I found are different from this problem. Although, I can solve the problem now. I want to solve it more efficiently.

Is the problem well studied? Are there any algorithms to solve it more efficiently? (Approximation is acceptable)

• This seems like a variant of the knapsack problem, but we have multiple knapsacks that must all be filled as evenly as possible. Feb 8 at 22:26

It depends what you mean by variance. Assuming it's how uniformly tasks are assigned and objective to have almost uniform total time per worker you either do what the above answer suggests or define two variables, say $$z_1$$ & $$z_2$$ that takes in the min and max values of total time taken per worker. Like $$z_1 \le \sum_{jobs}$$TotalTime$$\ \forall$$ workers.
Same for $$z_2$$ with relation as $$\ge$$.
Then minimize $$z_2-z_1$$. Most solvers will assign tasks as uniformly as possible.