Стрелочные графы

1.2 Стрелочные графы

В этом типе графов (рис. 1) каждая операция представлена стрелкой. Длина стрелок значения не имеет. Направление стрелки отражает ход времени и обычно указывается слева направо. Начало и окончание каждой операции называются событиями и изображаются на графе кружочками или узлом.

2

1

А

Предшествующее Операции Последующее

событие (начало) событие (окончание)

Рис. 1. Изображение операции на стрелочном графе

Операции обозначают буквой или словом, а события - числом. Поскольку любая операция характеризуется парой событий, ее можно также обозначать с помощью чисел, соответствующих этим событиям. Например, на рис. 1 операция А означает то же самое, что и операция (1, 2). Одному узлу может соответствовать (входить или выходить из него) несколько операций. Событие, изображаемое на графе с помощью узла, не считается свершившимся до тех пор, пока не окончены все входящие в него операции. Операция, выходящая из некоторого узла, Не может начаться до тех пор, пока не будет достигнуто начальное событие, т.е. пока не будут завершены все операции, входящие в узловое начальное событие.

Если операция С не может быть начата до момента окончания работ А и В, логическую схему данной ситуации можно представить графически следующим образом (см. рис. 2).

Начальным событием для С является конечное событие для А и В. Существенно, что в стрелочном графе сохраняется логическая зависимость операций. Иногда, чтобы достичь этого, необходимо включить в граф одну или более фиктивных логических операций.

Фиктивная логическая стрелка вводится в граф, если необходимо отразить, что некоторое событие не может появиться раньше другого события, а с помощью обычных стрелок, соответствующих операциям, этого сделать нельзя. Функция фиктивной логической операции состоит в том, чтобы показать последовательность появления событий.

 

1

3

4

А С

2

В

 

Рис. 2. Логические взаимосвязи в стрелочном графе

Фиктивным логическим операциям ставится в соответствие нулевая продолжительность выполнения, а изображаются они обычно пунктиром. Например, если работу С нельзя начать прежде, чем завершится операция А, а работу О нельзя начать до тех пор, пока не завершатся работы А и В, соответствующий стрелочный граф будет выглядеть следующим образом:

Кроме того, в стрелочных графах для избежания неоднозначности используются фиктивные операции идентификации. В некоторых пакетах прикладных программ, используемых в сетевом анализе, операции обозначаются не с помощью букв или слов, а числами, обозначающими соответствующие им события. Если же две или более операций выполняются одновременно и имеют одни и те же начальное и конечное события, то компьютер не сможет отличить их друг от друга и не воспримет вводимую исходную информацию. Как показано на рис. 4, включение фиктивной операции идентификации позволяет решить данную проблему. На практике принято нумеровать события таким образом, чтобы номер конечного события был больше, чем номер начального события.

1

5

2

А  С

Фиктивная логическая

операция

6

4

3

В  D

Рис. 3. Использование в стрелочном графе

фиктивной логической операции

 

Первый шаг после составления списка операций, входящих в проект, состоит в том, чтобы создать таблицу операций, в которой отражаются все операции, а также операции, непосредственно им предшествующие.

В данный список не включаются фиктивные логические операции или операции идентификации. На основе полученного списка строится стрелочный сетевой граф, включающий действительные и фиктивные операции и отражающий установленные взаимосвязи между ними. После того, как закончено построение исходного графа, можно выявить и исключить из рассмотрения ненужные фиктивные операции. Затем для улучшения логической схемы исходный граф можно модифицировать и перекомпоновать.

Фиктивная операция

идентификации

3

3

1

1

А Заменяется на

Рис. 4. Использование в стрелочном графе фиктивной операции идентификации

Ненужные фиктивные логические операции можно выявить с помощью простого практического правила. Если единственной операцией, выходящей из некоторого узла, является фиктивная логическая операция, то по всей вероятности без нее можно обойтись.

Пример 1. Компания "Эвриком" - это промышленная фирма, которая заключила контракт о производстве партии станков, предназначенных к использованию крупным предприятием обувной промышленности для массового производства обуви. Ниже перечислены операции, которые необходимо выполнить в процессе разработки и производства этих станков (табл. 1).

Нужно изобразить операции с помощью стрелочного графа.

Решение.

Сетевой граф должен начинаться с единственного начального события, которое показано на рис. 5 кружочком, и заканчиваться единственным конечным событием. Построение графа мы начали с первого события. С этого события начинаются все операции, которым не предшествуют никакие виды работ. Начинать построение полезно с примерного эскиза будущего графа:

F G

5 9 10 12

А  B C E  K  L

1 2 3 4 7 13 14

 D H I

6 8 11

J

 

Рис. 5. Примерный эскиз графа для примера 1

Таблица 1. Таблица операций для задачи из примера 1

ОПЕРАЦИИ	Непосредственно предшествующая операция
А Составление сметы затрат В Согласованные оценки С Покупка собственного оборудования D Подготовка конструкторских проектов E Строительство основного цеха F Монтаж оборудования G Испытания оборудования H Определение типа модели I Проектирование внешнего корпуса J Создание внешнего корпуса K Конечная сборка L Контрольная проверка	- A B B D C,E F D D H,I G,J K

В соответствии с приведенной выше таблицей необходимо тщательно, переходя от одной операции к другой, проверить построенный в первом приближении граф.

A  B C  F G  K L

1 2 3 5 8 9 10 11

D E J

4  7 Фиктивная операция

H I идентификации

6

 

Рис.6. Новый чертеж стрелочного графа для примера 1

 

Пример 2. Компания "Эвриком" является участником другого проекта, детали которого приведены ниже. Изобразим данный проект при помощи стрелочного графа.

Решение

Построение начинаем с начального события, обозначенного кружком 1. Из таблицы следует, что существуют три операции - А, В и С, которым не предшествует ни одна из операций. Поэтому из начального события выходят три стрелки. На первый взгляд таблица операций выглядит чрезвычайно простой, однако отразить присущую ей логику с помощью сетевого графа достаточно трудно, вследствие чего мы вынуждены использовать три фиктивные логические операции (см. рис. 7).

 

Таблица 2. Таблица операций для примера 2

Операция	Непосредственно Предшествующая операция	Операция	Непосредственно предшествующая операция
A B C D	- - - A,B	E F G H	B,C C D,E F,G

4

2

1 5 6 7 8

3

Рис. 7. Стрелочный граф для примера 2