Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki: Year: Volume: Issue: Page: Find

 Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2019, Volume 29, Issue 3, Pages 363–381 (Mi vuu689)

MATHEMATICS

On the question of the optimization of permutations in the problem with dynamic constraints

A. G. Chentsovab, A. A. Chentsovb

a Ural Federal University, ul. Mira, 19, Yekaterinburg, 620002, Russia
b N. N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620219, Russia

Abstract: The “additive” problem of sequentially visiting megalopolises (nonempty finite sets) is considered; some tasks are executed as the megalopolises are visited. Permutations and operations are evaluated by cost functions that admit a dependence on the list of tasks. There are restrictions of different types, which include precedence conditions used in the “positive direction” (to reduce the complexity of calculations). In addition, this conception involves dynamical restrictions that are formed in the process of task execution. This conception is oriented to engineering applications associated with sheet cutting on CNC machines. An approach to constructing optimal solutions based on a nonstandard version of dynamic programming (DP) is investigated. This approach takes into account restrictions of different types, including dynamic constraints which naturally arise in sheet cutting applications (in particular, it takes into account heat tolerances related to diffusion of heat in the vicinities of tie-in points). In this regard, a combination of “direct” interdictions of movements and cutting and a system of penalties is allowed; in the latter case, cost functions with a dependence on the list of tasks arise. The variant of DP that is used allows one to optimize the selection of a starting point, the route, which is identified with a permutation of the indexes, and the trajectory corresponding to the above-mentioned route. An economical variant of DP is used at the stage of construction of the Bellman function. This conception allows avoiding calculation of the whole array of values of this function; instead, only the system of its layers is defined (in the case of using the precedence conditions, which are typical of the problem of sheet cutting, this conception results in a considerable reduction of calculation costs). An optimal DP-based algorithm is constructed and realized on PC, and the results of the computational experiment are presented.

Keywords: route, path, precedence conditions.

 Funding Agency Grant Number Russian Foundation for Basic Research 18-01-00410_à The research was funded by the Russian Foundation for Basic Research (project no. 18-01-00410).

DOI: https://doi.org/10.20537/vm190307

Full text: PDF file (798 kB)
Full text: http://vm.udsu.ru/.../2019-3-7
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.6
MSC: 05A05, 97N70, 97N80

Citation: A. G. Chentsov, A. A. Chentsov, “On the question of the optimization of permutations in the problem with dynamic constraints”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 29:3 (2019), 363–381

Citation in format AMSBIB
\Bibitem{CheChe19} \by A.~G.~Chentsov, A.~A.~Chentsov \paper On the question of the optimization of permutations in the problem with dynamic constraints \jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki \yr 2019 \vol 29 \issue 3 \pages 363--381 \mathnet{http://mi.mathnet.ru/vuu689} \crossref{https://doi.org/10.20537/vm190307}