МАТРИЧНЫЙ МЕТОД ПОИСКА ПУТЕЙ НА ВЗВЕШЕННЫХ ОРИЕНТИРОВАННЫХ ГРАФАХ В ЗАДАЧАХ СЕТЕВОГО ПЛАНИРОВАНИЯ ПРИ ПРОЕКТИРОВАНИИ И ЭКСПЛУАТАЦИИ МОРСКИХ ПОРТОВ

Аннотация

Отмечается, что сетевое планирование, или сетевой анализ, представляет собой класс прикладных методов управления проектами, обеспечивающих планирование, анализ сроков выполнения (как ранних, так и поздних), риска невыполнения проекта или его отдельных частей. Данные методы позволяют увязать выполнение различных работ и процессов во времени, составить операционный график выполнения проекта, получить прогноз общей продолжительности реализации всего проекта. В современной практике проектирования, строительства и управления морским портами сетевое планирование представляет наиболее востребованный инструментарий лиц, принимающих решение. Методы сетевого планирования условно подразделяются на детерминированные (диаграммы Гантта, жесткие и с дополнительным временным люфтом, метод критического пути и др.) и вероятностные. Последние, в свою очередь, делятся на неальтернативные (метод статистических испытаний или метод Монте-Карло, метод оценки и пересмотра планов PERT) и альтернативные (метод графической оценки и анализа GERT). Во многих приложениях основу используемого метода составляет поиск пути на графе. Многократное повторение экспериментов, характерное для наиболее эффективных вероятностных методов, предъявляет высокие требования к снижению вычислительной трудоемкости используемых алгоритмов. Кроме того, различный характер причинно-следственных связей между объектами сетевых моделей приводит к формированию такой структуры изображающего процессы графа, которые не позволяют применять большинство известных алгоритмов. В данной статье описывается матричный алгоритм поиска путей на взвешенных ориентированных графах, отличающийся низкой вычислительной трудоемкостью, простотой и наглядностью, а также допускающий различные виды причинно-следственных связей между составными событиями. Предложенный алгоритм является результативным в отношении поставленных задач, а его реализация практически не отличается от псевдокода, использованного для его описания, что обеспечивает легкость реализации, простоту отладки и верификации кода, легкость встраивания алгоритма в различные прикладные задачи сетевого планирования. Одной из таких задач является нахождение критических путей в условиях разброса временных параметров всех работ (операций), связывающих между собой вершины-события.

Ключевые слова

сетевое планирование, поиск путей на графе, методы имитационного моделирования

Читать полный текст статьи:  PDF

Список литературы

Об авторах

Кузнецов Александр Львович - доктор технических наук, профессор

thunder1950@yandex.ru. kaf_pgt@gumrf.ru

ФГБОУ ВО «ГУМРФ имени адмирала С. О. Макарова»