Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. 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. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj (where sj is the speed of machine j), and identical-machines scheduling - in which pi,j = pi (the same run-time on all machines). In the standard three-field notation for optimal job scheduling problems, the unrelated-machines variant is denoted by R in the first field. For example, the problem denoted by " R|| C max {\displaystyle C_{\max }} " 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|| ∑ C i {\displaystyle \sum C_{i}} . More generally, when some jobs are more important than others, it may be desired to minimize a weighted average of the completion time, where each job has a different weight. This is denoted by R|| ∑ w i C i {\displaystyle \sum w_{i}C_{i}} . In a third variant, the goal is to maximize the minimum completion time, " R|| C min {\displaystyle C_{\min }} " . This variant corresponds to the problem of Egalitarian item allocation.
Algorithms
Minimizing the maximum completion time (makespan) Minimizing the maximum completion time is NP-hard even for identical machines, by reduction from the partition problem. Horowitz and Sahni 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 O ( 10 2 l n ) {\displaystyle O(10^{2l}n)} , where l {\displaystyle l} is the smallest integer for which ϵ ≥ 2 ⋅ 10 − l {\displaystyle \epsilon \geq 2\cdot 10^{-l}} . Therefore, the run-time is in O ( n / ϵ 2 ) {\displaystyle O(n/\epsilon ^{2})} , so it is an FPTAS. For minimizing the maximum completion time on two unrelated machines, the run-time is O ( 10 l n 2 ) {\displaystyle O(10^{l}n^{2})} = O ( 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 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 presented a different 2-factor approximation algorithm. Glass, Potts and Shade 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.
Minimizing the average completion time Bruno, Coffman and Sethi present an algorithm, running in time O ( max ( m n 2 , n 3 ) ) {\displaystyle O(\max(mn^{2},n^{3}))} , for minimizing the average job completion time on unrelated machines, R|| ∑ C j {\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|| ∑ w j C j {\displaystyle \sum w_{j}C_{j}} (where wj is the weight of job j), is NP-hard even on identical machines, by reduction from the knapsack problem. It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the partition problem. Schulz and Skutella present a (3/2+ε)-approximation algorithm using randomized rounding. Their algorithm is a (2+ε)-approximation for the problem with job release times, R| r j {\displaystyle r_{j}} | ∑ w j C j {\displaystyle \sum w_{j}C_{j}} .
… excerpt ends here. Continue reading the full article.
