Finally, task 6 can be done at any time—nothing needs to be done before
it, and it is not a prerequisite for any other task. Additionally, each task
must be assigned to a single worker and not broken up into subtasks—if
we could do this, we’d simply label each subtask as a separate task.
A little additional terminology is associated with the above digraph. A
task is ready if all prerequisites for the task have been completed. In the
above diagram, tasks 1, 2, 3, and 6 are ready at the outset, whereas task 5
will be ready only when task 3 has been completed, and task 4 will be ready
only when both tasks 1 and 2 are completed. Notice that it will take a
minimum of 16 time units to complete all the tasks, as task 2 followed by
task 4, which requires 16 time units, is the critical path—the path of long-
est duration.
Numerous algorithms have been devised for scheduling tasks; we’ll ex-
amine just one of them, which is known as priority-list scheduling. The
idea is simple. We make a list of the tasks in order of importance. When a
task is finished, we cross it off the list. If someone is free to work on a task,
we set that person to work on the most important unfinished task, as deter-
mined by the priority list—if several mechanics are free, we assign them in
alphabetical order. The algorithm does not describe how the priority list is
constructed—for instance, if the garage owner’s wife needs her oil changed,
that item may be placed at the top of the priority list, and if someone slips
the garage owner $20 for extra-fast service, that might go right behind it.
To illustrate how all this stuff comes together, let’s suppose that times
in the above digraph are measured in hours, and our priority list is T1,
T2, T4, T3, T5, T6. If Al is the only mechanic on hand, there is no real
scheduling to be done—Al just does all the jobs on the priority list in that
order, and it takes him a total of 32 hours (the sum of all the times) to fin-
ish all the tasks. However, if the garage hires Bob, another mechanic, we
use the priority list to construct the following schedule.
Mechanic Task Start Times
0 4 6 9 11 16 18
Al T1 T3 T5 T6 Done
Bob T2 T4 Idle DoneSince tasks 1 and 2 are at the head of the priority list and both are ready at
the start, we schedule Al for task 1 and Bob for task 2. When Al finishes
task 1, at the end of 4 hours, the next task on the priority list is task 4—but
task 4 isn’t ready yet, as Bob hasn’t finished task 2. So Al must bypass task
4 and start in on task 3, the next task on the priority list. The rest of the dia-
4 How Math Explains the World