Построение сетевого графика

Нумерация событий комплекса операций проекта WSP

Начальное событие	Код операции	Предшествующие операции	Конечное событие
	Z1
	Z2	Z1
	Z3	Z2, Z15, Z17
	Z4	Z2, Z17
	Z5	Z15, Z17
	Z6	Z4, Z5, Z16, Z17
	Z7	Z3, Z4, Z15, Z17
	Z8	Z3, Z4, Z15, Z17
	Z9	Z6, Z7, Z8, Z18
	Z10	Z6, Z7, Z8, Z18
	Z11	Z6, Z7, Z8, Z9
	Z12	Z9, Z11
	Z13	Z9, Z10, Z11, Z12
	Z14	Z13
	Z15	Z1
	Z16	Z1
	Z17	Z1
	Z18	Z1

При этом предполагается, что каждой операции соответствует два отдельных события: начальное и конечное. Например, для операции Z9 начальным событием является 16 и конечным 17.

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

Пусть Z = {z₁, z₂, …, z_m} – множество операций, а I = {i₀, i₁,…i_n} – множество событий комплекса операций проекта .

Построим ориентированный граф по следующим правилам.

1. Количество вершин графа равно количеству событий комплекса операций ;

2. Количество дуг графа равно количеству операций комплекса операций ;

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

1). , – на множестве вершин графа ;

2). , – на множестве дуг графа .

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

5. Граф должен иметь только одну вершину , не имеющую исходящих дуг, она должна соответствовать завершающему событию i_t = f (v_t ).

6. Граф не должен содержать контуров.

7. Любая пара вершин графа должна быть соединены не более чем одной дугой.

Граф представляет собой математическую модель комплекса операций. Каждая дуга e_k этого графа соответствует одной операции z_k, а каждая вершина v_i – одному событию . Причем, если i_r является начальным, а – конечным событиями для операции , то является начальной, а – конечной вершинами для дуги , т.е. инцидентность вершин и дуг графа моделирует инцидентность событий и операций комплекса.

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

Попытка построить сетевой график для комплекса операций, представленного в табл. 3.2 приводит к некоторым сложностям.

Рассмотрим сначала отдельно операцию Z4, имеющую начальное событие 6 и конечное 7. Она непосредственно предшествует операциям Z6, Z7 и Z8. Первоначальное построение приводит к графу, изображенному на рис. 1. Вершины графа (события) здесь изображены овалами, а дуги (операции) сплошными линиями со стрелками. Дуги соединяют вершины, соответствующие начальному и конечному событиям соответствующей операции.

Рис. 1. Построение фрагмента сетевого графика для операций Z4, Z6, Z7 и Z8

Интуитивно ясно, что событие 7 должно предшествовать событиям 10, 12 и 14. Но в перечне (табл. 3.2) нет операций, связывающих эти события. В таких случаях необходимо расширить комплекс операций, добавив фиктивные операции, позволяющие отразить недостающие логические связи между событиями. На рис. 2 изображен предыдущий граф (рис. 1), в который добавлены три дуги, соответствующие фиктивным операциям F1, F2 и F3. Как правило, фиктивные операции изображаются на рисунках штриховой линией. Дальше всегда будем придерживаться такого обозначения.

Рис. 3 Добавление фиктивных операций

для связи операции Z4 с операциями Z6, Z7 и Z8

Фиктивные операции отражают технологическую или ресурсную зависимость в выполнении некоторых операций. В данном примере фиктивные операции F1, F2 и F2 отражают тот факт, что кодирование интерфейсов пользователей (операция Z6), кодирование процедур СУБД (Z7) и кодирование классов (Z8) в проекте WSP не могут быть начаты раньше, чем закончится проектирование классов (Z4). Для того, чтобы подчеркнуть, что операция является не фиктивной, будем использовать термин действительная операция. Таким образом, все операции, приведенные в табл. 1 и 2, являются действительными операциями.

На рис.3 изображен сетевой график всего комплекса операций проекта WSP. Как и раньше, действительные операции отображены сплошными помеченными дугами, а фиктивные операции пунктирной линией. Обозначения для фиктивных операций вводить не обязательно – для этого будем использовать упорядоченные пары инцидентных вершин. Например, фиктивные операции <3,4 >, <29,4> и <33,4 > указывают на то, что действительная операция Z3 не может быть начата до тех пор, пока не закончатся действительные операции Z2, Z15 и Z17.

Рис. 3.3. Сетевой график проекта WSP