- INSTANCE:
Set
*C*of compilers, set*T*of tasks, number*m*of processors, length and compiler for each , set-up time for each . - SOLUTION:
An
*m*-processor preemptive schedule for*T*, i.e., for each , a partition of*t*into any number of subtasks such that and an assignment that assigns to each subtask of*t*a pair of nonnegative integers such that and, for , . Such a schedule must satisfy the following additional constraint: Whenever two subtasks of*t*and of*t'*with are scheduled consecutively on the same machine (i.e., and no other subtask has and ), then if they have the same compiler (i.e.,*c(t) = c(t')*) and if they have different compilers. - MEASURE:
The overall completion time, i.e., the maximum over all subtasks of
.

*Good News:*Approximable within

[102].*Comment:*If all set-up times are equal, then the problem is approximable within*3/2-1/2m*for and admits an FPTAS for*m=2*[467].*Garey and Johnson:*SS6 and SS12