AN EXTREMAL TWO-STAGE ROUTING PROBLEM AND PROCEDURES BASED ON DYNAMIC PROGRAMMING

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. © Krasovskii Institute of Mathematics and Mechanics.All rights reserved.