The Drilling Problem
The History of The Solution
Originally, the task was given to a junior engineer, who designed a tool
that accomplished the task using 33 passes. The result was considered to be less than satisfactory.
Afterward, a more experienced engineer came up with a better result: the new design
allowed the job to be done in 31 passes.
Then, the chief engineer of the plant challenged all the engineers to find a better solution.
A team of experienced engineers won a prize offered by the chief engineer by finding a solution
requiring only 29 passes.
Graph Theory to the Rescue!
One of the engineers from the plant consulted a friend who was (and is)
a mathematician specializing in Graph Theory.
The engineer showed the problem to his mathematician friend,
who immediately recognized it as a graph theory problem:
a special case of the famous Vertex Coloring Problem.
The mathematician did two things:
-
He developed a scheme which did the job in only 25 passes.
-
He proved that any scheme requires at least 25 passes.
|
In addition, it turned out that the secondary goal also was achieved:
the number of different gang drills used for the proposed scheme was 3 -
fewer than required by any previous design.
|