s
Section 5.2 Topological Sorting
359
Task 9:
max(time to complete task 5, time to complete task 8)
+ time to perform task 9
= max(6.0, 12.0) + 2.0 = 12.0 + 2.0 = 14.0
Task 10:
max(time to complete task 2, time to complete task 8)
+ time to perform task 10
= max(7.0, 12.0) + 3.0 = 12.0 + 3.0 = 15.0
Task 11:
max(time to complete task 9, time to complete task 10)
+ time to perform task 11
= max(14.0, 15.0) + 5.0 = 15.0 + 5.0 = 20.0
Task 12:
max(time to complete task 7, time to complete task 11)
+ time to perform task 12
= max(3.0, 20.0) + 0.5 = 20.0 + 0.5 = 20.5
Therefore the minimum number of hours to manufacture a rocking chair is 20.5.
From node 12, we can travel back in the chart, selecting at each point of multiple prerequisites the node that contributed the maximum value. This gives the
sequence of nodes
12, 11, 10, 8, 4, 1
or, reversing this sequence,
1, 4, 8, 10, 11, 12
The sum of the times to perform each task in this sequence is 20.5. If any of
these tasks takes longer to perform than its allotted time, the entire project will
take longer than 20.5 hours. This sequence of nodes is a critical path through the
PERT chart—performing these tasks in the allotted time is critical to completing
the entire project on time.
The critical path in a PERT chart represents the minimum time to completion
of the entire project. If a task not on the critical path takes longer than its allotted
time to perform, then the critical path may shift to include this node, because it
then becomes the bottleneck slowing down completion of the total project. In a
complex project, the critical path must continually be recomputed to determine
where best to allocate resources to move the project forward.
PRaCtiCe 18 Compute the minimum time to completion and the nodes on the critical path for the housebuilding project of Practice 17.
Given a partial ordering r on a finite set, there is always a total ordering s that
is an extension of r, meaning that if x r y, then x s y. The process of topological
sorting finds such a total ordering from a partial ordering. This is indeed a sorting
process in the sense that the objects end up being totally ordered, but since they
must be partially ordered to begin with, it is a very specialized sorting process.
Recall that in a finite partially ordered set, an element is minimal if it has
no predecessors. In a finite nonempty partially ordered set, at least one minimal
■
Section 5.2 Topological Sorting
359
Task 9:
max(time to complete task 5, time to complete task 8)
+ time to perform task 9
= max(6.0, 12.0) + 2.0 = 12.0 + 2.0 = 14.0
Task 10:
max(time to complete task 2, time to complete task 8)
+ time to perform task 10
= max(7.0, 12.0) + 3.0 = 12.0 + 3.0 = 15.0
Task 11:
max(time to complete task 9, time to complete task 10)
+ time to perform task 11
= max(14.0, 15.0) + 5.0 = 15.0 + 5.0 = 20.0
Task 12:
max(time to complete task 7, time to complete task 11)
+ time to perform task 12
= max(3.0, 20.0) + 0.5 = 20.0 + 0.5 = 20.5
Therefore the minimum number of hours to manufacture a rocking chair is 20.5.
From node 12, we can travel back in the chart, selecting at each point of multiple prerequisites the node that contributed the maximum value. This gives the
sequence of nodes
12, 11, 10, 8, 4, 1
or, reversing this sequence,
1, 4, 8, 10, 11, 12
The sum of the times to perform each task in this sequence is 20.5. If any of
these tasks takes longer to perform than its allotted time, the entire project will
take longer than 20.5 hours. This sequence of nodes is a critical path through the
PERT chart—performing these tasks in the allotted time is critical to completing
the entire project on time.
The critical path in a PERT chart represents the minimum time to completion
of the entire project. If a task not on the critical path takes longer than its allotted
time to perform, then the critical path may shift to include this node, because it
then becomes the bottleneck slowing down completion of the total project. In a
complex project, the critical path must continually be recomputed to determine
where best to allocate resources to move the project forward.
PRaCtiCe 18 Compute the minimum time to completion and the nodes on the critical path for the housebuilding project of Practice 17.
Given a partial ordering r on a finite set, there is always a total ordering s that
is an extension of r, meaning that if x r y, then x s y. The process of topological
sorting finds such a total ordering from a partial ordering. This is indeed a sorting
process in the sense that the objects end up being totally ordered, but since they
must be partially ordered to begin with, it is a very specialized sorting process.
Recall that in a finite partially ordered set, an element is minimal if it has
no predecessors. In a finite nonempty partially ordered set, at least one minimal
■