Optimum path design applied to cutting holes in parts.

Wessely, Emil ; Hrubina, Kamil ; Balczak, Stanislav 等

1. INTRODUCTION

With cutting holes, when time spent to displace a tool is the shortest of all eventualities (minimum) and a cutting tool path trajectory is the shortest one, an actual and natural requirement, which is solved as an optimization procedure of cutting holes provided by one tool and applied to one group of holes, is changed to a minimization of passive paths.

Before a mathematical treatment of optimization of holes in parts cutting procedure is provided, we deal with a design of a cutting tool optimum path with cutting holes on a selected wall of a part. The shortest closed path has to be chosen of all cutting tool paths along which a cutting tool would pass, once through each hole. Passing of the tool through the hole refers to the tool entering the centre of the hole and leaving the hole after the hole completion. The holes centres in parts are determined in a plane, in a two-dimensional space by an ordered pair of real numbers (Hrubina & Jadlovska, 2002). The holes axes pass through the points that denote the holes centres. This is where a cutting tool has its start position when cutting a selected hole. The holes distances refer to the distances of the holes centres.

[FIGURE 1 OMITTED]

The problem of a minimization of a secondary requirement of a property, which determines the hole placement to a certain group, is simplified, for example, we will create a group in dependence on holes diameters and the problem can be transformed to several problems of a certain type, where a type of a hole cutting in a selected group of holes will be determining (Macura, 2005). Optimization of passive transitions with holes cutting is the problem related to a selection of a set having a finite number of possibilities /Fig. 1. The amount of time spent to displace the tool is the sum of times required to displace the tool from the j - th hole centre to the j - th hole centre of the following hole centre, where i, j = 1,2, ..., n, n [member of] N, N = {1,2,3, ...} (Macura, 2003).

2. A BRIEF DESCRIPTION OF THE APPLIED METHOD

Graph theory is a part of discrete mathematics researching graphs properties.

Different types of graphs can be used in various applications:

* not-oriented graph--graph edges are not oriented, eventually all edges are oriented in both directions.

* weighted graph--graph edges have an assigned value which denotes, e.g. length, permeability, speed ...

* oriented graph--graph edges have a determined orientation represented in figures mostly as an arrow.

[FIGURE 2 OMITTED]

Many practical problems can be reformulated to the problems referring to a certain class of graphs. In this case, the holes are nodes and the weighted edges represent the distance between the individual nodes. We generate a model representing individual nodes and their distances. The aim is to find the shortest path. Based on graph theory, it is possible to use one of the algorithms to search for the shortest path. We will use the search of the minimum skeleton. The minimum skeleton is such a skeleton of the weighted graph which has the smallest weight of its all skeletons, i.e. the smallest sum of edge weights (Hrubina et al., 2002). In the graph, we will select an arbitrary vertex V. As a result, a component graph G1 is formed. An edge with a minimum weight and which is one of the edges arising from the vertex V is selected for the minimum skeleton. Thus, a component graph containing the vertex V, a minimum edge with another incidental vertex is created. With finite graphs, the procedure is completed, with a vertex graph after the steps. The resulting graph is a minimum skeleton of the graph G. Several methods can be used to determine minimum skeletons. One of them is searching for a minimum skeleton according to Kruskal. He suggests that before the search is started, all edges should be arranged according to the weight in an ascending order. Then, the edges are used successively and they are added in such a manner so that a cycle does not occur. If a cycle occurs in the skeleton after the edge is added, the edge is left out and we proceed by the following edge. Based on the Prim-Jarnik's algorithm of searching for the minimum skeleton, the skeleton is constructed through a successive adding of new vertices to the skeleton. We start from an arbitrary vertex in the graph. In the graph, the distances between the pairs of nodes are defined. We search for such a sequence of nodes, the edges of which connect all nodes of the network and the sum of their distances is minimum. We will apply the Prim-Jarnik's algorithm. We will select an arbitrary vertex V. Thus, we obtain the component graph G1. The minimum-weight edge which is one of the edges outgoing from the vertex V, is chosen to a minimum skeleton. As a result, the component graph containing the vertex V, a minimum edge and another incidental vertex is formed. With finite graphs, the procedure is completed, while with a vertex graph after the steps. The resulting graph is the minimum skeleton of the graph G/Fig.3.

[FIGURE 3 OMITTED]

In the concrete case, the sum of the distances was 930.13. It is possible, however, that this sequence is not the only possibility. It may occur that the edges that can be added have an equal weight. It means that it is only the question of a selection.

However, it is important to emphasize that with the creation of the minimum skeleton it was taken to consideration that the given skeleton has to contain each node only once and, as far as possible, to avoid the tool returning to a certain node.

3. CONCLUSION

The essence of the solution lies in the analysis of secondary tool motions, when a cutting tool is displaced from the axis of one hole to the axis of the following hole. With the optimization of a cutting procedure applied to a large number of holes, the function that is being evaluated is time in which a tool is displaced. The holes axes are determined by the point in the plane by an ordered pair of numbers. The design of a cutting procedure will include the proposal of the shortest path to displace the cutting tool supposing that time spent on displacing is minimum. The contribution presents the possibility of graph theory application to a real technical problem considering some specific requirements of technical practice. The essence of a path optimization is that optimum cutting trajectories create the shortest path of a cutting tool. The solution is primarily concentrated on the analysis of secondary motions of a tool (Macurova, 2007). We generate a model representing individual nodes and their distances. The aim is to find the shortest path. Based on graph theory, it is possible to use one of the algorithms to search for the shortest path. The contribution contains an optimum path design based on graph theory applied to cutting holes in parts. The essence of a path optimization is that optimum cutting trajectories create the shortest path of a cutting tool /Fig. 3. Mathematical treatment of optimization of holes in parts cutting procedure is provided, we deal with a design of a cutting tool optimum path with cutting holes on a selected wall of a part. The shortest closed path has to be chosen of all cutting tool paths along which a cutting tool would pass, once through each hole. Passing of the tool through the hole refers to the tool entering the centre of the hole and leaving the hole after the hole completion. Many practical problems can be reformulated to the problems referring to a certain class of graphs. In this case, the holes are nodes and the weighted edges represent the distance between the individual nodes.

5. ACKNOWLEDGEMENTS

The paper is support with science project VEGA 1/4004/07.

6. REFERENCES

Hrubina K.; Jadlovska A. & Hrehova S. (2002). Methods and Tasks of the Operation Analysis Solution by Computer. Kosice 2002, 324 p., ISBN 80-88941-19-9

Macurova, A. (2007). Approximation of Functions in Experimental Methods. Forum Statistic Slovak. Number 2/2007. Year III. pp. 164-167, ISSN 1336-7420

Macura, D. (2003). Ordinary Differential Equations. 1. issue. Presov: FHPV PU, 79 p., ISBN 80-8068-175-9

Macura, D. (2005). Function of Multivariable 1. issue. Presov: FHPV PU, 56 pages, ISBN 80-8068-321-2

Hrubina K. & Jadlovska A. (2002). Optimal Control and Approximation of Variation Inequalities Cybernetics. The International Journal of Systems and Cybernetics. MCB University Press of England. Vol. 31, No 9/10, 2002, pp. 1401-1408, ISSN 036-492X