Unrelated-machines scheduling

Minimizing the maximum completion time is NP-hard even for identical machines, by reduction from the partition problem.

Horowitz and Sahni[1] presented:

• Exact dynamic programming algorithms for minimizing the maximum completion time on both uniform and unrelated machines. These algorithms run in exponential time (recall that these problems are all NP-hard).
• Polynomial-time approximation schemes, which for any ε>0, attain at most (1+ε)OPT. For minimizing the maximum completion time on two uniform machines, their algorithm runs in time ${\displaystyle O(10^{2l}n)}$, where ${\displaystyle l}$ is the smallest integer for which ${\displaystyle \epsilon \geq 2\cdot 10^{-l}}$. Therefore, the run-time is in ${\displaystyle O(n/\epsilon ^{2})}$, so it is an FPTAS. For minimizing the maximum completion time on two unrelated machines, the run-time is ${\displaystyle O(10^{l}n^{2})}$ = ${\displaystyle O(n^{2}/\epsilon )}$. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.

Lenstra, Shmoys and Tardos[2] presented a polytime 2-factor approximation algorithm, and proved that no polytime algorithm with approximation factor smaller than 3/2 is possible unless P=NP. Closing the gap between the 2 and the 3/2 is a long-standing open problem.

Verschae and Wiese[3] presented a different 2-factor approximation algorithm.

Glass, Potts and Shade[4] compare various local search techniques for minimizing the makespan on unrelated machines. Using computerized simulations, they find that tabu search and simulated annealing perform much better than genetic algorithms.

Bruno, Coffman and Sethi[5] present an algorithm, running in time ${\displaystyle O(\max(mn^{2},n^{3}))}$, for minimizing the average job completion time on unrelated machines, R||${\displaystyle \sum C_{j}}$ (the average over all jobs, of the time it takes to complete the jobs).

Minimizing the weighted average completion time, R||${\displaystyle \sum w_{j}C_{j}}$ (where w_j is the weight of job j), is NP-hard even on identical machines, by reduction from the knapsack problem.[1] It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the partition problem.[6]

Schulz and Skutella[7] present a (3/2+ε)-approximation algorithm using randomized rounding. Their algorithm is a (2+ε)-approximation for the problem with job release times, R|${\displaystyle r_{j}}$|${\displaystyle \sum w_{j}C_{j}}$.

Bar-Noy, Bar-Yehuda, Freund, Naor and Schieber[8] consider a setting in which, for each job and machine, there is a profit for running this job on that machine. They present a 1/2 approximation for discrete input and (1-ε)/2 approximation for continuous input.

Suppose that, instead of "jobs" we have valuable items, and instead of "machines" we have people. Person i values item j at p_i,j. We would like to allocate the items to the people, such that the least-happy person is as happy as possible. This problem is equivalent to unrelated-machines scheduling in which the goal is to maximize the minimum completion time. It is better known by the name egalitarian or max-min item allocation.