7. МЕТОД НЕЧЕТКОГО КРИТИЧЕСКОГО ПУТИ

Опишем классический (четкий) метод критического пути (critical path method - CPM). Легко видеть, что продолжительность проекта определяется путем максимальной длины, называемым критическим путем. Операции, принадлежащие критическому пути, называются критическими. Остальные (некритические) операции имеют резерв времени, характеризуемый максимальной задержкой операции, при которой продолжительность проекта не изменяется. Критические операции имеют нулевой резерв. Приведем соответствующие формулы.

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

Предположим, что выполнение комплекса операций (проекта) начинается в нулевой момент времени. Обозначим Q0 - множество событий, не требующих выполнения ни одной из операций, то есть входы сети; Qt - множество событий, непосредственно предшест-

вующих событию i, то есть множество вершин j сети, для которых существует дуга (j; i). Положим

t- = 0, i e Qd; t- = max (t- + j), i e V \\ Q0.

jeQi

Величина t- называется ранним моментом (временем) свершения

i-го события и характеризует время, раньше которого это событие произойти не может.

T = max t-

ieV

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

Поздним моментом t+ свершения события называется максимальное время его наступления, не изменяющее продолжительности проекта. Обозначим Ri - множество событий, непосредственно следующих за событием i, то есть множество вершин j сети, для которых существует дуга (i;j). Вычислим для каждой вершины- события i длину li максимального пути от этой вершины до выхода сети - события, заключающегося в завершении всего комплекса операций (для выходов сети считаем соответствующие величины равными нулю):

li = max (lj + tj), i e V.

jeRi

Положим t~+ = T - li, i e V.

Полным резервом Dti события i называется разность между его поздним и ранним моментами свершения, то есть

Dti = t+ - t-, i e V.

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

(имеется нечеткая информация относительно продолжительностей операций) неопределенность.

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

Сначала обобщим рассмотренную модель на случай интер-вальной неопределенности относительно продолжительности операций, а именно, будем считать, что t- е [ t- , t— ], i, j е V.

Тогда ранние моменты t- свершения событий принадлежат

отрезкам А- = [ t--, t-+ ], где

t-- = t- = 0, i е Q0; t- = max (t-- + t-

j^-Qi

t- = max (t-+ + t +), i е V \\ Q0.

Длина критического пути принадлежит отрезку Л = [TT+], где

T- = max t--, T = max t-+.

IgV IgV

По аналогии с (3), вычислим для каждой вершины-события i

оценки [/Г; l+ ] длины максимального пути от этой вершины до

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

/: = max (/- + t- ), /+ = max (l+ + t+), i е V. Положим t+- = T- - lT, t++ = T+ - li, i е V.

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

+

(8) D t- = t+ - t-, D t+ = t+ - t+, i e V.

В интервальной модели, в отличие от «классической», нельзя однозначно сказать является ли событие критическим.

В первый класс попадают события, для которых имеет место полная определенность, то есть, события, для которых обе границы (8) равны между собой и равны нулю. Эти операции можно с полным основанием назвать критическими.

Во второй (промежуточный по степени «критичности») класс попадают события, для которых нижняя граница отрезка полных резервов равна нулю, а правая строго положительна. Такие события могут в рамках существующей неопределенности оказаться критическими. Условно назовем их полукритическими.

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

Рассмотрим иллюстративный пример.

Табл. 4. Параметры операций в примере 3

Операции Минимальная Максимальная продолжительность продолжительность

Пример 3. Пусть имеется сеть, приведенная на рисунке 8 с интервалами продолжительностей операций, приведенными в таблице 4. В таблице 5 приведены параметры событий, рассчитанные соответствии с формулами (5)-(8).

Рис. 8. Сеть в примере

\r\n0-1 1 3\r\n0-2 4 7\r\n0-3 1 3\r\n1-3 1 3\r\n1-4 5 6\r\n2-4 2 4\r\n3-4 4 6\r\nТабл. 5. Параметры событий в примере 3

\r\nСобытие Г l- l+ t++ Dt- Dt+\r\n0 0 0 6 12 0 0 0 0\r\n1 1 3 5 9 1 3 0 0\r\n2 4 7 2 4 4 8 0 1\r\n3 2 6 4 6 2 6 0 0\r\n4 6 12 0 0 6 12 0 0\r\nВидно, что при использовании нижних границ интервалов продолжительностей операций критическими являются все события и длина критического пути T ~ = 6, а при использовании верхних границ - критическим является путь 0-1-3-4 длины T = 12. Следовательно, в условиях существующей неопределенности события 0, 1, 3 и 4 являются критическими, а событие 2 - полукритическим.

Отметим, что в предельном случае интервальной неопределенности, то есть при полной информированности, когда отрезки [ ti}-, tj ] - суть точки, i, j е V, выражения (5)-(8) переходят в соответствующие выражения (1)-(4).

Обобщим теперь рассмотренную модель интервальной неопределенности на нечеткий случай, при котором относительно про- должительностей операций имеется нечеткая информация j~ (tjj) ,

где j~ (•) : ® [0; 1] - функция принадлежности нечеткой про-

tij

должительности операции (i, j), i, j е V.

Нечеткая информация относительно продолжительности операций может быть получена от экспертов в ситуации, когда проект и каждая операция являются уникальными (например, научные,

организационные и др. проекты) и отсутствуют как нормативы, так и статистические данные.

В соответствии с принципом обобщения [14, 64, 94] функция принадлежности нечеткого раннего времени свершения i-го события, i e V, имеет вид (ранние времена свершения событий - входов сети являются четкими равны нулю):

m (x) = max min [ min (m~ (x.-,)); m(x.) ].

ti {(Xji), ш,Xj | max(Xj+x., )= x} jeQ, j J tj J

jeQi

Функция принадлежности нечеткого времени завершения проекта (нечеткой длины критического пути) есть

m~(T) = max min (m (x.)).

1 {(X, ), ieV | min(x, )=T} jeV \'j \'

jeV J

Нечеткие длины максимального пути от вершины i e V до выхода сети (соответствующие длины для событий - выходов сети - являются четкими и равны нулю) имеют функцию принадлежности

m~ (x) = max min [min( m~. (x,,- )); m~ (x, )].

li {(x,j), jeRt | max (x. +x, )=x} jeR, tj J lj J

jeRi

Функции принадлежности нечетких поздних времен свершения событий имеют вид:

m~+ (x) = max min [ m~(T); mx)], i e V.

ti {(T, x, ) | T - xt = x} li

Функции принадлежности нечетких полных резервов событий имеют вид:

mD~ (x) = max min [ m~ + (Уг) ; m~- (x,)], i e V.

h {( Уi, xi )|y, - xi = x} H h

Величину m, = mD~ (0) e [0; 1] можно интерпретировать как

степень принадлежности i-го события критическому пути, i e V.

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

Отметим, что в частном случае нечеткой неопределенности -

при интервальной неопределенности (то есть когда m~ (t,) = 1 и

tij ij

Supp m(tj) = [ t-, tj ], (i, j) e E) выражения (9)-(13) переходят в соответствующие выражения (5)-(8).