CASPIAN JOURNAL
MANAGEMENT AND HIGH TECHNOLOGIES
Solution of the problem of placement laded segments on array permutations "bubble"
 |
Read | Dvoryankin A. M. Solution of the problem of placement laded segments on array permutations "bubble" // Caspian journal : management and high technologies. — 2018. — №4. — pp. 39-45. |
/39-45.jpg)
Dvoryankin A. M. - Doct. Sci. (Engineering), Professor, Volgograd State Technical University, 28 Lenin Ave., Volgograd, 400005, Russian Federation, dvam1@mail.ru
The article provides a description of the basic concepts: a loaded segment, the connection of segments, the definition of order on a set of segments, a formula for calculating the center of gravity of the connection of segments. The problem of locating a set of segments loaded with a concentrated force is formulated. The criterion of optimal placement is the minimum deviation of the center of gravity from the given one. The task is NP complete. The brute-force algorithm for solving it has the time complexity O ( n !), Where n is the number of segments to be placed. Therefore, the search for efficient, approximate algorithms is an urgent task. The definition of the “bubble” permutation array is given. An algorithm is proposed for generating transpositions, with the help of which it is possible to form permutations of this array. The theorem on non-decreasing of the position of the center of gravity of the connection of segments on these permutations is proved. A theorem on calculating the increment of the center of gravity position on adjacent permutations is proved. On the basis of these theorems, an algorithm is constructed for the approximate solution of the problem of allocating segments, the time complexity of which is O ( n ). The concept of accuracy of the solution is given - deviation of the center of gravity from the target position. A formula is given that determines the maximum possible deviation for given segments. Examples of the algorithm are given. The results of the work can be used to plan the optimal placement of cargo on the vehicle.
Key words: нагруженный отрезок, соединение отрезков, размещение отрезков, центр тяжести, перестановка, транспозиция, массив «пузырек», loaded segment, connection of segments, placement of segments, center of gravity, permutation, transposition, “bubble” array