Улучшение алгоритма Дейкстры для оценки характеристик и критического пути проекта

В любой отрасли разработка структуры планирования проекта представляет собой сложную техническую задачу, которая включает в себя оценку факторов, ограничивающих выполнение задач по каждому виду работ, и соответствующие инструменты планирования. Любое ограничение влияет на время выполнения работ, эксплуатационные издержки и общую эффективность выполнения проекта. Процессы метода оценки и пересмотра программ (Programme Evaluation Review Technique, PERT) и метода критического пути (Critical Path Method, CPM) побудили многих исследователей изучать возможные способы поиска критических путей и работ в сетевом графике. CPM и PERT пока еще очень далеки от реализации вероятностной среды. Однако подходы на основе искусственного интеллекта, такие как генетический алгоритм, алгоритм Дейкстры и другие, используются для анализа сети в рамках управления проектами. Настоящее исследование призвано помочь менеджеру проекта спланировать график выполнения строительного проекта для определения ожидаемого времени его завершения. В данной исследовательской работе мы описываем метод получения раннего и позднего значений времени критического пути с помощью модифицированного алгоритма Дейкстры с треугольными нечеткими числами. Для поиска оптимального пути для предложенного метода разработаны алгоритмы прохода вперед и назад. Также приведены численные примеры. Результаты моделирования приведены с использованием программы «C». Наконец, проводится сравнение с традиционным методом PERT.

1. Библиографический список 1. Chang H., Abraham J.A. CHAN: An efficient critical path analysis algorithm // 1993 European Conference on Design Automation with the European Event in ASIC Design, Paris, France, 22-25 February 1993. Pp. 444-448. DOI: 10.1109/EDAC.1993.386435

2. Cheng X.L., ZhangY.L., Cui X.S. Applied in Resource Constrained Project Scheduling Problem // Industrial Engineering Journal. 2004. Vol. 7(3). Pp. 51-54.

3. Lee D. Probability of project completion using stochastic project scheduling simulation // Journal of Construction Engineering and Management. 2005. Vol. 131(3). Pp. 310-318.

4. Li Q, Zhang J., Zhang R.T. Application of Monte Carlo Simulation in Project Schedule // Journal of Yangtze University (Natural Science Edition). 2007. Vol. 4(2). Pp. 62-66.

5. Lu M., AbouRizk S.M. Simplified CPM/PERT simulation model // Journal of Construction Engineering and Management. 2000. Vol. 126(3). Pp. 219-226.

6. MacCrimmon K.R., Ryavec C.A. An Analytical Study of the PERT Assumptions // Operation Research. 1964. Vol. 12. No. 1. Pp. 16-37.

7. Malcon D.G., Roseboom J.H., Clark C.E. et al. Application of a Technique for Research and Development Program Evaluation // Operation Research. 1959. Vol. 7. Issue 5. Pp.646-669.

8. Sackey Solomon, Kim Byung-Soo. Schedule Risk Analysis using a proposed Modified Variance and Mean of the Original Program Evaluation and Review Technique Model // KSCE Journal of Civil Engineering. 2018. Vol. 23(4). Pp. 1484-1492.

9. Ravi Shankar N., Sireesha V. Using modified Dijkstra’s algorithm for critical path method in a project network // International Journal of Computational and Applied Mathematics. 2010. Vol. 5. No. 2. Pp. 217-225.

10. Xiaokang Han, Wenzhou Yan, Mei Lu. Intelligent Critical Path Computation Algorithm Utilising Ant Colony Optimisation for Complex Project Scheduling // Complexity. 2021. Vol. 2021. Article ID 9930113. 8 p. DOI: 10.1155/2021/9930113

11. Zadeh L.A. Fuzzy sets // Information and Control. 1965. Vol. 8. Issue 3. Pp 338-353.