PSI - Issue 40

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

106

2

nuclear power in connection with minimization of dose load under dismantling of radiation hazardous objects and problems connected with sheet cutting on CNC machines; see [6]. The general approach of [7] allowed to construct optimal solution for above-mentioned informative problems based on the use of the dynamic programming (DP) apparatus in realization dating back to article [8] (in discrete optimization, the scheme of [9] is used more often). But, in high dimension problems, the realization of algorithms based DP is difficult; in this connection, for given problems, optimizing constructions using insertions and multi-insertions were proposed. ([10, 11]) In the present article, we are oriented to constructions [6, 7, 10] and apply procedures [11, 12] where DP used under conditions of starting point optimization. We consider the setting for which constraint connected with binary partition of all set of tasks is given (development of given design is possible for the case, when partition in the sum of larger number of sets is used; but, now, in theoretical constructions, we limit ourselves to the case of binary partition). Specifics of the problem are as follows: at first, all tasks of the first subset should be fulfilled and only after that it is possible to proceed with fulfilment tasks of the second subset. This situation can arire under sheet cutting on CNC machines in the case when two zones are selected (a variant when it is selected more than two zones is possible also) and cutting process is fulfilled under this requirement. Of course, the application of supposed algorithm without given requirement is possible also; in this case, we obtain a heuristic for the solution of the routing problem with large dimension. Of course, in the last case, we obtain suboptimal (generally speaking) result. The basic of considered construction is a non-standard two-stage variant of DP (we recall that on this basis multi stage variant can be constructed also). In the following section, we discuss algorithmic variant of given procedure; we keep in mind the outline of the logical structure of algorithm at the functional level. The important peculiarity of the used DP scheme is its universality from the starting point; this distinguishes given scheme from [9] essentially. 1. Informative setting of problem. In this article, we hold informative presentation of our algorithm at the functional level. We fix a nonempty set X of arbitrary nature, finite not an empty subset X 0 of it, natural number n, n ≥ 2, finite sets M 1 , ... , M n , each of which is a subset of X, and nonempty relations 1 ,..., for which 1 ⊂ M 1 × M 1 , … , ⊂ M n × M n . (1) Later, we consider the case when n is quity a large number. In addition, ̅1̅̅, ̅ ̅ ≜ { k ∈ N | k ≤ n } is the interval of the positive integers N ≜ {1; 2; . . . } ( ≜ is the equality by definition), and N 0 ≜ {0} ∪ N . We suppose that (M j ∩ 0 = ∅ ∀ j ∈ 1̅̅,̅̅ ̅ ) & (M p ∩ M q = ∅ ∀ p ∈ 1̅̅,̅̅ ̅ ∀ q ∈ ̅1̅,̅̅ ̅ \ {p}). (2) Supposing that ℳ ≜ { M i : i ∈ 1̅̅,̅̅ ̅ } (the family of megalopolises); under N ∈ 2̅̅,̅ ̅̅̅−̅̅̅ ̅ ≜ {k ∈ N | (2 ≤ k)&(k ≤ n − 2)} (later, without additional clarifications, we consider intervals of ℕ and ℕ 0 of the above-mentioned type), we consider ℳ 1 ≜ {M i : i ∈ ̅1̅,̅̅ ̅ }, ℳ 2 ≜ ℳ \ ℳ 1 = {M i : i ∈ ̅ ̅̅̅+̅̅̅1̅̅, ̅ ̅ }. Suppose that M ( j ) ≜ M N + j ∀ j ∈ ̅1̅,̅ ̅̅̅−̅̅̅N̅ . Then M (1) , ..., M ( n − N ) are nonempty finite set and ℳ 2 = { M ( j ) : j ∈ ̅1̅,̅ ̅̅̅−̅̅̅N̅ }. Moreover, let ( ) ≜ + under j ∈ ̅1̅,̅ ̅̅̅−̅̅̅N̅ . So, ℳ 1 forms the first zone and ℳ 2 forms the second zone. For problems connected with visitings of zones, we introduce two types of precedence conditions; for this, we fix two sets K 1 and K 2 , K 1 ⊂ 1̅̅,̅̅ ̅ × ̅1̅,̅̅ ̅ , K 2 ⊂ 1̅̅,̅̅ ̅̅−̅̅̅ ̅̅ × ̅1̅,̅̅ ̅̅−̅̅̅̅ ̅ . (3)