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

go backgo forward
go backgo forward

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.

A Gang Drill

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 different spots.


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.

The Problem

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!!!

go backgo forward
go backgo forward