The Drilling Problem
First, A True Story...
A gang drill is commonly used in machine-tool plants to drill a series of holes.
The gang drill is a set of drill bits placed on a single head; in one
pass of the drill, several holes can be made. The gang drill has a significant constraint:
the individual bits on the gang drill must have a certain amount of space between them.
|Figure 1: A Gang Drill
As you can see, the drill head contains several drill
bits. The drill bits must be at least 35 units apart.
The item in which the holes are to be drilled is called the
workpiece. Between passes
of the gang drill, the workpiece can be moved so that the next pass drills holes in
|Figure 2: Workpiece
A surface - in our case, a hexagonal sheet of metal - in
which a specific pattern of holes will be drilled.
Also, the positions of the bits in the gang drill may be changed between passes -
as you can imagine, this can be time-consuming, and should not have to be done too often.
Given a workpiece and a gang drill with certain constraints,
what is the most efficient way to drill a desired pattern of holes?
This is exactly the situation faced by workers at a machine-tool plant several years ago.
A customer gave them a workpiece and a desired pattern of holes,
and the workers had to figure out the best way to achieve that pattern using the gang drills
available on the factory floor - i.e. by what sequence of movements and drill-bit-position changes?
Maximizing the efficiency of this process is very important!
The drilling will be part of a production process
carried out continuously for the life of the gang drill.
(These machine tools are very expensive!)
Any improvement in the efficiency of the process would have a substantial and
long-lasting positive effect.
The way to improve efficiency is to design the process such that
a small number of passes are made (provided all technological constraints are satisfied).
After several unsuccessful attempts, the most efficient way to drill a specific pattern
on the workpiece shown above was found and proven to be optimal.
How was this done?
You guessed it... through an application of graph theory!!!