Unrelated-machines scheduling: Difference between revisions

Revision as of 19:02, 25 November 2021

Revision as of 07:18, 15 May 2022

Line 26:

Minimizing the ''weighted average'' completion time is NP-hard even on ''identical'' machines, by reduction from the [[knapsack problem]].'''<ref name=":0" />''' It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the [[partition problem]].<ref name=":3">{{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>

Schulz and Skutella<ref>{{Cite journal |last=Schulz |first=Andreas S. |last2=Skutella |first2=Martin |date=2002-01-01 |title=Scheduling Unrelated Machines by Randomized Rounding |url=https://epubs.siam.org/doi/abs/10.1137/S0895480199357078 |journal=SIAM Journal on Discrete Mathematics |volume=15 |issue=4 |pages=450–469 |doi=10.1137/S0895480199357078 |issn=0895-4801}}</ref> present a (3/2+ε)-approximation algorithm using [[randomized rounding]].

=== Maximizing the profit ===