|
This article is cited in 4 scientific papers (total in 4 papers)
An extremal two-stage routing problem and procedures based on dynamic programming
A. G. Chentsovab, P. A. Chentsova a N.N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg
Abstract:
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, route, precedence conditions.
Received: 04.04.2022 Revised: 26.04.2022 Accepted: 30.04.2022
Citation:
A. G. Chentsov, P. A. Chentsov, “An extremal two-stage routing problem and procedures based on dynamic programming”, Trudy Inst. Mat. i Mekh. UrO RAN, 28, no. 2, 2022, 215–248
Linking options:
https://www.mathnet.ru/eng/timm1917 https://www.mathnet.ru/eng/timm/v28/i2/p215
|
Statistics & downloads: |
Abstract page: | 101 | Full-text PDF : | 17 | References: | 13 | First page: | 4 |
|