Формалізація алгоритму автоматичної побудови оптимального розкладу послідовності робіт, що задається ациклічним спрямованим графом

Abstract

Розглядається програмний продукт розв'язання задачі побудови оптимального розкладу послідовності робіт, відношення порядку на якій задається ациклічним спрямованим графом загального виду. Алгоритм реалізує послідовність дій побудови оптимального розкладу для строго послідовно-паралельного графа [І], Узагальнення алгоритму здійснюється ітераційним аналізом графа загального вигляду та декомпозиції його на множини максимальних пріоритетів, що є послідовно-паралельними підграфами. Досліджується ефективність застосованих алгоритмічних рішень.

The subject is software for the optimal schedule construction on the sequence of works with the precedence constraints assigned by the non-circle directed graph. The base of above mentioned software is an algorithm of the optimal schedule construction on the set of works with the precedence constraints assigned by series-parallel graph [1], This algorithm is generalized by means of the general-form graph iteration analysis and decomposition onto the maximal priority sets which are the series-parallel sub-graphs, The effectiveness of used algorithmic methods is investigated.