Unrelated-machines scheduling is an optimization problem in computer science and operations research.
We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized (usually, the makespan should be minimized).
The time that machine i needs in order to process job j is denoted by pi,j.
The term unrelated emphasizes that there is no relation between values of pi,j for different i and j.
In the standard three-field notation for optimal job scheduling problems, the unrelated-machines variant is denoted by R in the first field.
" is an unrelated-machines scheduling problem with no constraints, where the goal is to minimize the maximum completion time.
In some variants of the problem, instead of minimizing the maximum completion time, it is desired to minimize the average completion time (averaged over all n jobs); it is denoted by R||
This variant corresponds to the problem of Egalitarian item allocation.
Minimizing the maximum completion time is NP-hard even for identical machines, by reduction from the partition problem.
Horowitz and Sahni[1] presented: 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.
Glass, Potts and Shade[4] compare various local search techniques for minimizing the makespan on unrelated machines.
Bruno, Coffman and Sethi[5] present an algorithm, running in time
, for minimizing the average job completion time on unrelated machines, R||
(where wj 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.
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.
However, in some cases it is possible to bound the number of possible configurations, and therefore find an approximate solution in polynomial time.
Vallada and Ruiz[12] present a solution using a genetic algorithm.
Nisan and Ronen in their 1999 paper on algorithmic mechanism design.