Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 13:
* The '''SPT algorithm''' (Shortest Processing Time First), sorts the jobs by their length, shortest first, and then assigns them to the processor with the earliest end time so far. It runs in time O(''n'' log ''n''), and minimizes the average completion time on ''identical'' machines,<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> '''P||'''<math>\sum C_i</math>.
**There can be many SPT schedules; finding the SPT schedule with the smallest finish time (also called OMFT - optimal mean finish time) is NP-hard. Sahni<ref name=":3" /> presents an exponential-time algorithm and a polynomial-time approximation algorithm for identical machines.
* '''Horowitz and Sahni<ref name=":0" />''' present an exact algorithm, with run time O(''n'' log ''m n''), for minimizing the average completion time on ''uniform'' machines, '''Q||'''<math>\sum C_i</math>.
* '''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, '''R||'''<math>\sum C_i</math>.
=== Minimizing the weighted-average completion time ===
Minimizing the ''weighted average'' completion time is NP-hard even on ''identical'' machines, by reduction from the [[Knapsack problem|knapsack problem.]]'''<ref name=":0" />''' It is NP-hard even if the number of machines is fixed and at least
'''Sahni<ref name=":3" />''' presents an exponential-time algorithm and a polynomial-time approximation algorithm for ''identical'' machines.
'''Horowitz and Sahni<ref name=":0" />''' presented:
* Exact [[dynamic programming]] algorithms for minimizing the ''weighted-average completion time'' on ''uniform'' machines. These algorithms run in exponential time.
Line 30 ⟶ 35:
* 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 name=":3">{{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
* A PTAS that attains (1+ε)OPT in time <math>O(n\cdot (n^2 / \epsilon)^{m-1})</math>. It is an FPTAS if ''m'' is fixed. For m=2, the run-time improves to <math>O(n^2 / \epsilon)</math>. The algorithm uses a technique called ''interval partitioning''.
'''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:
| |||