Uniform-machines scheduling: Difference between revisions

Revision as of 15:37, 18 June 2021

Revision as of 15:39, 18 June 2021

Line 16:

In 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 '''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 forFor ''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>

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