Uniform-machines scheduling: Difference between revisions

Revision as of 14:53, 18 June 2021

Revision as of 15:07, 18 June 2021

Line 8:

==Algorithms==

The simple algorithm called [[greedy number partitioning]], or the '''LPTSPT algorithm''' (LongestShortest Processing Time First), sortswhich theruns jobsin bytime theirO(''n'' length,log longest first''n''), and then assigns them tominimizes the processor''average'' with the earliest endcompletion time so far. While originally developed foron ''identical'' processors, it has good asymptotic convergence properties even with different speedsmachines.<ref>{{Cite journal|last=FrenkHorowitz|first=J. B. G.Ellis|last2=Rinnooy KanSahni|first2=A. H. G.Sartaj|date=19871976-0504-01|title=TheExact Asymptoticand OptimalityApproximate ofAlgorithms thefor LPTScheduling RuleNonidentical Processors|url=https://pubsonline.informsdoi.org/doi/abs/10.12871145/moor321941.12.2.241321951|journal=MathematicsJournal of Operationsthe ResearchACM|volume=1223|issue=2|pages=241–254317–327|doi=10.12871145/moor321941.12.2.241321951|issn=03640004-765X5411}}</ref>

'''Bruno, Coffman and Sethi'''<ref>{{Cite journal|last=Bruno|first=J.|last2=Coffman|first2=E. G.|last3=Sethi|first3=R.|date=1974-07-01|title=Scheduling independent tasks to reduce mean finishing time|url=https://doi.org/10.1145/361011.361064|journal=Communications of the ACM|volume=17|issue=7|pages=382–387|doi=10.1145/361011.361064|issn=0001-0782}}</ref> present an algorithm, running in time <math>O(\max(m n^2,n^3))</math>, for minimizing the ''average'' completion time on ''unrelated'' machines. They show that minimizing the ''weighted average'' completion time is NP-hard even on ''identical'' machines, by reduction from the [[Knapsack problem|knapsack problem.]]

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

The simple algorithm called [[greedy number partitioning]], or the '''LPT algorithm''' (Longest Processing Time First), 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>{{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>''' present several algorithms for both uniform machines and unrelated machines, with various objective functions:

* An exact algorithm for minimizing the ''maximum'' completion time on both uniform and unrelated machines, with exponential run-time (bothnote that these problems are NP-hard).

*An exact algorithm for minimizing the ''average'' completion time on ''uniform'' machines, with run time O(''n'' log ''m n'').

*An exact algorithms for minimizing the ''weighted-average completion time'' on ''uniform'' machines, with exponential run-time (this problem is NP-hard).

'''Hochbaum and Shmoys''',<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> who developed a PTAS for identical processors, extended their PTAS to handle processors with different speeds.