Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > The Drilling Problem
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

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:
  1. He developed a scheme which did the job in only 25 passes.
  2. 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.

 
 
go backgo forward
go backgo forward