4. Элементы сетевого планирования

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

1. Проекты состоят из хорошо определенной совокупности работ, выполнение которых означает завершение проекта.

2. Работы упорядочены таким образом, что они должны выполняться в определенной последовательности.

3. Продолжительность выполнения каждой работы известна заранее либо может быть оценена достаточно точно.

4. Предполагается, что начатая работа продолжается без перерыва до завершения.

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

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

5.1 Построение сетевой модели

Для полного описания проекта необходимо :

1. Задать список работ, входящих в проект, S={s₁,s₂,…,s_n}, и длительность их выполнения t(s_i).

2. Задать для каждой работы s_iÎS список непосредственно предшествующих ей работ Г^-1(s_i).

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

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

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

Направление дуги определяет соотношения предшествования. На отрезке сети

i-е событие должно произойти до начала работы А. Аналогично, j-е событие не может произойти до завершения работы А.

Отношение предшествования между узлами является транзитивным. Если i-е событие предшествует j-му событию, а j-е событие предшествует k-му событию, то i-e событие предшествует k-му событию:

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

Неправильное представление предшествования.

Сетевая модель с фиктивной работой.

Рисунок 1. Рисунок 2.

Допустим, например, что фрагмент сетевой модели, показанный на рис. 1, соответствует такой последовательности выполнения работ: работа G следует за работами В и С, и работа Е следует за работой В (но не за работойС)]. Очевидно, что тогда схема на рис.1 является неправильной, поскольку она показывает, что как работа G, так и работа Е следуют за работами С и В. Чтобы получить правильное представление, необходимо ввести фиктивную работу, продолжительность которой равна нулю. Фиктивная работа обозначена штрихпунктиром. Правильное представление дано на рис. 2, где через X обозначена фиктивная работа. При необходимости фиктивные работы могут использоваться для изображения соотношений между работами, которые невозможно представить другим способом. Введение в проект фиктивных работ - это прием, позволяющий показать требуемое соотношение без изменения фактической продолжительности проекта. Для иллюстрации построения сетевой модели рассмотрим следующий пример.

Пример 1.

Требуется построить сетевой график проекта. Информация о проекте представлена в таблице 1.

Таблица 1

Работа si		Продол-житель-ность работы	Непосред-твенно предшеству-ющие работы
Обозна-чение	Описание	t(si)	Г-1(si)
A	Закупка деталей для узла 1	6	Нет
B	Закупка деталей для узла 2	4	Нет
C	Закупка деталей для узла 3	9	Нет
D	Изготовление узла 1	7	A
E	Изготовление узла 2	8	B
F	Изготовление узла 4	6	D,E
G	Изготовление узла 3	10	C,D
H	Сборка	4	F,G
I	Проверка и испытание	3	H

Сетевой график, соответствующий проекту, изображен на рис.3. В нем буквами X и Y обозначены фиктивные работы, наличие которых здесь обязательно. Действительно, если убрать дугу X, то получим сеть для проекта, в котором работе G непосредственно предшествуют работы E,D,C. Однако, это не соответствует проекту, описанному в таблице 1. Аналогичный результат получим, исключив фиктивную дугу Y: работе F будут непосредственно предшествовать работы E,D,C.

Сетевой график для примера 1.

Рисунок 3.

Около каждой дуги указаны имя соответствующей работы и ее продолжительность.

Для построения наиболее эффективного метода анализа сети требуется определить правильную нумерацию событий.

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

События сети на рис.3 имеют правильную нумерацию.

При большом размере сети определение правильной нумерации событий может вызвать затруднения.

Алгоритм правильной нумерации событий.

Начинаем просмотр сети с начального события (узла, для которого Г^-1(s_i)=Æ ), которому присваиваем номер 1 и считаем событием 0-го ранга. Полагаем i =0, k₀=0.

Вычеркиваем все дуги, исходящие из событий i-го ранга. Если таких дуг нет, переходим к шагу 4.

События s¢, для которых Г^-1(s¢)=Æ , объединяем в группу событий (i+1)-го ранга и присваиваем им в произвольном порядке номера k_i+1,k_i+2,k_i+3,…,k_i+1. Увеличиваем i на единицу и переходим к шагу 2.

Конечной целью анализа сетевой модели является получение инфор­мации о плановых сроках выполнения отдельных работ. Остановимся на решении этой задачи методом критического пути (МКП).