Content deleted Content added
Lazy Maniik (talk | contribs) m Added {{Orphan}} tag |
Erel Segal (talk | contribs) No edit summary |
||
Line 20:
* 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 scheme|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 <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>. 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.
'''Glass, Potts and Shade'''<ref>{{Cite journal|date=1994-07-01|title=Unrelated parallel machine scheduling using local search|url=https://www.sciencedirect.com/science/article/pii/0895717794902054|journal=Mathematical and Computer Modelling|language=en|volume=20|issue=2|pages=41–52|doi=10.1016/0895-7177(94)90205-4|issn=0895-7177}}</ref> compare various [[Local search (optimization)|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 algorithm|genetic algorithms]].
== External links ==
| |||