Формалізація алгоритму автоматичної побудови оптимального розкладу послідовності робіт, що задається ациклічним спрямованим графом
Date
2005-03-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Видавництво Національного університету “Львівська політехніка”
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.
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.
Description
Keywords
Citation
Павлов О. Формалізація алгоритму автоматичної побудови оптимального розкладу послідовності робіт, що задається ациклічним спрямованим графом / О. Павлов, Л. Аксенова, О. Кулікова // Вісник Національного університету “Львівська політехніка”. — Львів : Видавництво Національного університету “Львівська політехніка”, 2000. — № 413 : Комп’ютерна інженерія та інформаційні технології. — С. 127–133. — (Методи й алгоритми сучасних інформаційних технологій).