Developing Systems

On an effective solution of the Bellman — Johnson problem on a tree-like network

M. Sh. Levin, E. V. Levner

Moscow

Abstract: The paper is concerned with the Bellman — Johnson problem on a tree-like network (in the case of two machines). The view is refuted that no algorithm with exponential labor consumption estimate exists for it. An effective solution algorithm is proposed for a labor consumption of $O(n \log n)$ where $n$ is the number of activities.

UDC: 519.14


Received: 19.12.1977

 English version: Automation and Remote Control, 1979, 39:10, 1497–1504

Bibliographic databases:

• 
•