Information Technology Reference
In-Depth Information
2.2.3
Automated Drilling Location and Hit Sequencing
Consider an automated drilling machine that drills holes on a flat sheet. The turret has
to be loaded with all the tools required to hit the holes. There is no removing or adding
of tools. The machine bed carries the flat plate and moves from home, locating each
scheduled hit on the flat plate under the machine turret. Then the turret rotates and
aligns the proper tool under the hit. This process continues until all hits are completed
and the bed returns to the home position.
There are two problems to be solved here. One is to load tools to the turrets and
the other is to locate or sequence hits. The objective is to minimize the cycle time
such that the appropriate tools are loaded and the best hits-sequence is obtained. The
problem can therefore be divided into two: (i) solve a TSP for the inter
hit sequencing;
(ii) solve a quadratic assignment problem (QAP) for the tool loading. [21] developed a
mathematical formulation to this problem and iterated between the TSP and QAP. Once
the hit sequence is known, the sequence of tools to be used is then fixed since each hit
requires specific tool. On the other hand, if we know the tool assignment on the turret,
we need to know the inter-hit sequence. Connecting each hit in the best sequence is
definitely a TSP, where we consider the machine bed home as the home for the TSP,
and each hit, a city. Inter
−
hit travel times and the rotation of the turret are the costs
involved and we take the maximum between them, i.e. inter
−
hit
travel time, turret rotation travel time). The cost to place tool
k
in position
i
and tool
l
in position
j
is the time it takes the turret to rotate from
i
to
j
multiplied by the number
of times the turret switches from tool
k
to
l
.
The inter-hit travel times are easy to estimate from the geometry of the plate to be
punched and the tools required per punch. The inter
−
hit cost = max (inter
−
hits times are first estimated and
then adjusted according to the turret rotation times. This information constitutes the
data for solving the TSP. Once the hit sequence is obtained from the TSP, the tools
are placed, by solving the QAP. Let us illustrate the TSP
−
−
QAP solution procedure by
considering an example.
Example 2.2
A numerically controlled (NC) machine is to punch holes on a flat metal sheet and the
hits are shown in Fig 2.4. The inter-hit times are shown in Table 2.2. There are four tools
{
. The machine turret can hold five tools and
rotates in clockwise or anti-clockwise direction. When the turret rotates from one tool
position to an adjacent position, it takes
60
time units. It takes
75
time units and
90
time units to two locations and three locations respectively. The machine bed home is
marked
0
. Assign tools to the turret and sequence the hits.
a
,
b
,
c
,
d
}
and the hits are
{
1
,
2
,
3
,
4
,
5
,
6
,
7
}
Solution
From the given inter
−
hit times, modified inter-hit times have to be calculated using
the condition: inter
hit cost = max (inter-hit travel time, turret rotation travel time).
For example, for inter
−
hit between locations
1
and
2
, the inter-hit travel time is
50
time units. Now, the tool for hit
1
is
c
while the tool for hit
2
is
a
. This means there is
−
Search WWH ::
Custom Search