Результаты исследований: Вклад в журнал › Статья › Рецензирование
Результаты исследований: Вклад в журнал › Статья › Рецензирование
}
TY - JOUR
T1 - Two-Stage Dynamic Programming in the Routing Problem with Decomposition
AU - Chentsov, A. G.
AU - Chentsov, P. A.
PY - 2023/5/1
Y1 - 2023/5/1
N2 - This paper considers an optimal movement routing problem with constraints. One such constraint is due to decomposing the original problem into a preliminary subproblem and a final subproblem; the tasks related to the preliminary problem must be executed before the tasks of the final subproblem begin. In particular, this condition may arise in the tool control problem for thermal cutting machines with computer numerical control (CNC): if there are long parts among workpieces, the cutting process near a narrow material boundary should start with these workpieces since such parts are subject to thermal deformations, which may potentially cause rejects. The problem statement under consideration involves two zones for part processing. The aggregate routing process in the original problem includes a starting point, a route (a permutation of indices), and a particular track consistent with the route and the starting point. Each of the subproblems has specific precedence conditions, and the travel cost functions forming the additive criterion may depend on the list of pending tasks. A special two-stage procedure is introduced to apply dynamic programming as a solution method. The structure of the optimal solution is established and an algorithm based on this structure is developed. The algorithm is implemented on a personal computer and a computational experiment is carried out.
AB - This paper considers an optimal movement routing problem with constraints. One such constraint is due to decomposing the original problem into a preliminary subproblem and a final subproblem; the tasks related to the preliminary problem must be executed before the tasks of the final subproblem begin. In particular, this condition may arise in the tool control problem for thermal cutting machines with computer numerical control (CNC): if there are long parts among workpieces, the cutting process near a narrow material boundary should start with these workpieces since such parts are subject to thermal deformations, which may potentially cause rejects. The problem statement under consideration involves two zones for part processing. The aggregate routing process in the original problem includes a starting point, a route (a permutation of indices), and a particular track consistent with the route and the starting point. Each of the subproblems has specific precedence conditions, and the travel cost functions forming the additive criterion may depend on the list of pending tasks. A special two-stage procedure is introduced to apply dynamic programming as a solution method. The structure of the optimal solution is established and an algorithm based on this structure is developed. The algorithm is implemented on a personal computer and a computational experiment is carried out.
UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=85171617413
UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=001067925500007
U2 - 10.1134/S0005117923050053
DO - 10.1134/S0005117923050053
M3 - Article
VL - 84
SP - 543
EP - 563
JO - Automation and Remote Control
JF - Automation and Remote Control
SN - 0005-1179
IS - 5
ER -
ID: 45142562