Алгоритм поиска минимального разреза сетевой модели слиянием вершин

Задача сокращения общей продолжительности проекта («сжатие») возникает при разработке и корректировке календарных графиков. Работы, требующие «сжатия», определяются минимумом дополнительно привлекаемых ресурсов при их единичном сокращении. Минимальный разрез критической сети определяет такие работы. Представлена сущность поиска минимального разреза путем слияния вершин (стягивания ребер) критической сети. Порядок выбора вершин состоит в следующем. Возможные варианты слияния (предварительные шаги) оцениваются эквивалентными разрезами. Минимальный разрез определяет приоритетную для слияния вершину критической сети. После этого алгоритм повторно исследует все возможные варианты присоединения смежных вершин (на следующем шаге). Показана общая применимость алгоритма. Установлены условия эффективного применения метода слияния вершин. Представлены результаты поиска минимальных разрезов критической сети с помощью данного метода. Расчеты показали, что в 14 из 15 примеров алгоритм установил глобальные минимальные разрезы. Реализация предложенных подходов позволит определить работы графика, подлежащие оптимизации, рассчитать размер сокращения и количество привлекаемых ресурсов. Предложенная методика может быть рекомендована для использования руководителями строительных проектов.