RUS  ENG
Full version
JOURNALS // Problemy Upravleniya // Archive

Probl. Upr., 2024 Issue 2, Pages 23–29 (Mi pu1348)

Mathematical problems in management

An optimal allocation algorithm for reentrant resources on network graphs

O. A. Kosorukovab, D. V. Lemtyuzhnikovacd

a Moscow State University, Moscow, Russia
b The Presidential Academy (RANEPA), Moscow, Russia
c Moscow Aviation Institute (National Research University), Moscow, Russia
d Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia

Abstract: This paper considers the problem of allocating reentrant resources when performing a set of interdependent works that are represented by a network graph. By assumption, the work completion time linearly depends on the resource amount used. We justify a solution algorithm in the case of a set of works with a predetermined sequence of events in the network graph. Also, we propose an algorithm for reducing the general problem to an auxiliary one with ordered event times and an algorithm for constructing an optimal solution of the original problem. The convergence of this algorithm is ensured by finite iterations at each stage. The overall computational complexity of the algorithm can be estimated as $O(n^2)$, where $n$ denotes the number of vertices in the original network graph. It seems promising to apply this algorithm for planning the sets of interdependent works using reentrant resources.

Keywords: network graph, unordered events, event merging, event splitting, pathfinding.

UDC: 519.863

Received: 03.02.2024
Revised: 19.03.2024
Accepted: 03.04.2024

DOI: 10.25728/pu.2024.2.2


 English version:
Control Sciences, 2024:2, 17–22


© Steklov Math. Inst. of RAS, 2025