MINIMUM 3-DEDICATED PROCESSOR SCHEDULING

• INSTANCE: Set T of tasks, set P of 3 processors, and, for each task $t\in T$, a length $l(t)\in Z^+$ and a required subset of processors $r(t) \subseteq P$.

• SOLUTION: A schedule for T, i.e., a starting time function $s: T \rightarrow Z^+$ such that, for any two tasks $t_1$ and $t_2$ with $r(t_1) \cap r(t_2) \neq \emptyset$, either $s(t_1)+l(t_1) < s(t_2)$ or $s(t_2)+l(t_2) < s(t_1)$.

• MEASURE: The makespan of the schedule, i.e., $\max_{t \in T}(s(t)+r(t))$.

  
  

• Good News: Admits a PTAS [18].

• Comment: Admits a PTAS even for any fixed number of processors.