MINIMUM MULTIPROCESSOR SCHEDULING WITH SPEED FACTORS

• INSTANCE: Set T of tasks, number m of processors, for each task $t\in T$ a length $l(t)\in Z^+$, and for each processor $i\in [1..m]$ a speed factor $s(i)\in Q$ such that s(1)=1 and $s(i)\ge 1$ for every i.

• SOLUTION: An m-processor schedule for T, i.e., a function $f: T\rightarrow[1..m]$.

• MEASURE: The finish time for the schedule, i.e., $\max\limits_{i\in[1..m]}\displaystyle\sum\limits_{t\in T: \atop f(t)=i} l(t)/s(i)$.

  
  

• Good News: Admits a PTAS [256].

• Bad News: Does not admit an FPTAS [256].

• Comment: Admits an FPTAS for the variation in which the number of processors m is constant [261].