Сетевое планирование в условиях неопределенности. Анализ и оптимизация сетевого графика

              Здесь рассчитываем значения Lj в порядке роста номеров:

L0=0; L1 = 2(i=0); L2 =1(i=0);
L3 = max[L0+5, L1+2, L2+2]=5 (i=0) и т.д.

              Затем рассчитываем значения Mi в порядке убывания номеров:

M7=0; M6=4 (k=7); M5=max [2+M6, 7+M7] = 7(k=7);
M4 =4 (k=7); M3 =max[6+M4, 2+M5]=10 (k=4) и т.д.

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

              По информации из колонок 3 или 5 можно выявить критические пути с длиной 15: [ 0 - 1 - 5 - 7 ] и [ 0 - 3 - 4 - 7 ].

              Очевидно, что работы, не лежащие на критических путях, обладают резервами времени - их выполнение при некоторых условиях может быть задержано на какое-то время. Cуществуют 4 вида резервов:

1.      Полный резерв Rij = Tj1 - Ti0 — Tij,

2.      Свободный резерв Rij = Tj0 - Ti0 — Tij,

3.      Независимый резерв Rij =max [ Tj0 - Ti1 - Tij, 0],

4.      Частный резерв Rij = Tj1 - Ti1 — Tij.

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

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

              Для нашего графика на уровне критичности 1 подкритическими будут работы 1-3, 3-5, 5-6, 6-7. Чтобы убедиться в этом, возьмем работу 5-6 и найдем путь максимальной длины, проходящий через нее, по индексам предшествующих и последующих событий. Так событию 5 в пути максимальной длины предшествует событие 1, а ему - событие 0. Событию 6 в таком пути последует событие 7. Длина пути 0-1-5-6-7 равна 14 и задержка на 1 при выполнении работ 5-6 или 6-7 сделает его критическим.

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

              В первом графике все некритические работы имеют одинаковый полный резерв, равный 8. Однако напряженность работ пути 0-1-4 составляет 24 единицы времени на интервале 32, тогда как напряженность работ пути 0-2-3 составляет 2 единицы на 10. Нет сомнения, что работы второго пути можно выполнять с большей "прохладцей", чем первого (отдыхаем 8 дней из 10 и 8 дней из 32 соответственно).

              Во втором графике работы 0-2 и 2-3 имеют резерв 3, а работы 0-1 и 1-4 - резерв 8, но напряженность у них одинакова.

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

              Так для рассмотренного выше сетевого графика выберем некритическую работу 1-3. Обнаруживаем, что через нее проходит путь (максимальной длины) 0-1-3-4-7. Ближайшими соседями на критических путях 0-1-5-7 и 0-3-4-7 будут события 1,7 и 0,3 соответственно. Отсюда находим коэффициент напряженности

K13=max│(T13+T34+T47)/(T15+T57) ; (T01+T13)/T03│=max│12/13 ; 4/5│=12/13

Аналогично получаем:

K35=max│(T03+T35)/(T01+T15) ; (T35+T57)/(T34+T47)│=max│7/8 ; 9/10│= 9/10

K16=11/15

K56=K67=14/15

K02=K23=13/15

K24=12/15

1.6. Сетевое планирование в условиях неопределенности

Продолжительность выполнения работ часто трудно задать точно и

потому в практической работе вместо одного числа (детерминированная

оценка) задаются две оценки — минимальная и максимальная.  Минимальная (оптимистическая)  оценка  tmin(i,j)  характеризует продолжительность  выполнения  работы  при  наиболее  благоприятных обстоятельствах,  а  максимальная (пессимистическая) tmах(i,j)  —  при наиболее  неблагоприятных.  Продолжительность  работы  в  этом  случае рассматривается,  как  случайная  величина,  которая  в  результате реализации  может  принять  любое  значение  в  заданном  интервале. Такие  оценки  называются  вероятностными (случайными),  и  их ожидаемое  начение  toж оценивается  по  формуле (при  бета-распределении плотности вероятности):

tож(i,j)=(3tmin (i,j) + 2t max(i,j)) / 5.

Для  характеристики  степени разброса  возможных  значений  вокруг

ожидаемого уровня используется показатель дисперсии S2:

S2 (i,j) = (t max (i,j) – t min (i,j))2 / 52  = 0,04 ( t max (i,j) – t min (i,j))2

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

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

1)  определить  вероятность  того,  что  продолжительность критического пути tкр не превысит заданного директивного уровня Т;

2)  определить  максимальный  срок  выполнения  всего  комплекса

работ Т при заданном уровне вероятности р.

Первая задача решается на основе интеграла вероятностей Лапласа

Ф(z) использованием формулы: P (t kp < T) = 0,5 + 0,5 Ф(z),

Где нормированное отклонение случайной величины: 

z = (Т - tKp)/S Kp; SKp — среднее квадратическое отклонение, вычисляемое как корень квадратный из дисперсии продолжительности критического пути.

Соответствие между z и симметричным   интегралом   вероятностей  (когда z вычисляется более чем  с одним знаком в дробной части) можно

найти в специальной статистической литературе.

При достаточно большой полученной величине вероятности (более 0,8)  можно  с  высокой  степенью  уверенности  предполагать своевременность выполнения всего комплекса работ.

Для решения второй задачи используется формула: Т = t ож (Lkp )+ z × S kp .

1.7. Проблемы применения систем сетевого планирования

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

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

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

2. Решение экономической задачи

              В таблице указаны оценки времени выполнения некоторого

проекта, данные ответственными исполнителями и экспертами.