MATRIX METHOD FOR FINDING THE PATHS ON WEIGHTED ORIENTED GRAPHS IN THE TASKS OF PORT NET OPERATIONAL PLANNING

Network planning, or network analysis, is a class of application methods for project management that provides planning, analysis of deadlines (both early and late), risk of project failure or individual parts of the project. These methods allow you to link the performance of different works and processes over time, to make an operational schedule of the project, to get a forecast of the total duration of the project. In the modern practice of designing, building and managing seaports, network planning represents the most sought-after toolkit for decision makers. Network planning methods are conditionally divided into deterministic (Gant’s diagrams, rigid and with additional time-lag, critical path method, etc.) and probabilistic. Latter, in turn, are divided into non-alternative (method of statistical tests or the Monte Carlo method, the method of evaluating and revising PERT plans) and alternative (GERT graphic assessment method).In many applications, the basis of the used method is to find a path on the graph. Multiple repetition of experiments, characteristic of the most effective probabilistic methods, imposes high demands to reduce the computational laboriousness of the used algorithms. In addition, the different nature of cause-and-effect relations between objects of network models leads to the formation of such a structure depicting graph processes, which do not allow the use of most known algorithms. A matrix algorithm for finding paths on weighted oriented graphs, characterized by low computational laboriousness, simplicity and visibility, and allowing different types of cause-effect relations between events, is described in the paper. The proposed algorithm is effective in terms of the set tasks, and its implementation is almost no different from the pseudo-code used to describe it.This makes it easy to implement, easy to debug and verify code, and easy to embed the algorithm in various network planning applications. One of these tasks is to find critical paths in the context of the time parameters of all works (operations) linking the tops of events.

network planning, graph search, simulation techniques

1. Кудрявцев Е. М. Project 2003. Сетевое планирование и управление проектами / Е. М. Кудрявцев. - М.: ДМК Пресс, 2014. - 240 c.

2. Woolf M. B. CPM Mechanics: The Critical Path Method of Modeling Project Execution Strategy / M.B. Woolf. - ICS-Publications, 2012. - 480 p.

3. KelleyJrJ.E.Critical-pathplanningandscheduling/J.E.KelleyJr,M.R.Walker//IRE-AIEE-ACM‘59(Eastern).- New York, NY, United States: Association for Computing Machinery, 1959. - С. 160-173. DOI: 10.1145/1460299.1460318.

4. Burgelman J. Computing project makespan distributions: Markovian PERT networks revisited / J. Burgelman, M. Vanhoucke // Computers & Operations Research. - 2019. - Vol. 103. - Pp. 123-133. DOI: 10.1016/ j.cor.2018.10.017.

5. Newell M. The Project Management Question and Answer Book / M. Newell, M. Grashina. - American Management Association, 2003. -98 p.

6. Washburn A. Military operations research / A. Washburn // Handbooks in Operations Research and Management Science. - 1994. - Vol. 6. - Pp. 67-106. DOI: 10.1016/S0927-0507(05)80085-4.

7. Thayer H. Management of the Hanford Engineer Works in World War II: How the Corps, DuPont and the Metallurgical Laboratory fast tracked the original plutonium works / H. Thayer. - ASCE Press, 1996. - 224 p. DOI: 10.1061/9780784401606.

8. Ali I. Isolating critical flow path and algorithmic partitioning of the AND/OR mobile workflow graph / I. Ali, S. Bagchi // Future Generation Computer Systems. - 2020. - Vol. 103. - Pp. 28-43. DOI: 10.1016/j.future.2019.09.059.

9. Burgelman J. Computing project makespan distributions: Markovian PERT networks revisited / J. Burgelman, Vanhoucke // Computers & Operations Research. - 2019. - Vol. 103. - Pp. 123-133. DOI: 10.1016/j.cor.2018.10.017.

10. Baker S. L. Critical Path Method (CPM) / S. L. Baker. - University of South Carolina, Dept. of Health Services Policy and Management Courses and Curricula, HSPM J716, 2004.

11. Bellman R. On a routing problem / R. Bellman //Quarterly of applied mathematics. - 1958. - Vol. 16. - Is. 1. - Pp. 87-90. DOI: 10.1090/qam/102435.

12. Ford Jr. L. R. Flows in Networks / L. R. Ford Jr., D. R. Fulkerson. - Princeton University Press, 1962. - 212 p.

13. Dijkstra E. W. A note on two problems in connexion with graphs / E. W. Dijkstra // Numerische mathematik. - 1959. - Vol. 1. - Pp. 269-271. DOI: 10.1007/BF01386390.

14. Кормен Т. Х. Алгоритмы: построение и анализ / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн. - 2-е изд. - М.: «Вильямс», 2006. - 1296 с.

15. Левитин А. В. Жадные методы: Алгоритм Дейкстры / А. В. Левитин // Алгоритмы. Введение в разработку и анализ. - М.: Вильямс, 2006. - С. 189-195.