This article is cited in 8 papers

Dynamic programming in a generalized courier problem with inner tasks: elements of a parallel structure

A. M. Grigoriev, E. E. Ivanko, A. G. Chentsov

Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg

Abstract: In the article we concern the questions connected with the realization of a dynamic programming method in problems of consequent visiting of megapolises. The realization is complicated by precedence conditions and works inside the megapolises. The scheme for constructing a reduced (partial) array of Bellman function values using parallel computing without loss in accuracy is suggested. This procedure is realized on a multiprocessor computing system; parallelizing is performed at the stage of Bellman function layers construction.

Keywords: route, trace, precedence condition.

UDC: 519.157

Received: 28.02.2011