mireabulletinRussian Technological JournalRussian Technological Journal2782-32102500-316XRTU MIREA10.32362/2500-316X-2023-11-1-60-69mireabulletin-615Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGАлгоритм поиска подкритических путей на сетевых графикахAlgorithm for finding subcritical paths on network diagramshttps://orcid.org/0000-0003-2853-6184АнфёровМ. А.АnfyorovM. A.

Анфёров Михаил Анисимович, д.т.н., профессор, профессор кафедры «Предметно-ориентированные информационные системы» Института кибербезопасности и цифровых технологий

119454, Москва, пр-т Вернадского, д. 78

Mikhail A. Аnfyorov, Dr. Sci. (Eng.), Professor, Domain-Specific Information Systems Department, Institute of Cybersecurity and Digital Technologies

78, Vernadskogo pr., Moscow, 119454

anfyorov@inbox.ruМИРЭА – Российский технологический университетРоссияMIREA – Russian Technological UniversityRussian Federation2023030220231116069Copyright © Анфёров М.А., 20232023Анфёров М.А.Аnfyorov M.A.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.rtj-mirea.ru/jour/article/view/615

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

Objectives

Objectives. Network diagrams are used as an information support element in planning and project management processes for structuring planned work and calculating project efficiency characteristics. In order to optimize and balance resources used in projects, it becomes necessary to locate in these models not only the critical path of the maximum weighted length, but also the subcritical paths closest to it having a shorter length in relation to it. The aim of the work is to synthesize and analyze an algorithm for finding k-shortest paths between the input and output network vertices, on which basis the above-mentioned subcritical paths can be identified.

Methods

Methods. The provisions of graph theory and group theory, as well as the method of dynamic programming, were used.

Results

Results. An algorithm for finding k-shortest paths in contourless directed graphs having a strict order relation was developed. Abstract elements were defined according to group theory in graphs as p-contours, between which a multilevel structure of relations for implementing the necessary search of paths was then established. For substantiating the efficiency of the constructed algorithm, the validity of the main provisions was demonstrated as follows: firstly, the multilevel system of relations is exhaustive; secondly, there is no loss in the final solution during the operation of the algorithm; thirdly, the paths obtained as a result of the work of the algorithm satisfy the main required relation between them. Numerically, the algorithm was implemented by the dynamic programming method extended by means of an additional functional relationship, implying the presence of suboptimal policies.

Conclusions

Conclusions. The conducted runs of computational experiments confirmed the operability and efficiency of the software-implemented algorithm. The performed analysis demonstrated the good convergence characteristics of the proposed algorithm as compared with other algorithms of this class applied to network diagrams. On this basis, it can be recommended for practical use in project management information systems.

управление проектамисетевой графиккритический путьалгоритмвычислительный экспериментproject managementnetwork diagramcritical pathalgorithmcomputational experimentReferencesHagstrom 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.3230200208Hagstrom 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.3230200208Kamburowski 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-QKamburowski 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-QBianco 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.20388Bianco 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.20388Brennan M. PERT and CPM: a selected bibliography. Monticello, Ill.: Council of Planning Librarians, 1968. 11 p.Brennan M. PERT and CPM: a selected bibliography. Monticello, Ill.: Council of Planning Librarians, 1968. 11 p.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.20Alagheband 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.20Damci 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-0Damci 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-0Willis 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-8Willis 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-8Bowers J.A. Criticality in resource constrained networks. J. Oper. Res. Soc. 1995;46(1):80–91. https://doi.org/10.1057/jors.1995.9Bowers J.A. Criticality in resource constrained networks. J. Oper. Res. Soc. 1995;46(1):80–91. https://doi.org/10.1057/jors.1995.9Shtub 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-3Shtub 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-3Shtub A. The integration of CPM and material management in project management. Constr. Manag. Econ. 1988;6(4):261–272. https://doi.org/10.1080/01446198800000023Shtub A. The integration of CPM and material management in project management. Constr. Manag. Econ. 1988;6(4):261–272. https://doi.org/10.1080/01446198800000023Ananthanarayanan 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-9Ananthanarayanan 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-9Garcí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.115193Garcí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.115193Fulkerson D.R. Expected critical path lengths in PERT networks: Oper. Res. 1962;10(6):745–912. https://doi.org/10.1287/opre.10.6.808Fulkerson D.R. Expected critical path lengths in PERT networks: Oper. Res. 1962;10(6):745–912. https://doi.org/10.1287/opre.10.6.808Bellman R. On a routing problem. Quart. Appl. Math. 1958;16(1):87–90. https://doi.org/10.1090/qam/102435Bellman R. On a routing problem. Quart. Appl. Math. 1958;16(1):87–90. https://doi.org/10.1090/qam/102435Stern 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-xStern 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-xDreyfus S.E. An appraisal of some shortest-path algorithms. Operations Research. 1969;17(3):395–412. https://doi.org/10.1287/opre.17.3.395Dreyfus S.E. An appraisal of some shortest-path algorithms. Operations Research. 1969;17(3):395–412. https://doi.org/10.1287/opre.17.3.395Clarke 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/0111081Clarke 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/0111081Pollack 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-2Pollack 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-2Shier 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.3230060303Shier 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.3230060303Shier 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.3230090303Shier 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.3230090303Minieka 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.145Minieka 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.145Eppstein D. Finding the k shortest paths. SIAM J. Comput. 1999;28(2):652–673. https://doi.org/10.1137/S0097539795290477Eppstein D. Finding the k shortest paths. SIAM J. Comput. 1999;28(2):652–673. https://doi.org/10.1137/S0097539795290477Yen 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/2629312Yen 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/2629312Hershberger 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.1290682Hershberger 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.1290682Chen 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.12699Chen 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.12699Hu 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.023Hu 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.023Hamed 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.004Hamed 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.004Hu 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.8628928Hu 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.8628928Liu 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=10185Liu 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=10185Guo 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/1748301816680470Guo 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/1748301816680470Xu 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.005Xu 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.005Jin 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.005Jin 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.005Kaufmann A., Debazeille G. La méthode du chemin critique. Paris: Dunod; 1964. 170 p.Kaufmann A., Debazeille G. La méthode du chemin critique. Paris: Dunod; 1964. 170 p.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/2099049Bellman 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/2099049Shier 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.020Shier 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

The authors declare that there are no conflicts of interest present.