Unrelated-machines scheduling: Difference between revisions

Revision as of 04:56, 2 March 2023

Revision as of 09:20, 27 March 2023

Line 23:

=== Minimizing the average completion time ===

Bruno, Coffman and Sethi<ref>{{Cite journal|last1=Bruno|first1=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|s2cid=2507557 |issn=0001-0782|doi-access=free}}</ref> present an algorithm, running in time <math>O(\max(m n^2,n^3))</math>, for minimizing the average job completion time on ''unrelated'' machines, '''R||'''<math>\sum C_j</math> (the average over all ''jobs'', of the time it takes to complete the jobs).

Minimizing the ''weighted average'' completion time, '''R||'''<math>\sum w_j C_j</math> (where ''w_j'' is the weight of job ''j''), 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|s2cid=10956951 |issn=0004-5411|doi-access=free}}</ref>

Schulz and Skutella<ref>{{Cite journal |last1=Schulz |first1=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]]. Their algorithm is a (2+ε)-approximation for the problem with job release times, '''R|<math>r_j</math>|'''<math>\sum w_j C_j</math>.