Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 20:
* [[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]].
=== Maximizing the profit ===
'''Bar-Noy, Bar-Yehuda, Freund, Naor and Schieber'''<ref>{{Cite journal|last=Bar-Noy|first=Amotz|last2=Bar-Yehuda|first2=Reuven|last3=Freund|first3=Ari|last4=(Seffi) Naor|first4=Joseph|last5=Schieber|first5=Baruch|date=2001-09-01|title=A unified approach to approximating resource allocation and scheduling|url=https://doi.org/10.1145/502102.502107|journal=Journal of the ACM|volume=48|issue=5|pages=1069–1090|doi=10.1145/502102.502107|issn=0004-5411}}</ref> consider a setting in which, for each job and machine, there is a ''profit'' for running this job on that machine. They present a 1/2 approximation for discrete input and (1-''ε'')/2 approximation for continuous input.
== Extensions ==
| |||