Archive of Issues
Russia Yekaterinburg
Section  Mathematics 
Title  The Bellmann insertions in the route problem with constraints and complicated cost functions 
Author(s)  Chentsov A.G.^{ab} 
Affiliations  Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences^{a}, Ural Federal University^{b} 
Abstract  The problem of sequential circuit of megalopolises with precedence conditions and cost functions that permit a dependence on tasks list is considered. Such problems can arise, in particular, in atomic energetic while investigating the questions connected with lowering of workers irradiation under permutations in radiative fields for realization of services connected with division of radiating elements. Another application of the developed methods is connected with important engineering problem of routing the instrument movements under the leaf cutting on numerically controlled machines. This problem has sufficiently large dimensionality and many precedence conditions: if a detail has not only exterior but at least one interior contours (the simplest example is a washer) then the interior contours must be cut before the cutting of exterior contour (finite sets located near corresponding contours are used as megalopolises). In this case the possible dependence of cost functions on tasks list can reflect various technological conditions. We note that perceptible dimensionality characterized by all contours in total leads to necessity of heuristics employment. Therefore, questions concerning at least local improvement of solutions appear sufficiently important for the investigation. The basic attention in the article is devoted to the construction of optimizing insertions in complicated conditions: it is required to reduce the fragment of precedence conditions and to transform the corresponding cost functions; in the last case, it is important to preserve the dependence on tasks list. Both abovementioned moments are taken into account under the procedure construction having the sense of algorithm on functional level. 
Keywords  route, trace, precedence conditions 
UDC  519.6 
MSC  28A33 
DOI  10.20537/vm140410 
Received  15 November 2014 
Language  Russian 
Citation  Chentsov A.G. The Bellmann insertions in the route problem with constraints and complicated cost functions, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, issue 4, pp. 122141. 
References 

Full text 