Abstract:
The problem of sequentially traversing megacities with precedence conditions and cost functions that allow dependence on the task list is considered. It is assumed that the entire set of tasks is decomposed into a sum of non-empty subsets (groups); it is necessary to sequentially solve partial problems of visiting megacities in each of the groups. The order of visiting the groups themselves is specified a priori. It is assumed that the precedence conditions of the overall problem are localized in the aforementioned groups. The formulation is oriented towards the engineering problem of tool control during shape sheet metal cutting of parts by zones on CNC machines. The main method used is dynamic programming under decomposition conditions, where optimal procedures are implemented for each of the partial problems separately, after which a special gluing of the obtained solutions is performed. This resolves the issue of decomposing the original “large” problem into a system of partial problems of moderate dimension. Based on theoretical constructs, a workable algorithm is constructed and implemented on a PC. Solutions to model examples are presented.
Fulltext:
PDF file (1078 kB)