MINIMUM PREEMPTIVE SCHEDULING WITH SET-UP TIMES

• INSTANCE: Set C of compilers, set T of tasks, number m of processors, length $l(t)\in Z^+$ and compiler $c(t)\in C$ for each $t\in T$, set-up time $s(c)\in Z^+$ for each $c\in C$.

• SOLUTION: An m-processor preemptive schedule for T, i.e., for each $t\in T$, a partition of t into any number of subtasks $t_1,\ldots,t_k$ such that $\sum_{i=1}^k l(t_i) = l(t)$ and an assignment $\sigma = (\sigma_1, \sigma_2)$ that assigns to each subtask $t_i$ of t a pair of nonnegative integers $(\sigma_1(t_i), \sigma_2(t_i))$ such that $1 \le \sigma_1(t_i) \le m$ and, for $1 \le i < k$, $\sigma_2(t_{i+1}) \ge \sigma_2(t_i) + l(t_i)$. Such a schedule must satisfy the following additional constraint: Whenever two subtasks $t_i$ of t and $t_j'$ of t' with $\sigma_2(t_i) < \sigma_2(t_j')$ are scheduled consecutively on the same machine (i.e., $\sigma_1(t_i) = \sigma_1(t_j')$ and no other subtask $t_k''$ has $\sigma_1(t_k'') = \sigma_1(t_i)$ and $\sigma_2(t_i) < \sigma_2(t_k'') < \sigma_2(t_j')$), then $\sigma_2(t_j') \ge \sigma_2(t_i) + l(t_i)$ if they have the same compiler (i.e., c(t) = c(t')) and $\sigma_2(t_j') \ge \sigma_2(t_i) + l(t_i) + s(c(t'))$ if they have different compilers.

• MEASURE: The overall completion time, i.e., the maximum over all subtasks of $\sigma_2(t_i)+l(t_i)$.

  
  

• Good News: Approximable within
  
  $$\max\left(\frac{3m}{2m+1},\frac{3m-4}{2m-2}\right)$$
  
  
  [102].

• Comment: If all set-up times are equal, then the problem is approximable within 3/2-1/2m for $m \geq 2$ and admits an FPTAS for m=2 [467].

• Garey and Johnson: SS6 and SS12