s
Section 5.2 Topological Sorting
357
task
prerequisite tasks
hours to perform
1. Selecting wood
None
3. 0
2. Carving rockers
1
4. 0
3. Carving seat
1
6. 0
4. Carving back
1
7. 0
5. Carving arms
1
3. 0
6. Selecting fabric
None
1. 0
7. Sewing cushion
6
2. 0
8. Assembling back and seat
3, 4
2. 0
9. Attaching arms
5, 8
2. 0
10. Attaching rockers
2, 8
3. 0
11. Varnishing
9, 10
5. 0
12. Adding cushion
7, 11
0. 5
We can define a partial ordering on the set of tasks by
x d y 4 task x = task y or task x is a prerequisite to task y
It is easy to see that this relation is reflexive, antisymmetric, and transitive. Also,
x a y 4 task x is a prerequisite to task y
In the Hasse diagram for this partial ordering, the nodes are tasks; we’ll add
to each node the information about the time to perform the task. Also, as is traditional, we’ll orient the diagram so that if x a y, then x is to the left of y rather than
below y. Thus the entire diagram runs from left to right rather than from bottom to
top. Such a diagram for task scheduling is often called a PERT(program evaluation and review technique) chart, first developed for tracking the construction
of Navy submarines but useful for managing any complex project with a number of subtasks. The PERT chart for manufacturing rocking chairs is shown in
Figure 5.7, with task numbers substituted for task names and arrows pointing to
a task from its prerequisite task(s). The numbers in parentheses indicate the time
required to perform the task.
2(4.0)
10(3.0)
3(6.0)
4(7.0)
8(2.0)
1(3.0)
9(2.0)
5(3.0)
6(1.0) 7(2.0)
12(0.5)
11(5.0)
Figure 5.7