Revision as of 08:34, 5 October 2021 edit Erel Segal (talk \| contribs) Extended confirmed users, IP block exemptions 14,576 edits →Monotonicity and Truthfulness Tag: Visual edit ← Previous edit		Revision as of 16:46, 13 October 2021 edit undo Erel Segal (talk \| contribs) Extended confirmed users, IP block exemptions 14,576 edits →Algorithms Tag: Visual edit Next edit →
Line 26: === Minimizing the maximum completion time (makespan) === Minimizing the ''maximum'' completion time is NP-hard even for ''identical'' machines, by reduction from the [[partition problem]]. A constant-factor approximation is attained by the [[Longest-processing-time-first scheduling#uniform\|Longest-processing-time-first algorithm]]. '''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:

Uniform-machines scheduling: Difference between revisions