How Math Explains the World.pdf

There’s a lot of idle time here, but that’s to be expected. The important
point is that all tasks are finished after twelve hours, and that’s the opti-
mal solution.
Let’s see what happens when we look at the three mechanics when the
task times were all reduced by one hour.

T9-8

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

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

The priority list is the same as the above: T9, T5, T6, T7, T8, T1, T2, T3,
T4. This leads to the following schedule.

Mechanic Task Start and Finish Times

0 1 2 5 8 10

Al T1 T9 Done

Bob T2 T4 T5 T7 Idle Done

Chuck T3 Idle T6 T8 Idle Done

Once again, this is the best we can do. Is this the sword that cuts through
the Gordian knot of scheduling? Regrettably not. As you might have sus-
pected from the fact that this problem still has a $1 million bounty on its
head, neither the priority-list algorithm nor decreasing-times processing
will always deliver the optimal schedule. However, decreasing-times pro-
cessing is superior to the list-processing algorithm in the following impor-
tant respect: the worst-case scenario with decreasing-times processing is
substantially superior to the worst-case scenario with the list-processing
algorithm. Suppose that T represents the length of the optimal schedule.
If m mechanics are available, then the worst that can happen with the list-
processing algorithm is a schedule of length (2
1/m)T. However, if de-
creasing-times processing is used, the worst that can happen is a schedule
whose length is (4T
m)/3.^1
There is one such algorithm that always works: construct all possible
schedules, and choose the one that best optimizes whatever criteria are

Murphy’s Law 157