Revision as of 02:05, 19 August 2023 edit OAbot (talk \| contribs) Bots 646,409 edits m Open access bot: doi updated in citation with #oabot. ← Previous edit		Revision as of 14:53, 27 November 2023 edit undo Citation bot (talk \| contribs) Bots 5,872,605 edits Removed proxy/dead URL that duplicated identifier. \| Use this bot. Report bugs. \| Suggested by Corvus florensis \| #UCB_webform 195/2500 Next edit →
Line 13: Minimizing the ''maximum'' completion time is NP-hard even for ''identical'' machines, by reduction from the [[partition problem]]. Horowitz and Sahni'''<ref name=":0">{{Cite journal\|last1=Horowitz\|first1=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\|s2cid=18693114 \|issn=0004-5411\|doi-access=free}}</ref>''' presented: * Exact [[dynamic programming]] algorithms for minimizing the ''maximum'' completion time on both uniform and unrelated machines. These algorithms run in exponential time (recall that these problems are all NP-hard).

Unrelated-machines scheduling: Difference between revisions