Uniform-machines scheduling: Difference between revisions

Revision as of 20:06, 19 June 2021

Revision as of 20:11, 19 June 2021

Line 25:

Minimizing the ''maximum'' completion time is NP-hard even for identical machines, by reduction from the [[partition problem]]. Many approximation algorithms are known.

'''Graham''' proved that:

'''Graham'''<ref name=":2">{{Cite journal|last=Graham|first=Ron L.|author-link=Ronald Graham|date=1966|title=Bounds for Certain Multiprocessing Anomalies|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1966.tb01709.x|journal=Bell System Technical Journal|language=en|volume=45|issue=9|pages=1563–1581|doi=10.1002/j.1538-7305.1966.tb01709.x|issn=1538-7305}}</ref> proved that:

* Any [[list scheduling]] algorithm (an algorithm that processes the jobs in an arbitrary fixed order, and schedules each job to the first available machine) is a <math>2-1/m</math> approximation for ''identical'' machines.<ref Itname=":2">{{Cite journal|last=Graham|first=Ron L.|author-link=Ronald Graham|date=1966|title=Bounds for Certain Multiprocessing Anomalies|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1966.tb01709.x|journal=Bell System Technical Journal|language=en|volume=45|issue=9|pages=1563–1581|doi=10.1002/j.1538-7305.1966.tb01709.x|issn=1538-7305}}</ref> The bound is tight for any ''m''. This algorithm runs in time O(''n'').

* The specific list-scheduling algorithm called '''Longest Processing Time First''' (LPT), which sorts the jobs by descending length, is a <math>4/3-1/3m</math> approximation for ''identical'' machines.<ref name=":1">{{Cite journal|last=Graham|first=Ron L.|author-link=Ronald Graham|date=1969-03-01|title=Bounds on Multiprocessing Timing Anomalies|url=https://epubs.siam.org/doi/abs/10.1137/0117039|journal=SIAM Journal on Applied Mathematics|volume=17|issue=2|pages=416–429|doi=10.1137/0117039|issn=0036-1399}}</ref>{{Rp|sec.5}} 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> It is also called [[greedy number partitioning]],.

'''Sahni'''<ref>{{Cite journal|last=Sahni|first=Sartaj K.|date=1976-01-01|title=Algorithms for Scheduling Independent Tasks|url=https://doi.org/10.1145/321921.321934|journal=Journal of the ACM|volume=23|issue=1|pages=116–127|doi=10.1145/321921.321934|issn=0004-5411}}</ref> presented several algorithms for ''identical'' machines. In particular:

* A PTAS that attains (1+ε)OPT in time <math>O(n\cdot (n^2 / \epsilon)^{m-1})</math>.

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