Approximation Algorithm Task Scheduling

• ​BOUNDS ON MULTIPROCESSING TIMING ANOMALIE(1969)

  • ​general bound: $\frac{w'}{w} \leq 1+ \frac{n-1}{n'}$ 

  •  dynamically formed: $\frac{w'}{w} \leq 2- \frac{2}{n+1}$ 

  • ​The special case < is empty: $\frac{ w_{L} }{w_{0}} \leq \frac{3}{4}- \frac{1}{3n}$ 
    
    

  • ​a new algorithm: $\frac{ w(k)}{w_{0}} \leq 1+\frac{1-1/n}{1+[k/n]}$ 
    
    

• ​Approximation Algorithms for Scheduling Unrelated Parallel Machines(1990)

  • ​ Prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2unless P =NP

  • ​   A special case where the machines are identical:
       Refer to an algorithm that is guaranteed to produce a solution of length no more than p times the optimum as a p-approximation algorithm.
    

  • ​   Identical machines is the case of machines that run at different speeds but do so uniformly:
      We prove that the existence of a polynomial (1 + $ε$ )-approximation algorithm for any  $ε$ <1/2 would imply thatP = NP.

  • ​Extend Pott's[1985] work by proving that the fractional solution to the linear program can be rounded to a good integral approximation in polynomial time

• ​Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speed(1999)

  • ​  Each machine i runs at a specified speed s , is1,..., m, and so if job j is i processed by machine i, it takes prs time units to be completed, ji is1,..., m, js1,..., n;
      We provide an O （log m) -approximation algorithm for this problem(before the best is O( $\sqrt{m}$ ). Furthermore, we provide a much stronger performance guarantee for instances in which there are a limited number of distinct machine speeds

• ​Optimization and approximation in deterministic sequencing and scheduling: A survey(1979)

  • ​P|prec, $p_{j}$ =1| $C_{max}$ :
    
    with critical path:
     $C_{max} (CP)/ C_{max}^{*} \leq \begin{cases} \frac{4}{3} &\text{if } m=2 \\ 2-\frac{1}{m-1} &\text{if } m \geq 3 \end{cases}$ 
    [Chen 1975 &Chen & Liu 1975]
    [Kunde 1976]
    
    use Coffman-Graham(CG) algorithm: $C_{max} (CG)/ C_{max}^{*} \leq 2-\frac{2}{m} (m \geq 2)$ 
    
    

  •  $P2| prec,1\leq p_{j}\leq2|C_{max}$ : 
    
    $C_{max}(GCG)/C_{max}^{*} \leq \begin{cases} \frac{3}{4} &\text{if } k=2 \\ \frac{3}{2}-\frac{1}{2k} &\text{if } k \geq 2 \end{cases}$