108990 (Сетевые графики)

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

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

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

Пусть некоторый проект W состоит из работ V₁,...,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 предшествует всем тем работам vW, для которых список ПРЕДШ(v) пуст, иначе говоря, для всех таких работ vW положим ПРЕДШ(v)={s}. Положим далее ПРЕДШ(s) =, ПРЕДШ(p)={vW: 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).

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

Отсутствие контуров в сети G позволяет пронумеровать работы проекта W таким образом, чтобы для каждой дуги (V_i,V_j) сети G выполнялось условие i

Конечной целью построения сетевой модели является получе­ние информации о возможных сроках выполнения как отдельных работ, так и о возможном сроке выполнения всего проекта в це­лом. Обозначим через 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), vV.

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

1. Объявить возможные ранние сроки начала РНАЧ(v) и выполнения РВЫП(v) работ равными нулю. Текущей вершиной объявить первую вершину v_k=v_1.

2. Всем вершинам v предшествующим текущей вершине v_k, значение РНАЧ(v_k) присвоить максимум из значений РВЫП(v) и РНАЧ(v_k). Значение РВЫП(v_k) положить равным значению РНАЧ(v_k) плюс время выполнения самой работы текущей вершины t(v_k).

3. Если имеется следующая вершина (работа) после текущей, то объявить ее текущей вершиной v_k, иначе перейти в Шаг 5.

4. Вернуться в Шаг 2.

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

Пусть T — плановый срок выполнения проекта W. Ясно, что Т должно удовлетворять неравенству Т >= РВЫП(V_n+1).

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

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

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

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

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

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

АЛГОРИТМ 2.

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

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

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

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

3. Присвоить значению ПВЫП(v) для всех работ vПРЕДШ(v) предшествующих текущей работе v_k минимальное значение из значений ПВЫП выполнения роботы v или ПНАЧ выполнения текущей работы v_k, если таковых нет перейти в Шаг 4.

4. Если имеется предыдущая вершина (работа) к текущей, то объявить её текущей, иначе перейти в Шаг 6.

5. Перейти в Шаг 2.

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

Проиллюстрируем работу приведенных алгоритмов на следующих примерах:

Пример 1: Проект гаража для стоянки автопогрузчиков.

Рис 1. Проект гаража для стоянки автопогрузчиков.

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

Таблица результатов работы алгоритма.

Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=71. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.

Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPB(v)=ПНАЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).

Из таблицы видно, что критическими работами являются 1, 2, 3, 4, 6, 7, 8, 9, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=71.