Adapted from ``Combinatorial Scheduling Theory'' by R.L. Graham.
Things have not gone well in the assembly section of the Acme Bicycle Company. Although sales are high, the assembly division is unable to meet quota. You have been sent to straighten things out. You begin by finding out exactly how a bicycle is made. You figure that when you have found out what the assemblers are doing you will have no difficulty determining a better way of doing things (after all, what good is spending $17,000 per year on school if you can't make a bicycle at the end of it?).
The first thing you learn is that the assembly of a bicycle can be broken into a number of smaller jobs (with the time in parantheses):
Due to space and equipment restrictions, the 20 assemblers are divided into 10 teams of 2 people.
Question: What is the minimum amount of time to build a bicycle (based on the data so far)?
Unfortunately, it is impossible to build a bicycle in arbitrary order. For instance, it is difficult to attach the front fork if the front wheel is already attached. After length discussions, you determine the following requirements:
B must be preceeded by A.
J must be preceeded by B, C, D, E and G.
C must be preceeded by D, E, and A.
Both E and F must be preceeded by D.
Both H and I must be preceeded by E, F and G.
G must be preceeded by F.
To simplify your search for a schedule, you have implemented some working rules: the first rule is that no assembler can be idle if there is some job for her to do. The second is that once an assembler starts a subassembly, he must continue until it is completed. The second rule might be enforced by the union; the first rule is an example of a heuristic: rather than look at all possible things for an assembler to do, we simplify the problem a bit.
Question: What is the fastest a team of two can finish a bicycle?
Unfortunately, that is not fast enough to meet quota. Therefore, you decide to buy power tools for every assembler. These tools reduce every operation by one minute. This should be enough to assure quota (which requires a 32 minute assembly).
Question: What is the fastest a team of two can build a bicycle with power tools?
Very strange, we seem to have wasted a lot of money on these tools. At this point, your superiors are wondering if they would have done better with a Wharton graduate. You decide to throw money to the wind in order to meet quota. You return the rented power tools and hire 10 new assemblers. You do not have enough space to form new teams, so instead you add one person to each team, forming teams of three. Surely this will be enough to meet quota.
Question: What is the fastest a team of three can build a bicycle?
You are left wandering the halls muttering to yourself when your termination notice arrives.
There are a couple of things to notice in this exercise:
-- When you really want to optimize, it is difficult to know when to stop trying heuristics.
-- Heuristics can lead to weird behavior (although here the behavior is not necessarily the fault of the heuristics -- it is the fault of the work rules, although you might have assumed the work rules did not affect optimality).