gram is pretty straightforward. This schedule is as good as we could hope
for, as there are a total of 34 hours that must be scheduled, and there is no
way we can schedule 17 hours for each mechanic (unless we allow a task to
be broken up between two mechanics, which isn’t allowed by the rules). It
finishes all tasks as quickly as possible, and minimizes the amount of idle
time, two frequently used criteria in constructing schedules.
When Making Things Better Actually Makes Things Worse
The interaction between the task digraph and the priority list is compli-
cated, and unexpected situations can arise.
T1-3T9-9T2-2 T3-2 T4 -2T5-4 T6-4 T7-4 T8-4The priority list is just the tasks in numerical order: T1, T2, T3,... , T9.
The garage has three mechanics: Al, Bob, and Chuck. The schedule that
results appears below.
Mechanic Task Start Times
0 2 3 4 8 12
Al T1 T9 Done
Bob T2 T4 T5 T7 Done
Chuck T3 Idle T6 T8 DoneFrom a schedule standpoint, this is a “perfect storm” scenario. The
critical path is 12 hours long, all tasks are finished by this time, and we
have minimized the amount of idle time, as there are 34 hours of tasks to
be done and three mechanics available for 12 hours would be a total of 36
hours.
If the garage has a lot of business, it might decide to hire an extra me-
chanic. If the jobs to be done conform to the above digraph and the same
priority list, we would certainly expect that there would be a lot more idle
time, but the resulting schedule contains a surprise.
Prologue 5