Geodesic
About a routing problem of the tool motion on sheet cutting
Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 2, pp. 278-294

Voir la notice de l'article provenant de la source Math-Net.Ru

For the routing problem of tool permutations under the thermal cutting of parts from sheet material realized on CNC machines, questions connected with constructing precise (optimal) and heuristic algorithms used on the stage of mathematical simulation of route elements under sequential megalopolises circuit are investigated. Cutting points and points of tool cut-off are items (cities) of the above-mentioned megalopolises. In each megalopolis, interior works are provided. These works are connected with motion to the equidistant curve of the cut contour of a part from the cutting point and (with cutting completed) with motion from the equidistant curve to the tool cut-off (we keep in mind a working run). The problem about the time-optimal process of cutting which is a special variant of the generalized courier problem is investigated (the problem of the routing on the megalopolises with precedence conditions). An optimal procedure based on the dynamic programming and an effective heuristic algorithm realized on a multicore computer are proposed. A dynamic programming based procedure uses a special extension of the main problem. This extension provides the replacement of admissibility by precedence with the admissibility by deletion (from the list of tasks). Precedence conditions are used for decreasing computational complexity: it excludes the building of the whole array of the Bellman function values (this function is replaced by the layers system).
Keywords: routing problem, preceding condition. 
@article{MAIS_2015_22_2_a9,
     author = {A. A. Petunin and A. G. Chentsov and P. A. Chentsov},
     title = {About a routing problem of the tool motion on sheet cutting},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {278--294},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2015_22_2_a9/}
}
TY  - JOUR
AU  - A. A. Petunin
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - About a routing problem of the tool motion on sheet cutting
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2015
SP  - 278
EP  - 294
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2015_22_2_a9/
LA  - ru
ID  - MAIS_2015_22_2_a9
ER  - 
%0 Journal Article
%A A. A. Petunin
%A A. G. Chentsov
%A P. A. Chentsov
%T About a routing problem of the tool motion on sheet cutting
%J Modelirovanie i analiz informacionnyh sistem
%D 2015
%P 278-294
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2015_22_2_a9/
%G ru
%F MAIS_2015_22_2_a9
A. A. Petunin; A. G. Chentsov; P. A. Chentsov. About a routing problem of the tool motion on sheet cutting. Modelirovanie i analiz informacionnyh sistem, Tome 22 (2015) no. 2, pp. 278-294. http://geodesic.mathdoc.fr/item/MAIS_2015_22_2_a9/