Задача о максимальном пути и сетевые графики.

Задача о максимальном пути формулируется следующим об­разом: в заданной сети G=(V,E,c) с выделенным узлом s, для ка­ждого узла v V найти s-v-путь, имеющий максимальную длину среди всех возможных s-v-путей в сети G.

Отметим, что имеет смысл решать эту задачу лишь в сетях, не содержащих контуров положительной длины. Рассмотрев тогда сеть, отличающуюся от исходной только изменением знаков ве­сов дуг, получим сеть, в которой нет контуров отрицательной длины. Применяя к новой сети алгоритм Форда-Беллмана, можно построить кратчайшие s-v-пути, которые будут путями макси­мальной длины в исходной сети.

Впрочем, задачу о максимальном пути в общем случае можно решать и непосредственно, заменяя в алгоритме Форда-Беллмана строку 6 на строку

6' forw V doD[v] := max(D[v], D[w]+A[w,v]);

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

Важный частный случай сети с неотрицательными весами дуг в предположении отсутствия контуров положительной длины сводится к случаю отсутствия контуров в сети. Следовательно, задача о максимальном пути в частном случае может быть реше­на алгоритмом 6.6, в котором +∞ заменяется на

-∞ (строка 3), а min на шах (строка 6). Несложное доказательство корректности исправленного таким образом алгоритма 6.6 мы предоставляем читателю.

Отметим, что замена всех минимумов в алгоритме Дейкстры (строки 7 и 10) на максимумы не позволяет получить алгоритм решения задачи о максимальном пути. Для примера достаточно рассмотреть сеть, изображенную на рис.6.5. Здесь модификация алгоритма Дейкстры, при которой все минимумы заменены на максимумы неправильно определит путь максимальной длины от узла s до узла 2.

Итак, алгоритм Форда-Беллмана и алгоритм 6.6 легко могут быть модифицированы для вычисления длин максимальных

s-v- *1 путей. Сами же пути с помощью вычисленных Задача о максимальном пути в бесконтурной сети имеет большое практическое значение. Она является важнейшим зве­ном в методах сетевого планирования работ по осуществлению некоторого проекта.

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

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

Здесь мы разберем основные моменты одного из методов се­тевого планирования, называемого методом критического пути (МКП).

Метод был разработан в конце пятидесятых годов Дюпоном и Ремингтоном Рандом для управления работой химических заво­дов фирмы "Дюпон де Немур" (США).

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

Для удобства, в список работ проекта W добавим две фиктив­ные работы s и t, где работа s обозначает начало всего проекта W, а работа t — завершение работ по проекту W. При этом будем считать, что работа s предшествует всем тем работам v W, для которых список ПРЕДШ(v) пуст, иначе говоря, для всех таких работ v W положим ПРЕДШ(v)={s}. Положим далее ПРЕДШ(s) = Ø, ПРЕДШ(t)={v W : v не входит ни в один список ПРЕДШ(w)}, то есть считаем, что работе t предшествуют все те работы, которые могут выполняться самыми последними. Время выполнения работ s и t естественно положить равными нулю; t(s)=t(t)=0.

Весь проект W теперь удобно представить в виде сети G=(V,E,c), где сеть G=(V,E,c) определим по правилам:

1. V=W, то есть множеством узлов объявим множе­ство работ;

2. E={(v,w) : v ПРЕДШ(w)}, то есть отношение предшествования задает дуги в сети;

3. c(v,w)=t(w).

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

Понятно, что сетевой график любого проекта не может содер­жать контуров. Действительно, пусть узлы v_kl,v_k2,...,v_kr=v_k1 обра­зуют контур в сети G. Это означает, что работа v_k2 не может на­чаться раньше, чем будет завершена работа v_k1 работа v_k3 — раньше, чем завершится работа v_k2, и т.д., и, наконец, v_kr = v_k| -— раньше, чем будет завершена работа v_kr-1. Но тогда никакая из работ v_k1...,v_kr никогда не сможет быть выполнена. А каждый ре­альный проект должен допускать возможность его завершения. Следовательно, в сетевом графике нет контуров.

Отсутствие контуров в сети G позволяет пронумеровать рабо­ты проекта W таким образом, чтобы для каждой дуги (v_i, v_j) сети G выполнялось условие i<j (лемма 6.3). Напомним, что осущест­вить такую нумерацию узлов сети G можно с помощью алгорит­ма 6.5 ТОПСОРТ. Поэтому в дальнейшем будем считать, что уз­лы в сети G топологически отсортированы.

Рис 6.6 Проект строительства дома и его сетевой график

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

Обозначим через РВЫП(v) (соответственно PHAЧ(v)) наибо­лее ранний возможный срок выполнения работы v (соответственно наиболее ранний возможный срок начала рабо­ты v). Удобно считать, что РВЫП(s)=PHAЧ(s)=0. Поскольку на­чать выполнять работу v можно только после того, как будут вы­полнены все работы, предшествующие данной работе v, то полу­чим следующие формулы для расчета значений PHAЧ(v) и РВЫП(v):

PHAЧ(v) = max{ РВЫП(w): w ПРЕДШ(v)},

РВЫП(v) = PHAЧ(v) + t(v).

Легко видеть, что значение РВЫП(v) равно длине максималь­ного s-v-пути в сети G. Поэтому, для вычисления значений РВЫП(v) можно использовать алгоритм 6.6 вычисления длин минимальных путей в бесконтурной сети, в котором все миниму­мы заменены на максимумы. При этом значение РВЫП(t) дает наиболее ранний возможный срок завершения всего проекта в целом.

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

АЛГОРИТМ 6.7.

(* расчет наиболее ранних возможных сроков начала и выполне­ния работ *)

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

Результаты: Наиболее ранние возможные сроки начала и выпол­нения работ PHAЧ[v], РВЫП[v], v V.

Здесь, в алгоритме 6.7, узлы сетевого графика s и t обозначены соответственно через v₀ и v_n+1.

Значения РВЫП(v) и PHAЧ(v) для сетевого графика, изобра­женного ранее на рис.6.6, приведены на рис. 6.7. Из найденных значений следует, что этот проект не может быть завершен ранее чем через 20 единиц времени.

Пусть Т — плановый срок выполнения проекта W. Ясно, что Т должно удовлетворять неравенству Т ≥ PBЫП(v_n+1).

Через ПВЫП(v) (соответственно ПНАЧ(у)) обозначим наибо­лее поздний допустимый срок выполнения (начала) работы v, то есть такой срок, который не увеличивает срок Т реализации всего проекта. Например, для работы 3 сетевого графика из рис. 6.6 имеем РНАЧ(3)=12, РВЫП(3)=14, но ясно, что начать работу 3 можно на единицу времени позже, поскольку это не повлияет на срок выполнения всего проекта, а вот задержка в реализации этой же работы на 2 единицы приведет к увеличению срока выполне­ния всего проекта на 1 единицу времени.

АЛГОРИТМ 6.8.

(* Расчет наиболее поздних сроков начала и окончания работ *) Данные: Сетевой график G работ V, заданный списками ПРЕДШ[v], v V, плановый срок окончания проекта — Т. Результаты: Наиболее поздние допустимые сроки выполнения и начала работ ПВЫП[v] и ПНАЧ[v].

Прямо из определений получаем справедливость равенств ПНАЧ(v_n+1)=ПВЫП(v_n+1)=Т. Поскольку произвольная работа v должна быть завершена до начала всех наиболее поздних допус­тимых сроков тех работ w, которым предшествует работа v, то получаем следующие формулы:

ПВЫП(v)=min{ПНАЧ(w): по всем w таким, что ПРЕДШ(w) v},

ПНАЧ(v)=ПВЫП(v)-t(v).

Вычислять значения ПВЫП(v) и ПНАЧ(v) можно, двигаясь по узлам сети G от v_n+1 к v₀. Все детали вычисления названных ха­рактеристик приведены выше в алгоритме 6.8.

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

PE3EPB(v)=ПНАЧ(v)-PHAЧ(v).

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

РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).

Рис 6.7. Численные характеристики сетевого графика

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

Численные значения введенных характеристик сетевых гра­фиков для проекта из рис.6.6 даны на рис. 6.7. Расчеты выполне­ны при Т=20. Критическими работами этого проекта являются работы с номерами 0,1,2,4,6,8, которые и образуют в сети G кри­тический путь.

Исследование сетевых графиков на этом мы завершим. Отме­тим только, что помимо рассмотренных нами характеристик, час­то рассматривают и большое число других, связанных, например, с неопределенностью во времени выполнения работ, с управле­нием ресурсами и т.д. Достаточно обширный и содержательный материал по этому поводу можно найти в книге [8].