How Math Explains the World.pdf

Mechanic Task Start Times

0 2 3 6 7 15

Al T1 T8 Idle Done

Bob T2 T5 T9 Done

Chuck T3 T6 Idle Done

Don T4 T7 Idle Done

A postmortem on this schedule reveals that the trouble started when
Don was assigned task 4 at the start. This made task 8 available “too
early,” and so Al can take it on, with the result that task 9 gets started 3
hours later than in the original schedule. This is certainly somewhat un-
expected, as you would think that having more mechanics available would
not result in a later finishing time.
The garage has an alternative to hiring an extra mechanic—it can up-
grade the equipment used for the various tasks. When it does so, it finds
that the time for each task has been reduced by one hour. We’d certainly
expect good things to happen after the upgrade. The original job digraph
is now modified to the one below.

T9-8

T1-2 T2-1 T3-1 T4 -1

T5-3 T6-3 T7-3 T8-3

When the same priority list (and, of course, the priority-list scheduling
algorithm) is used for the original three mechanics, the following sched-
ule gets constructed.

Mechanic Task Start Times

0 1 2 5 8 13

Al T 1 T5 T8 Idle Done

Bob T 2 T4 T6 T9 Done

Chuck T 3 Idle T7 Idle Done

6 How Math Explains the World