Uniform-machines scheduling: Difference between revisions

Revision as of 15:30, 18 June 2021

Revision as of 15:36, 18 June 2021

Line 18:

The '''LPT algorithm''' (Longest Processing Time First), also called [[greedy number partitioning]], sorts the jobs by their length, longest first, and then assigns them to the processor with the earliest end time so far. While originally developed for ''identical'' machines, it has good asymptotic convergence properties even for ''uniform'' machines.<ref>{{Cite journal|last=Frenk|first=J. B. G.|last2=Rinnooy Kan|first2=A. H. G.|date=1987-05-01|title=The Asymptotic Optimality of the LPT Rule|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.12.2.241|journal=Mathematics of Operations Research|volume=12|issue=2|pages=241–254|doi=10.1287/moor.12.2.241|issn=0364-765X}}</ref>

'''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>''' presentpresented:

* 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|lastlast1=Hochbaum|firstfirst1=Dorit S.|last2=Shmoys|first2=David B.|date=19881987-0601-01|title=AUsing Polynomialdual Approximationapproximation Schemealgorithms for Schedulingscheduling onproblems Uniformtheoretical Processors:and Using the Dual Approximationpractical Approachresults|url=https://epubs.siamdoi.org/doi/abs/10.11371145/02170337531.7535|journal=SIAM Journal onof Computingthe ACM|volume=1734|issue=31|pages=539–551144–162|doi=10.11371145/02170337531.7535|issn=00970004-53975411|s2cid=9739129}}</ref> whopresented developedseveral aapproximation PTASalgorithms for any number of ''identical'' processors,machines extended(even theirwhen PTASthe tonumber handleof processorsmachines withis differenta speeds.part of the input):

* For any ''r'' >0, an algorithm with approximation ratio at most (6/5+2^−''r'' ) in time <math>O(n(r+\log{n}))</math>.

* For any ''r'' >0, an algorithm with approximation ratio at most (7/6+2^−''r'' ) in time <math>O(n(r m^4+\log{n}))</math>.

* For any ''ε''>0, an algorithm with approximation ratio at most (1+ε) in time <math>O((n/\varepsilon)^{(1/\varepsilon^2)})</math> . This is a [[Polynomial-time approximation scheme|PTAS]]. Note that, when the number of machines is a part of the input, the problem is [[Strong NP-completeness|strongly NP-hard]], so no FPTAS is possible.

Later,<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> they developed a PTAS for ''uniform'' machines.

'''Epstein and Sgall'''<ref>{{Cite journal|last=Epstein|first=Leah|last2=Sgall|first2=Jiri|date=2004-05-01|title=Approximation Schemes for Schedulingon Uniformly Related and Identical Parallel Machines|url=https://doi.org/10.1007/s00453-003-1077-7|journal=Algorithmica|language=en|volume=39|issue=1|pages=43–57|doi=10.1007/s00453-003-1077-7|issn=1432-0541}}</ref> generalized this PTAS to handle more general objective functions. Let ''s_i'' (for ''i'' between 1 and ''k'') be the makespan of processor ''i'' in a given schedule. Instead of minimizing the objective function max(''s_i''), one can minimize the objective function max(''f''(''s_i'')), where ''f'' is any fixed function. Similarly, one can minimize the objective function sum(''f''(''s_i'')).