Bounds on the Scheduling of Typed Task Systems

We study the scheduling of different types of tasks on different types of processors. If there are k types of tasks and mᵢ, identical processors for tasks of type i, the finishing time of any list schedule is at most k + 1 - (1/ max (m₁ , ⋯ ,mₖ )) times worse than the optimal schedule. This bound is best possible. If the processors execute at different speeds then the performance of any list schedule (relative to the optimal schedule) is bounded by k plus the maximum ratio between the speeds of any two processors of the same type.