Uniform-machines scheduling: Difference between revisions

Revision as of 15:07, 18 June 2021

Revision as of 15:11, 18 June 2021

Line 8:

==Algorithms==

Minimizing the ''average'' completion time can be done in polynomial time:

The '''SPT algorithm''' (Shortest Processing Time First), which runs in time O(''n'' log ''n''), 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>

* The '''SPT algorithm''' (Shortest Processing Time First), whichsorts 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>

'''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.]]

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

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

MinimizingIn contrast, minimizing the ''weighted average'' completion time is NP-hard even on ''identical'' machines, by reduction from the [[Knapsack problem|knapsack problem.]]'''<ref name=":0" />''' Similarly, minimizing the ''maximum'' completion time is NP-hard even for identical machines, by reduction from the [[partition problem]]. Therefore, for these objectives, only efficient approximation algorithms are feasible.

The simple algorithm called [[greedy number partitioning]], or 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>''' present severalexact algorithms for minimizing the ''maximum'' completion time on both uniform machines and unrelated machines, withand variousfor objectiveminimizing functions:the ''weighted-average completion time'' on ''uniform'' machines. These algorithms run in exponential time (recall that these problems are all NP-hard).

* An exact algorithm for minimizing the ''maximum'' completion time on both uniform and unrelated machines, with exponential run-time (note 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.