The problem involves scheduling tasks on two processors for a directed acyclic graph (DAG), where each task $T_i$ has a given processing time (in parentheses) and dependencies represented by directed edges.

Let’s go through it step-by-step.

Step 1: Identify Task Durations and Dependencies

From the graph:

• Tasks with durations:
  • $T1$: 1 hour
  • $T2$: 1 hour
  • $T3$: 2 hours
  • $T4$: 1 hour
  • $T5$: 1 hour
  • $T6$: 5 hours
  • $T7$: 2 hours
  • $T8$: 4 hours
  • $T9$: 5 hours
• Dependencies (from the arrows):
  • $T1 \rightarrow T4, T5$
  • $T2 \rightarrow T5$
  • $T3 \rightarrow T6$
  • $T4 \rightarrow T7$
  • $T5 \rightarrow T8$
  • $T6 \rightarrow T9$
  • $T7 \rightarrow T8$
  • $T8, T9 \rightarrow \text{End}$

Step 2: Schedule Tasks on Two Processors

Criteria:

1. Respect dependencies.
2. Minimize overall completion time.
3. Use no more than 15 hours.

Possible Schedule

We’ll aim to balance the load across two processors and sequence tasks based on dependencies. Here’s one feasible schedule:

Explanation:

• 0-1 hours: Processor 1 handles $T1$, and Processor 2 handles $T2$ (independent tasks).
• 1-3 hours: $T4$ (depends on $T1$) is assigned to Processor 1, and $T3$ (independent) to Processor 2.
• 3-8 hours: $T5$ (depends on $T1$ and $T2$) is on Processor 1, and $T6$ (depends on $T3$) is on Processor 2.
• 3-5 hours: $T7$ (depends on $T4$) starts on Processor 1.
• 8-13 hours: $T8$ (depends on $T5$ and $T7$) on Processor 1, and $T9$ (depends on $T6$) on Processor 2.
• End: Both processors complete by hour 13.

Step 3: Optimal Completion Time

Using the above schedule, the total time is 13 hours, which is within the 15-hour limit.

Step 4: Bound on Optimal Finishing Time

For part (b), using the critical path (longest path through the task graph):

• Critical Path: $T1 \rightarrow T4 \rightarrow T7 \rightarrow T8 \rightarrow \text{End}$ with total time $1 + 1 + 2 + 4 = 8$ hours.
• Lower Bound on Optimal Time: 8 hours (time to complete the critical path).

The schedule achieves a completion time of 13 hours, which is close to optimal given dependencies and processor constraints.

Would you like further details on each step or have any specific questions?

Related Questions

1. How would the schedule change if there was an additional processor?
2. How would different task durations affect the optimal schedule?
3. What happens if one of the dependencies is removed?
4. Could tasks $T1$ and $T2$ be scheduled on the same processor initially?
5. How do different scheduling algorithms, like Earliest Start Time, affect the outcome?

Tip

When dealing with scheduling problems, visualize dependencies and critical paths to identify constraints quickly.