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(n2), 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.
Acknowledgments. This work was supported in part by the Russian Science Foundation, project no. 22-71-10131.
An Optimal Allocation Algorithm for Reentrant Resources on Network Graphs