Next: MINIMUM MULTIPROCESSOR SCHEDULING WITH Up: Multiprocessor Scheduling Previous: MINIMUM RESOURCE CONSTRAINED SCHEDULING Index

### MINIMUM PREEMPTIVE SCHEDULING WITH SET-UP TIMES

- 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 ti of t a pair of nonnegative integers such that and, for , . Such a schedule must satisfy the following additional constraint: Whenever two subtasks ti of t and tj' of t' with are scheduled consecutively on the same machine (i.e., and no other subtask tk'' 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

  [94].

- 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 [444].

- Garey and Johnson: SS6 and SS12

Next: MINIMUM MULTIPROCESSOR SCHEDULING WITH Up: Multiprocessor Scheduling Previous: MINIMUM RESOURCE CONSTRAINED SCHEDULING Index