General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Model. Anal. Inform. Sist.:

Personal entry:
Save password
Forgotten password?

Model. Anal. Inform. Sist., 2015, Volume 22, Number 2, Pages 278–294 (Mi mais441)  

This article is cited in 3 scientific papers (total in 3 papers)

About a routing problem of the tool motion on sheet cutting

A. A. Petunina, A. G. Chentsovab, P. A. Chentsovba

a Ural Federal University, Mira str., 19, Ekaterinburg, 620002, Russia
b N. N. Krasovskii Institute of Mathematics and Mechanics, Sofia Kovalevskaya str., 16, Ekaterinburg, 620990, Russia

Abstract: 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.

Full text: PDF file (461 kB)
References: PDF file   HTML file

Bibliographic databases:
UDC: 519.6
Received: 16.11.2013

Citation: A. A. Petunin, A. G. Chentsov, P. A. Chentsov, “About a routing problem of the tool motion on sheet cutting”, Model. Anal. Inform. Sist., 22:2 (2015), 278–294

Citation in format AMSBIB
\by A.~A.~Petunin, A.~G.~Chentsov, P.~A.~Chentsov
\paper About a routing problem of the tool motion on sheet cutting
\jour Model. Anal. Inform. Sist.
\yr 2015
\vol 22
\issue 2
\pages 278--294

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. A. Chentsov, A. G. Chentsov, “Obobschennaya model kurera s dopolnitelnymi ogranicheniyami”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 9:1 (2016), 46–58  mathnet  crossref  elib
    2. A. G. Chentsov, P. A. Chentsov, “Routing under constraints: problem of visit to megalopolises”, Autom. Remote Control, 77:11 (2016), 1957–1974  mathnet  crossref  isi  elib  elib
    3. A. G. Chentsov, A. A. Chentsov, “A discrete-continuous routing problem with precedence conditions”, Proc. Steklov Inst. Math. (Suppl.), 300, suppl. 1 (2018), 56–71  mathnet  crossref  crossref  isi  elib
  • Моделирование и анализ информационных систем
    Number of views:
    This page:233
    Full text:69

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019