СЕТЕВЫЕ ГРАФИКИ
Такие крупные проекты, как строительство дома, разработка автоматизированной системы бухгалтерского учета, изготовление станка и т.д. можно разбить на большое количество различных операций (работ). Одни операции могут выполняться одновременно, другие — только последовательно: одна операция после окончания другой. Например, при строительстве дома можно совместить во времени внутренние отделочные работы и работы по благоустройству территории, однако возводить стены можно только после того, как будет готов фундамент
Основные задачи планирования работ по осуществлению некоторого проекта:
определение времени возможного окончания как всего проекта в целом, так и отдельных работ, образующих проект;
определение резервов времени для выполнения отдельных работ;
определение критических работ, то есть таких работ, задержка в выполнении которых ведет к задержке выполнения всего проекта в целом;
управление ресурсами, если таковые имеются и т.п
Пусть некоторый проект W состоит из работ V 1 ,..., V n ; для каждой работы V k известно, или может быть достаточно точно оценено время ее выполнения t ( V k ). Кроме того, для каждой работы V k известен, возможно пустой, список ПРЕДШ( V k ) работ, непосредственно предшествующих выполнению работы V k . Иначе говоря, работа V k может начать выполняться только после завершения всех работ, входящих в список ПРЕДШ( V k )
В список работ проекта W добавим две фиктивные работы s и p , где работа s обозначает начало всего проекта W. а работа p — завершение работ по проекту W. При этом будем считать, что работа s предшествует всем тем работам v Î W, для которых список ПРЕДШ(v) пуст, иначе говоря, для всех таких работ v Î W   положим   ПРЕДШ(v)={s}.   Положим далее ПРЕДШ(s) = Æ , ПРЕДШ( p )={v Î W: v не входит ни в один список ПРЕДШ(w)}, то есть считаем, что работе p предшествуют все те работы, которые могут выполняться самыми последними. Время выполнения работ s и p естественно положить равными нулю:    t(s)=t( p )=0
Весь проект W теперь удобно представить в виде сети G =( V , E , c ). Ориентированный взвешенный граф G =( V , E , c ) называется сетью. Сеть может быть представлена матрицей весов дуг, массивами смежностей СЛЕД или ПРЕДШ, или списками СЛЕД[ v ] или ПРЕДШ[ v ]. При этом записи в списках смежности состоят из трех компонент: поля имени узла, поля веса соответствующей дуги и поля ссылки на следующую запись), где сеть G =( V , E , c ) определим по правилам:
V = W , то есть множеством узлов объявим множество работ;
E ={( v , w ) : v Î ПРЕДШ(w)}, то есть отношение предшествования задает дуги в сети;
c(v,w)=t(w)
Построенную сеть G часто называют сетевым графиком выполнения работ по проекту W. Легко видеть, что списки смежностей этой сети ПРЕДШ(v) совпадают с заданными для проекта списками предшествующих работ ПРЕДШ(v)
Очевидно, что сетевой график любого проекта не должен содержать контуров. Действительно, пусть узлы V k 1 , V k 2 ,..., V kr = V k 1 образуют контур в сети G. Это означает, что работа V k 2 не может начаться раньше, чем будет завершена работа V k 1 , работа V k 3 — раньше, чем завершится работа V k 2 , и т.д., и, наконец, V kr = V k 1 — раньше, чем будет завершена работа V kr -1 . Но тогда никакая из работ V k 1 ,..., V kr никогда не сможет быть выполнена. А каждый реальный проект должен допускать возможность его завершения. Следовательно, в сетевом графике нет контуров
Отсутствие контуров в сети G позволяет пронумеровать работы проекта W таким образом, чтобы для каждой дуги ( V i , V j ) сети G выполнялось условие i < j , то есть каждая дуга идёт из узла с меньшим номером в узел с большим номером. Осуществить такую нумерацию узлов сети G можно с помощью алгоритма топологической сортировки. Поэтому в дальнейшем будем считать, что узлы в сети G топологически отсортированы
Конечной целью построения сетевой модели является получение информации о возможных сроках выполнения, как отдельных работ, так и о возможном сроке выполнения всего проекта в целом. Обозначим через PB ЫП( v ) (соответственно PHA Ч( v )) наиболее ранний   возможный   срок   выполнения работы   v (соответственно наиболее ранний возможный срок начала работы v). Удобно считать, что PB ЫП( s )= PHA Ч( s )=0. Поскольку начать выполнять работу v можно только после того, как будут выполнены все работы, предшествующие данной работе v, то получим следующие формулы для расчета значений PHA Ч( v ) и PB ЫП( w ) :
PHA Ч( v ) = МАКС{ PB ЫП( w ): w Î ПРЕДШ(v)},
PBЫП(v)= PHAЧ(v) + t(v)
Значение PB ЫП( p ) дает наиболее ранний возможный срок завершения всего проекта в целом. Приведем запись алгоритма, непосредственно вычисляющего характеристики РНАЧ и РВЫП
 
Алгоритм 1.
Данные: Сетевой график G работ V , заданный списками ПРЕДШ( v ), v Î V
Результаты: Наиболее ранние возможные сроки начала и выполнения работ РНАЧ( v ), РВЫП( v ), v Î V
Объявить возможные ранние сроки начала РНАЧ( v ) и выполнения РВЫП( v ) работ равными нулю. Текущей вершиной объявить первую вершину v k = v 1.
Всем вершинам v предшествующим текущей вершине v k , значение РНАЧ( v k ) присвоить максимум из значений РВЫП( v ) и РНАЧ( v k ). Значение РВЫП( v k ) положить равным значению РНАЧ( v k ) плюс время выполнения самой работы текущей вершины t ( v k )
Если имеется следующая вершина (работа) после текущей, то объявить ее текущей вершиной v k , иначе перейти в Шаг 5
Вернуться в Шаг 2
Выдать наиболее ранние возможные сроки начала и выполнения работ РНАЧ(v), РВЫП(v), v Î V, конец работы алгоритма
  Пусть T — плановый срок выполнения проекта W. Ясно, что Т должно удовлетворять неравенству Т >= РВЫП( V n +1 )
Через ПВЫП( v ) (соответственно ПНАЧ( v )) обозначим наиболее поздний допустимый срок выполнения (начала) работы v , то есть такой срок, который не увеличивает срок Т реализации всего проекта
Значения возможных и допустимых сроков выполнения работ позволяют определить резервы времени для выполнения той или иной работы. Полный резерв (иногда его называют суммарный) времени выполнения работ определяется по формуле:
PE3EPB(v)=ПHAЧ(v)-PHAЧ(v)
Значение PE 3 EPB ( v ) равно максимальной задержке в выполнении работы v, не влияющей на плановый срок Т. Понятно, что справедливо и такое равенство: РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v)
Работы, имеющие нулевой резерв времени, называются критическими. Через любую такую работу проходит некоторый максимальный s- p -путь в сети G. Критические работы характеризуются тем, что любая задержка в их выполнении автоматически ведет к увеличению времени выполнения всего проекта
Приведем запись алгоритма, непосредственно вычисляющего характеристики ПВЫП и ПНАЧ
Алгоритм 2.
Данные: Сетевой график G работ V , заданный списками ПРЕДШ( v ), v Î V , плановый срок окончания проекта – Т
Результаты: Наиболее поздние допустимые сроки выполнения и начала работ ПВЫП( v ) и ПНАЧ( v )
Объявить для всех работ v Î V значение наиболее позднего срока выполнения работ равным Т – значению планового срока окончание проекта и вершину v p фиктивной работы p объявить текущей v k
Присвоить значение ПНАЧ текущей работы v k равным значению ПВЫП работы и вычесть время выполнения текущей работы
Присвоить значению ПВЫП(v) для всех работ v Î ПРЕДШ(v) предшествующих текущей работе v k минимальное значение из значений ПВЫП выполнения роботы v или ПНАЧ выполнения текущей работы v k , если таковых нет перейти в Шаг 4
Если имеется предыдущая вершина (работа) к текущей, то объявить её текущей, иначе перейти в Шаг 6
Перейти в Шаг 2
Выдать наиболее поздние допустимые сроки выполнения и начала работ ПВЫП( v ) и ПНАЧ( v ), конец работы алгоритма
Проиллюстрируем работу приведенных алгоритмов на следующих примерах:
Пример 1 : Проект   гаража для стоянки автопогрузчиков
n
Наименование работы
Предшествующие работы
Время выполнения t ( v k )

1
Начало проекта (фиктивная работа)
Нет
0

2
Срезка растительного слоя грунта
1
5

3
Монтаж каркаса
2
30

4
Обшивка стен профнастилом
3
15

5
Кровля из профнастила
3
12

6
Заполнение проема воротами
4
5

7
Масляная окраска ворот и профнастила
5,6
10

8
Щебёночное основание под полы
7
3

9
Асфальтовое покрытие
8
3

10
Уборка строительного мусора после строит
7
3

11
Конец проекта (фиктивная работа)
9,10
0

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

1
Объявление значений РНАЧ( v ) и РВЫП( v ), v Î V равными нулю. Текущая вершина v k =1

2
Вершин предшествующей первой нет
РВЫП(1)=РНАЧ(1)+ t (1). { РНАЧ(1) стало равным 0 }

3
Текущая вершина v k =2

4
Переход в Шаг 2

2
РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)} {РНАЧ(2) стало равным 0}
РВЫП(2)=РНАЧ(2)+ t (2) {РВЫП(2) стало равным 5}

3
Текущая вершина v k =3

4
Переход в Шаг 2

2
РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5}
РВЫП(3)=РНАЧ(3)+ t (3) {РВЫП(3) стало равным 35}

3
Текущая вершина v k =4

4
Переход в Шаг 2

2
РНАЧ(4)=МАКС{РВ