Uniform-machines scheduling: Difference between revisions

Revision as of 21:35, 19 June 2021

Revision as of 00:21, 24 June 2021

Line 15:

=== Minimizing the weighted-average completion time ===

Minimizing the ''weighted average'' completion time is NP-hard even on ''identical'' machines, by reduction from the [[Knapsack problem|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>

'''Sahni<ref name=":3" />''' presents an exponential-time algorithm and a polynomial-time approximation algorithm for ''identical'' machines.

Line 22:

* Exact [[dynamic programming]] algorithms for minimizing the ''weighted-average completion time'' on ''uniform'' machines. These algorithms run in exponential time.

* [[Polynomial-time approximation scheme]]<nowiki/>s, which for any ''ε''>0, attain at most (1+ε)OPT. For minimizing the ''weighted average'' completion time on two ''uniform'' machines, the run-time is <math>O(10^{l} n^2)</math> = <math>O( n^2 / \epsilon)</math>, so it is an FPTAS. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case. They do not present an algorithm for ''weighted-average'' completion time on ''unrelated'' machines.

=== Minimizing the maximum completion time (makespan) ===

Line 30:

* 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).

* [[Polynomial-time approximation scheme]]<nowiki/>s, which for any ''ε''>0, attain at most (1+ε)OPT. For minimizing the ''maximum'' completion time on two ''uniform'' machines, their algorithm runs in time <math>O(10^{2l} n)</math>, where <math>l</math> is the smallest integer for which <math>\epsilon \geq 2\cdot 10^{-l}</math>. Therefore, the run-time is in <math>O( n / \epsilon^2)</math>, so it is an [[FPTAS]]. For minimizing the ''maximum'' completion time on two ''unrelated'' machines, the run-time is <math>O(10^{l} n^2)</math> = <math>O( n^2 / \epsilon)</math>. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.

'''Hochbaum and Shmoys'''<ref name=":02">{{Cite journal|last1=Hochbaum|first1=Dorit S.|last2=Shmoys|first2=David B.|date=1987-01-01|title=Using dual approximation algorithms for scheduling problems theoretical and practical results|url=https://doi.org/10.1145/7531.7535|journal=Journal of the ACM|volume=34|issue=1|pages=144–162|doi=10.1145/7531.7535|issn=0004-5411|s2cid=9739129}}</ref> presented several approximation algorithms for any number of [[Identical-machines scheduling|''identical'' machines]]. Later,<ref>{{Cite journal|last=Hochbaum|first=Dorit S.|last2=Shmoys|first2=David B.|date=1988-06-01|title=A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach|url=https://epubs.siam.org/doi/abs/10.1137/0217033|journal=SIAM Journal on Computing|volume=17|issue=3|pages=539–551|doi=10.1137/0217033|issn=0097-5397}}</ref> they developed a PTAS for ''uniform'' machines.