Assume an order-requirement digraph has a critical path with length 40 minutes. Based on this information, when the digraph is scheduled on four machines, how much time will be required?
A) Exactly 10 minutes
B) Exactly 30 minutes
C) At least 40 minutes
D) Exactly 40 minutes

Question

Quizplus · Accepted Answer

The critical path represents the longest path through the order-requirement digraph and determines the minimum time required to complete all tasks. When the digraph is scheduled on four machines, the tasks can be parallelized to some extent, but the time required will still be at least as long as the critical path (since parallelization cannot reduce the length of the longest path). Therefore, the answer is at least 40 minutes. Choice C correctly reflects this understanding.

Assume an Order-Requirement Digraph Has a Critical Path with Length