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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Received: 28.06.2019

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}


Linking options:
  • http://mi.mathnet.ru/eng/vuu689
  • http://mi.mathnet.ru/eng/vuu/v29/i3/p363

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  •   . . .
    Number of views:
    This page:118
    Full text:78
    References:4

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021