Geodesic
An extremal two-stage routing problem and procedures based on dynamic programming
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 215-248

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

We study a routing problem in which the set of tasks is represented as the union of two disjoint subsets. The tasks from the first subset must be completed before the execution of the tasks from the second subset. Each task is associated with a visit to a megalopolis (a nonempty finite set) in order to perform some work. The choice of the order in which the tasks are performed is subject to precedence conditions, which are localized for the mentioned two subsets of the total set of tasks. The cost functions used in the formation of the additive criterion may involve a dependence on the list of tasks. To construct a solution, a two-stage procedure based on dynamic programming is proposed. An optimal algorithm is constructed and implemented as a computer program. A model problem about shaped sheet cutting on CNC machines is solved.
Keywords: dynamic programming, precedence conditions.
Mots-clés : route 
@article{TIMM_2022_28_2_a17,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {An extremal two-stage routing problem and procedures based on dynamic programming},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {215--248},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a17/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - An extremal two-stage routing problem and procedures based on dynamic programming
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2022
SP  - 215
EP  - 248
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a17/
LA  - ru
ID  - TIMM_2022_28_2_a17
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T An extremal two-stage routing problem and procedures based on dynamic programming
%J Trudy Instituta matematiki i mehaniki
%D 2022
%P 215-248
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a17/
%G ru
%F TIMM_2022_28_2_a17
A. G. Chentsov; P. A. Chentsov. An extremal two-stage routing problem and procedures based on dynamic programming. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 215-248. http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a17/