Unrelated-machines scheduling: Difference between revisions

Revision as of 06:08, 19 October 2021

Revision as of 06:11, 19 October 2021

Line 19:

* 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.

GlassLenstra, PottsShmoys and ShadeTardos<ref>{{Cite journal|last=Lenstra|first=Jan Karel|last2=Shmoys|first2=David B.|last3=Tardos|first3=Éva|date=19941990-0701-01|title=UnrelatedApproximation parallelalgorithms machinefor scheduling usingunrelated localparallel searchmachines|url=https://wwwdoi.sciencedirect.comorg/science/article/pii10.1007/0895717794902054BF01585745|journal=Mathematical and Computer ModellingProgramming|language=en|volume=2046|issue=21|pages=41–52259–271|doi=10.10161007/0895-7177(94)90205-4BF01585745|issn=08951436-7177|doi-access=free4646}}</ref> comparepresented variousa [[Localpolytime search2-factor (optimization)|localapproximation search]]algorithm, techniquesand forproved minimizingthat theno makespanpolytime onalgorithm unrelatedwith machines.approximation Usingfactor computerizedsmaller simulations,than they3/2 findis thatpossible [[tabuunless search]]P=NP. andClosing [[simulatedthe annealing]]gap performbetween muchthe better2 thanand [[Geneticthe algorithm|genetic3/2 algorithms]]is a long-standing open problem.

Versache and Wiese<ref>{{Cite journal|last=Verschae|first=José|last2=Wiese|first2=Andreas|date=2013-11-10|title=On the configuration-LP for scheduling on unrelated machines|url=https://link-springer-com.mgs.ariel.ac.il/article/10.1007/s10951-013-0359-4|journal=Journal of Scheduling|volume=17|issue=4|pages=371–383|doi=10.1007/s10951-013-0359-4|issn=1094-6136}}</ref> presentpresented a different 2-factor approximation algorithm.

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|doi-access=free}}</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 ===