Minimize worker variance assignment problem

Question

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)

Answer 1

First, you might consider a different objective function. Rather than variance, you might minimize the maximum time spent by any worker, or minimize the range in worker times (the difference between the longest and shortest times that any worker is occupied). That might speed up solution time.

If you want to settle for a good but not provably optimal solution, there are a number of possibilities. First, you can continue with your current model but set a time limit, and accept the incumbent solution when the time limit is reached. With some solvers, you may also find a parameter setting telling the solver to emphasize finding good incumbents (as opposed to improving the best bound), which in conjunction with a time limit might produce a sufficiently good solution.

Beyond that, there are numerous metaheuristics that can be applied to the problem. Some of them use a version of "neighborhood" search, in which you take a proposed set of assignments and see if you can improve it by, for example, swapping a pair jobs between two workers or just moving a job from one worker to another. Metaheuristics typically do not provide proof of optimality and frequently do not attain optimality. Whether they reach a good enough answer faster than your current approach can only be answered by experimentation.

Answer 2

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.