PSI - Issue 40

110 A.G. Chentsov et al. / Procedia Structural Integrity 40 (2022) 105–111 Chentsov A.G., Chentsov P.A./ Structural Integrity Procedia 00 (2022) 000 – 000 of all possible finishing points. We use (24) as the set of all starting points for ℳ 2 -problem. This problem is being solved by optimal DP algorithm [11]: essential task lists are constructed; later, with their application, layers of position space are defined; finally, the layers v 0 ∗ , v 1 ∗ , . . . , v n ∗ − N of the corresponding Bellman function are determined. The function v n ∗ − N is defined on the set {(x, 1̅̅,̅ ̅̅̅−̅̅̅N̅ ) : x ∈ X 00 } of position space. By this function the terminal component of additive criterion for ℳ 1 -problem is constructed. Then, we can introduce the corresponding additive criterion for ℳ 1 -problem. Later we solve ℳ 1 -problem with additive criterion for which terminal component is defined with employment of v n ∗ − N . In addition, we determine essential task lists and, with employment of these lists, construct layers of position space. For these layers, we realize construction of Bellman function layers: 0ℶ , 1ℶ , . . . , ℶ . In addition, ℶ is defined on the set {( x, ̅1̅,̅̅N̅ ) : x ∈ X 0 }; values of ℶ are corresponding extremums for ℳ 1 -problems under starting point fixation. After minimization of ℶ values, we determine and optimal starting point x 0 ∈ X 0 . Later, in direct time, we construct 10 ∈ 1 and trajectory ( t (1) ) ∈ ̅0̅̅,N̅̅ for ℳ 1 -problem ( ( t (1) ) ∈ ̅0̅̅,N̅̅ coordinated with 10 ) which are optimal in ℳ 1 -problem. In addition, N (1) ∈ 10 ( ) realizes the value v n ∗ − N (pr 2 ( N (1) )) ∈ ℝ + Ǥ ‡ —•‡ pr 2 ( N (1) ) as starting point for ℳ 2 – problem. Then, for ℳ 2 – problem, we construct the route 20 ∈ 2 ƒ† –”ƒŒ‡…–‘”› ( t (2) ) ∈ ̅0̅,̅ ̅̅−̅̅N̅̅ ) …‘‘”†‹ƒ–‡† ™‹–Š 20 ™Š‹…Š ƒ”‡ ‘’–‹ƒŽ ‹ ℳ 2 – problem with starting point pr 2 ( N (1) ) . Namely, the pair ( 20 , ( t (2) ) ∈ ̅0̅,̅ ̅̅−̅̅N̅̅ ) realizes the value v n ∗ − N (pr 2 ( N (1) )) as the sum of the corresponding values of cost functions of ℳ 2 -problem. Now, for solution of complete problem, we realize coalescence of routes and trajectories: we introduce 00 ≜ 10 ♦ 20 and ( t 00 ) ∈ ̅0̅,̅ ̅ ∈ 00 ሾ x 0 ሿ „› –Š‡ ”—Ž‡ ( 00 ≜ (1) ∀ ∈ ̅0̅,̅̅ ̅ ) & ( 00 ≜ ( − 2) ∀ ∈ ̅ ̅̅̅+̅̅̅1̅̅, ̅ ̅ ). Then, ( α 00 , ( t 00 ) ∈ ̅0̅,̅ ̅ , x 0 ) ∈ SOL . 3. Computing experiment Algorithm of Section 2 was implemented as a standard program for the problem of the instrument control under sheet cutting on CNC machines (solution on a personal computer was considered). In above-mentioned concrete problem, cost functions were determined in correspondence with [10]. Precedence conditions were given and constraints were connected with heat removal under thermal cutting; the last constraints, we call thermal tolerances. The list dependency of cost functions was emerged through the use of fines for violation of thermal tolerances. Every megalopolis arose under sampling of countor equidistant with selection of tie-in-points and switch off points. These two types of points are a cluster in ordered pair set. Every relation was realized in the form of the set of such ordered pairs connected with . Still megalopolises set is divided in the amount of two subsets corresponding to two zones in the cutting mode. For every of zones, own precedence conditions are defined by the corresponding address pairs of indexes. The task list dependence not divided into zones; this corresponds to nature cost functions in complete problem. Here, within the meaning of the problem the dependence on completed assignments arises. But, by unessential transformation this dependence can be reduced to dependence on assignments which still not completed. The last dependence corresponds to our theoretical construction. It was supposed that n = 50, N = 25, and as a corollary | ℳ 1 | = | ℳ 2 | = 25. The number of address pairs formative 1 is 14; analogous number for 2 is 16. The criterion was defined as cumulative time for fulfilment of all tasks; this rule is used under satisfaction of all thermal tolerances. Under violation of these tolerances, fines are imposed (see description of computing experiment in [10]). These fines increase criterion value. As a result, extremum was found (concretely 113.252); in addition, all constraints were completed (without accounting of fines, the corresponding result is 113.252 also). The computing time is 5 minutes 06.395 seconds. 6

References Gutin G., Punnen A. P. The traveling salesman problem and its variations, Springer, Berlin, 2002, 850 pp.

Made with FlippingBook - professional solution for displaying marketing and sales documents online