'''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>''' present:
* 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).
* An[[Polynomial-time approximateapproximation algorithmscheme]]<nowiki/>s, which for any ''ε''>0, attain at most (1+ε)OPT. For minimizing the ''maximum'' completion time on ''two ''uniform'' machines. For any ''ε''>0, their algorithm attains a maximum completion time at most (1+ε)OPTruns 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 algorithmalgorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.
*An similar algorithm for minimizing the ''maximum'' completion time on ''two unrelated'' machines. For any ''ε''>0, their algorithm attains a maximum completion time at most (1+ε)OPT in time <math>O(10^{l} n^2)</math>, where <math>l</math> is the smallest integer for which <math>\epsilon \geq 2\cdot 10^{-l}</math>, so the run-time is in <math>O( n^2 / \epsilon)</math>. Again, they claim that their algorithm can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.
'''Hochbaum and Shmoys''',<ref>{{Cite journal|last=Hochbaum|first=Dorit S.|last2=Shmoys|first2=David B.|date=1988-06-01|title=A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach|url=https://epubs.siam.org/doi/abs/10.1137/0217033|journal=SIAM Journal on Computing|volume=17|issue=3|pages=539–551|doi=10.1137/0217033|issn=0097-5397}}</ref> who developed a PTAS for identical processors, extended their PTAS to handle processors with different speeds.
