Optimal scheduling on multi-processor computing systems

A set of tasks {T1, T2, ..., Tr] are to be scheduled on a two-processor computing system. The execution time of each of the tasks is given. Moreover, a partial ordering ≪ over the set of tasks is specified. If Ti ≪ Tj, it is required that the execution of Tj will not begin until the completion of the execution of Ti. Let ω denote the total elapsed time for the execution of all the tasks in the set when an optimal non-preemptive schedule is used. Let ω′ denote the total elapsed time for the execution of all the tasks in the set when an optimal preemptive schedule is used. Trivially, we know that ω ≥ ω′ However, it can be shown that ω′ ≥ 3/4 ω This result can be extended to an n-processor computing system. In this case, ω′ ≥ n+1/2n ω Moreover, these are best possible bounds. A possible interpretation of the results is: The installation of a high speed drum in a two-processor computing system will increase the operation speed of the system by at most 25%. For an n-processor system, the increment is at most 50%. (The installation of a high speed drum enables us to interrupt the execution of tasks at will.)