Uniform-machines scheduling: Difference between revisions

Revision as of 20:05, 19 June 2021

Revision as of 20:06, 19 June 2021

Line 34:

'''Horowitz and Sahni<ref name=":0">{{Cite journal|last=Horowitz|first=Ellis|last2=Sahni|first2=Sartaj|date=1976-04-01|title=Exact and Approximate Algorithms for Scheduling Nonidentical Processors|url=https://doi.org/10.1145/321941.321951|journal=Journal of the ACM|volume=23|issue=2|pages=317–327|doi=10.1145/321941.321951|issn=0004-5411}}</ref>''' presented:

* Exact [[dynamic programming]] algorithms for minimizing the ''maximum'' completion time on both uniform and unrelated machines, and for minimizing the ''weighted-average completion time'' on ''uniform'' machines. These algorithms run in exponential time (recall that these problems are all NP-hard).

* [[Polynomial-time approximation scheme]]<nowiki/>s, which for any ''ε''>0, attain at most (1+ε)OPT. For minimizing the ''maximum'' completion time on two ''uniform'' machines, their algorithm runs in time <math>O(10^{2l} n)</math>, where <math>l</math> is the smallest integer for which <math>\epsilon \geq 2\cdot 10^{-l}</math>. Therefore, the run-time is in <math>O( n / \epsilon^2)</math>, so it is an [[FPTAS]]. For minimizing the ''maximum'' completion time on two ''unrelated'' machines, the run-time is <math>O(10^{l} n^2)</math> = <math>O( n^2 / \epsilon)</math>. For minimizing the ''weighted average'' completion time on two ''uniform'' machines, the run-time is <math>O(10^{l} n^2)</math> = <math>O( n^2 / \epsilon)</math>. 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. They do not present an algorithm for ''weighted-average'' completion time on ''unrelated'' machines.

'''Hochbaum and Shmoys'''<ref name=":02">{{Cite journal|last1=Hochbaum|first1=Dorit S.|last2=Shmoys|first2=David B.|date=1987-01-01|title=Using dual approximation algorithms for scheduling problems theoretical and practical results|url=https://doi.org/10.1145/7531.7535|journal=Journal of the ACM|volume=34|issue=1|pages=144–162|doi=10.1145/7531.7535|issn=0004-5411|s2cid=9739129}}</ref> presented several approximation algorithms for any number of ''identical'' machines (even when the number of machines is a part of the input):