|
В описание системы GERT мы включили в качестве параметра дуги время выполнения соответствующей операции процесса. В действительности можно рассматривать также любой характерный параметр процесса, который обладает аддитивностью по дугам любого пути. Если времена выполнения операций сети G представляются независимыми случайными величинами, то G' обладает рядом свойств, представляющих интерес с вычислительной точки зрения. Для изучения этих свойств далее рассмотрим три частных случая: 1) G' состоит из двух последовательных дуг; 2) G' — из двух параллельных ветвей, 3) G'— из одной ветви и одной петли. Последовательные дуги. Рассмотрим простую сеть, состоящую из двух последовательных ветвей. Эти две ветви могут быть заменены одной эквивалентной им ветвью, как показано ниже. Исходные ветви имеют Wпреобразования Wyfa) = Wjk(s) = pjkMjk(s). W-функция для эквивалентной ветви (/, к) имеет вид Wik(s) = PikMik(s). Напомним, что производящая функция моментов суммы двух независимых случайных величин равна произведению производящих функций моментов этих величин. Тогда поскольку pik = pijpjk и Mik(s) = то (2.3.2) Основной результат (2.3.2) может быть обобщен на случай трех и более ветвей: W-функция для эквивалентной ветви равна произведению 17функций для последовательных ветвей. Параллельные ветви. Рассмотрим простую сеть, состоящую из двух параллельных ветвей. Доказано, что эти ветви могут быть заменены эквивалентной ветвью. Пусть (/, у)—такая ветвь. По определению W^s) =PijM^s). В этом случае р,, ра + рь и Mrfs) = [paMa(s)+pbMb(s)]/(pa+pb). Поэтому 89 |
В частности, A/y(s) = £[esa] = esa при yy = а = const. Если а = 0, то A/y(s) = 1. В приложении 3 представлена таблица, в которой описаны некоторые наиболее важные функции распределения, указаны соответствующие производящие функции моментов и первые (математические ожидания) й вторые моменты относительно начала координат. Обозначим через ру — вероятность того, что операция (/, у) будет выполнена при условии, что узел i выполнен. Для случайной величины Yy определим W-функцию как Wy(s}=PijMy(s). (3.2.1) С помощью преобразования (3.2.1) всегда можно определить сеть G', структура которой идентична структуре сети G, только вместо двух параметров дуг ру и у у присутствует один параметр Wy. На рис. 3.2.1 изображены дуга сети G и соответствующая ей дуга сети G'. а б Рис. 3.2.1 Сети G и G' а элемент сети G; б — элемент сети G' В описание системы GERT мы включили в качестве параметра дуги время выполнения соответствующей операции алгоритма. В действительности можно рассматривать также любой характерный параметр процесса, который обладает аддитивностью по дугам любого пути. Если времена выполнения операций сети G представляются независимыми случайными величинами, то G' обладает рядом свойств, представляющих интерес с вычислительной точки зрения. Для изучения этих свойств далее рассмотрим три частных случая 1) G' состоит из двух последовательных дуг; 2) G' — из двух параллельных ветвей, 3) G' — из одной ветви и одной петли. 112 Последовательные дуги. Рассмотрим простую сеть, состоящую из двух последовательных ветвей. Эти две ветви могут быть заменены одной эквивалентной им ветвью, как показано ниже. Исходные ветви имеют Wпреобразования Wy(s) = pyMy(s), Wik(s) = pyM^s). И'-функция для эквивалентной ветви (г, к) имеет вид Wyfs) = pikMyfs). Напомним, что производящая функция моментов суммы двух независимых случайных величин равна произведению производящих функций моментов этих величин. Тогда ПОСКОЛЬКУ pik ^PyPik и Mik(s) = [Myftj][M;k(s)]f ТО Wik(s) = [pijMjj(s)][pjkMjk(s)] = Wij(s)Wik(s). (3.2.2) Основной результат (3.2.2) может быть обобщен на случай трех и более ветвей: JF-функция для эквивалентной, ветви равна произведению Wфункций для последовательных ветвей. Параллельные ветви. Рассмотрим простую сеть, состоящую из двух параллельных ветвей. Доказано, что эти ветви могут быть заменены эквивалентной ветвью. Пусть (/, у)—такая ветвь. По определению Wy(s) =PyMy(s). В этом случае ру = ра + рь и My(s) = \paMa(s)+pbMb(s)}l{pa+pb). Поэтому W,j (5) = [ра + рь + = W„ (s) + Wb (s) (3.2.3) L Pa + Pb J Формула (3.2.3) также может быть обобщена на случай сетей, состоящих из трех и более параллельных ветвей: ^-функция для эквивалентной ветви равна сумме РК-функций для параллельных дуг. Петли. Рассмотрим простую сеть, состоящую из одной петли и одной дуги. Она может быть преобразована в эквивалентную сеть, содержащую только одну дугу. Отметим, что рассматриваемая сеть может быть преобразована. Эта новая сеть будет состоять из бесконечной последовательности параллельных цепей, каждая из которых представляет собой совокупность последовательных ветвей. Поэтому можно вначале каждую ее цепь свести к из |