Uniform-machines scheduling: Difference between revisions

Revision as of 15:55, 18 June 2021

Revision as of 19:17, 19 June 2021

Line 8:

==Algorithms==

=== Minimizing the average completion time ===

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

Line 14 ⟶ 16:

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

=== Minimizing the maximum or the weighted-average completion time ===

In contrast, minimizingMinimizing 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 '''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. For ''identical'' machines, it asymptotically attains at most 4/3 of the maximum completion time. Iit 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>

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

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

Line 33 ⟶ 36:

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 thisthe PTAS for uniform machines to handle more general objective functions. Let ''C_i'' (for ''i'' between 1 and ''m'') be the makespan of machine ''i'' in a given schedule. Instead of minimizing the objective function max(''C_i''), one can minimize the objective function max(''f''(''C_i'')), where ''f'' is any fixed function. Similarly, one can minimize the objective function sum(''f''(''C_i'')).

== Extensions ==