Министерство общего и профессионального образования РФ.

Уральский государственный университет.

Сетевые графики

Курсовая работа студента группы ИС-202 Лисицын В.С.

Руководитель Замятин А. П.

Екатеринбург, 1999.

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

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

Пусть некоторый проект W состоит из работ V1,...,Vn; для каждой работы
Vk, известно, или может быть достаточно точно оценено время ее выполнения t(Vk). Кроме того, для каждой работы Vk известен, возможно пустой, список
ПРЕДШ(Vk) работ, непосредственно предшествующих выполнению работы Vk. Иначе говоря, работа Vk может начать выполняться только после завершения всех работ, входящих в список ПРЕДШ(Vk).

Для удобства, в список работ проекта 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) определим по правилам:
1. V=W, то есть множеством узлов объявим множество работ;
2. E={(v,w) : v(ПРЕДШ(w)}, то есть отношение предшествования задает дуги в сети;
3. c(v,w)=t(w).

Так построенную сеть G часто называют сетевым графиком выполнения работ по проекту W. Легко видеть, что списки смежностей этой сети ПРЕДШ[v] совпадают с заданными для проекта списками предшествующих работ ПРЕДШ(v).

Понятно, что сетевой график любого проекта не должен содержать контуров. Действительно, пусть узлы Vk1,Vk2,...,Vkr=Vk1 образуют контур в сети G. Это означает, что работа Vk2 не может начаться раньше, чем будет завершена работа Vk1, работа Vk3 — раньше, чем завершится работа Vk2, и т.д., и, наконец, Vkr = Vk1 — раньше, чем будет завершена работа Vkr-1. Но тогда никакая из работ Vk1,...,Vkr никогда не сможет быть выполнена. А каждый реальный проект должен допускать возможность его завершения.
Следовательно, в сетевом графике нет контуров.

Отсутствие контуров в сети G позволяет пронумеровать работы проекта W таким образом, чтобы для каждой дуги (Vi,Vj) сети G выполнялось условие i= РВЫП(Vn+1).

Через ПВЫП(v) (соответственно ПНАЧ(v)) обозначим наиболее поздний допустимый срок выполнения (начала) работы v, то есть такой срок, который не увеличивает срок Т реализации всего проекта.

Значения возможных и допустимых сроков выполнения работ позволяют определить резервы времени для выполнения той или иной работы. Полный резерв (иногда его называют суммарный) времени выполнения работ определяется по формуле:

PE3EPB(v)=ПHAЧ(v)-PHAЧ(v).

Значение PE3EPB(v) равно максимальной задержке в выполнении работы v, не влияющей на плановый срок Т. Понятно, что справедливо и такое равенство:
РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).

Работы, имеющие нулевой резерв времени, называются критическими. Через любую такую работу проходит некоторый максимальный s-p-путь в сети G.
Критические работы характеризуются тем, что любая задержка в их выполнении автоматически ведет к увеличению времени выполнения всего проекта.

Приведем запись алгоритма, непосредственно вычисляющего характеристики
ПВЫП и ПНАЧ.

АЛГОРИТМ 2.

Данные: Сетевой график G работ V, заданный списками ПРЕДШ(v), v(V, плановый срок окончания проекта – Т.

Результаты: Наиболее поздние допустимые сроки выполнения и начала работ
ПВЫП(v) и ПНАЧ(v).

1. Объявить для всех работ v(V значение наиболее позднего срока выполнения работ равным Т – значению планового срока окончание проекта и вершину vp фиктивной работы p объявить текущей vk.

2. Присвоить значение ПНАЧ текущей работы vk равным значению ПВЫП работы и вычесть время выполнения текущей работы.

Поделитесь этой записью или добавьте в закладки