Алгоритм поиска подкритических путей на сетевых графиках

Цели. Информационная поддержка процессов планирования и управления проектами использует в качестве модели сетевые графики, помогающие в формировании структуры планируемых работ и расчете характеристик эффективности проекта. С целью оптимизации и выравнивания ресурсов, используемых в проектах, возникает необходимость нахождения на этих моделях не только критического пути максимальной взвешенной длины, но и ближайших к нему подкритических путей с меньшей по отношению к нему длиной. Цель работы – синтез и анализ алгоритма поиска k-кратчайших путей между вершинами входа и выхода сети, позволяющего идентифицировать вышеназванные подкритические пути.
Методы. Использованы положения теории графов и теории групп, а также метод динамического программирования.
Результаты. Разработан алгоритм поиска k-кратчайших путей на ориентированных графах без контуров с отношением строгого порядка. С использованием теории групп на графах были определены абстрактные элементы – p-контуры, между которыми была установлена многоуровневая структура отношений, позволившая реализовывать необходимый поиск путей. В рамках обоснования работоспособности построенного алгоритма доказана справедливость основных положений: во-первых, многоуровневая система отношений является исчерпывающей; во-вторых, не происходит потерь в окончательном решении в процессе работы алгоритма; в-третьих, пути, найденные в результате работы алгоритма, удовлетворяют основному требуемому соотношению между ними. Численно алгоритм реализован методом динамического программирования, который был расширен за счет использования дополнительного функционального соотношения, предполагающего наличие подоптимальных политик. Выводы. Проведенная серия вычислительных экспериментов подтвердила работоспособность и эффективность программно реализованного алгоритма. Выполненный анализ показал хорошие характеристики сходимости предложенного алгоритма в сравнении с алгоритмами данного класса, применяемыми к сетевым графикам. Это позволяет рекомендовать его к практическому использованию в информационных системах управления проектами.

1. Hagstrom J.N. Computing the probability distribution of project duration in a PERT network. Networks. 1990; 20(2):231–244. https://doi.org/10.1002/net.3230200208

2. Kamburowski J., Michael D.J., Stallmann M.F.M. Minimizing the complexity of an activity network. Networks. 2000;36(1):47–52. https://doi.org/10.1002/1097-0037(200008)36:1%3C47::AID-NET5%3E3.0.CO;2-Q

3. Bianco L., Caramia M. A new formulation of the resource-unconstrained project scheduling problem with generalized precedence relations to minimize the completion time. Networks. 2010;56(4):263–271. https://doi.org/10.1002/net.20388

4. Brennan M. PERT and CPM: a selected bibliography. Monticello, Ill.: Council of Planning Librarians, 1968. 11 p.

5. Alagheband A., Soukhakian M.A. An efficient algorithm for calculating the exact overall time distribution function of a project with uncertain task durations. Indian Journal of Science and Technology. 2012;5(9):3310–3316. https://doi.org/10.17485/ijst/2012/v5i9.20

6. Damci A., Polat G., Akin F.D., et al. Use of float consumption rate in resource leveling of construction projects. Front. Eng. Manag. 2022;9:135–147. https://doi.org/10.1007/s42524-020-0118-0

7. Willis R.J. Critical path analysis and resource constrained project scheduling – Theory and practice. Eur. J. Oper. Res. 1985;21(2):149–155. https://doi.org/10.1016/0377-2217(85)90026-8

8. Bowers J.A. Criticality in resource constrained networks. J. Oper. Res. Soc. 1995;46(1):80–91. https://doi.org/10.1057/jors.1995.9

9. Shtub A. The trade-off between the net present cost of a project and the probability to complete it on schedule. J. Oper. Manag. 1986;6(3–4):461–470. https://doi.org/10.1016/0272-6963(86)90017-3

10. Shtub A. The integration of CPM and material management in project management. Constr. Manag. Econ. 1988;6(4):261–272. https://doi.org/10.1080/01446198800000023

11. Ananthanarayanan P.S. Project Technology and Management. In: S. Seetharaman (Ed.). Treatise on Process Metallurgy. V. 3. Industrial Processes. Elsevier; 2014. P. 1145–1191. https://doi.org/10.1016/B978-0-08-096988-6.00038-9

12. García-Heredia D., Molina E., Laguna M., et al. A solution method for the shared resource-constrained multi-shortest path problem. Expert Systems with Applications. 2021;182:115193. https://doi.org/10.1016/j.eswa.2021.115193

13. Fulkerson D.R. Expected critical path lengths in PERT networks: Oper. Res. 1962;10(6):745–912. https://doi.org/10.1287/opre.10.6.808

14. Bellman R. On a routing problem. Quart. Appl. Math. 1958;16(1):87–90. https://doi.org/10.1090/qam/102435

15. Stern R., Goldenberg M., Saffidine A., et al. Heuristic search for one-to-many shortest path queries. Ann. Math. Artif. Intell. 2021;89:1175–1214. https://doi.org/10.1007/s10472-021-09775-x

16. Dreyfus S.E. An appraisal of some shortest-path algorithms. Operations Research. 1969;17(3):395–412. https://doi.org/10.1287/opre.17.3.395

17. Clarke S., Krikorian A., Rausan J. Computing the N best loopless paths in a network. J. Soc. Indust. Appl. Math. 1963;11(4):1096–1102. https://doi.org/10.1137/0111081

18. Pollack M. Solutions of the kth best route through a network – A review. J. Math. Anal. Appl. 1961;3(3): 547–559. https://doi.org/10.1016/0022-247X(61)90076-2

19. Shier D.R. Iterative methods for determining the k shortest paths in a network. Networks. 1976;6(3):205–229. https://doi.org/10.1002/net.3230060303

20. Shier D.R. On algorithms for finding the k shortest paths in a network. Networks. 1979;9(3):195–214. https://doi.org/10.1002/net.3230090303

21. Minieka E., Shier D.R. A note on an algebra for the k best routes in a network. IMA J. Appl. Math. 1973;11(2): 145–149. https://doi.org/10.1093/imamat/11.2.145

22. Eppstein D. Finding the k shortest paths. SIAM J. Comput. 1999;28(2):652–673. https://doi.org/10.1137/S0097539795290477

23. Yen J.Y. Finding the K shortest loopless paths in a network. Manag. Sci. 1971;17(11–Theory Series):712–716. Available from URL: http://www.jstor.org/stable/2629312

24. Hershberger J., Maxel M., Suri S. Finding the k shortest simple paths: A new algorithm and its implementation. ACM Trans. Algor. 2007;3(4): Art. 45(19 p.) https://doi.org/10.1145/1290672.1290682

25. Chen B.Y., Chen X.-W., Chen H.-P., et al. A fast algorithm for finding K shortest paths using generalized spur path reuse technique. Transactions in GIS. 2021;25(1): 516–533. https://doi.org/10.1111/tgis.12699

26. Hu X.-B., Zhang C., Zhang G.-P., et al. Finding the k shortest paths by ripple-spreading algorithms. Eng. Appl. Artif. Intell. 2020;87:Art.103229. https://doi.org/10.1016/j.engappai.2019.08.023

27. Hamed A.Y. A genetic algorithm for finding the k shortest paths in a network. Egypt. Inform. J. 2010;11(2):75–79. https://doi.org/10.1016/j.eij.2010.10.004

28. Hu X.-B., Zhou J., Li H., et al. Finding the k shortest paths for co-evolutionary path optimization. In: IEEE Symposium Series on Computational Intelligence. November 18–21, 2018; Bangalore, India. P. 1906–1912. https://doi.org/10.1109/SSCI.2018.8628928

29. Liu G., Qiu Z., Chen W. An iterative algorithm for single-pair K shortest paths computation. WSEAS Transactions on Information Science and Applications. 2015;12(Art. 30):305–314. Available from URL: https://wseas.org/wseas/cms.action?id=10185

30. Guo J., Jia L. A new algorithm for finding the K shortest paths in a time-schedule network with constraints on arcs. J. Algorithms Comput. Technol. 2017;11(2):170–177. https://doi.org/10.1177/1748301816680470

31. Xu W., He S., Song R., et al. Finding the K shortest paths in a schedule-based transit network. Comput. Oper. Res. 2012;39(8):1812–1826. https://doi.org/10.1016/j.cor.2010.02.005

32. Jin W., Chen S., Jiang H. Finding the K shortest paths in a time-schedule network with constraints on arcs. Comput. Oper. Res. 2013;40(12):2975–2982. https://doi.org/10.1016/j.cor.2013.07.005

33. Kaufmann A., Debazeille G. La méthode du chemin critique. Paris: Dunod; 1964. 170 p.

34. Bellman R., Kalaba R. On kth best policies. J. Soc. Ind. Appl. Math. 1960;8(4)582–588. Available from URL: https://www.jstor.org/stable/2099049

35. Shier D.R. Computational Experience with an algorithm for finding the k shortest paths in a network. J. Res. Natl. Bureau Stand. 1974;78B(3)139–165. https://doi.org/10.6028/JRES.078B.020