Chapter 8, Problem 48E

Consider the project described by the digraph shown in Fig. 8-37, and assume that you are to schedule this project using $N=2$ processors.

a. Use the decreasing-time algorithm to schedule the project. Show the timeline for the project and finishing time $Fin$.

b. Find an optimal schedule and the optimal finishing time $Opt$.

c. Use the relative error formula $\epsilon =\frac{Fin-Opt}{Opt}$ to find the relative of the schedule found in (a), and express your answer as a percent.