Сетевое планирование и управление в организациях

 

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

      Для работ, начинающихся с номера «1», предшествующих работ нет. Для работы, начинающейся на номер «k», просматриваются все верхние строчки второй графы таблицы и отыскиваются строки, оканчивающиеся на этот номер. Количество найденных работ записывается во все строчки, начинающиеся с номера «k». Например, для работы (5,8) в гр. 1 поставим цифру 2, так как в гр. 2 на номер 5 оканчиваются две работы: (2,5) и (4,5).

      Заполнение  таблицы начинается с расчета  раннего срока  начала работ. Для  работ, имеющих цифру «ноль» в  первой графе, в гр. 4 также заносятся  нули, а их значение в гр. 5 получается в результате суммирования гр. 3 и 4.  В нашем случае таких работ только одна — (1, 2), поэтому в гр. 4 в соответствующей ей строке проставим 0, а в гр. 5 — 0+6 = 6. 

      Для заполнения следующих строк гр.4, т. е. строк, начинающихся с номера 2, просматриваются заполненные строки гр.  5, содержащие работы, которые оканчиваются на этот номер, и максимальное значение переносится в гр. 4 обрабатываемых строк. В данном  случае такая работа лишь одна (1, 2), о чем  можно судить по гр. 1. Цифру 6 из гр. 5 переносим в гр.4 для всех работ, начинающихся с номера 2, т. е. в три последующие строки с номерами (2, 3), (2, 4), (2, 5). Далее для каждой   из этих работ путем   суммирования их значений гр. 3 и 4 сформируем значение гр.5.: 

      t_po(2.3) = 5 + 6 =11

      t_po(2.4) = 3 + 6 = 9 

      Этот  процесс повторяется до тех пор, пока не будет заполнена последняя строка таблицы. 

      Графы 7 и 6 заполняются «обратным ходом», т. е. снизу вверх. Для этого просматриваются строки, оканчивающиеся на номер последнего события, и из гр. 5 выбирается максимальная величина, которая записывается в гр. 7 по всем строчкам, оканчивающимся на номер последнего события (см. формулу tn(N) = tp(N)). В нашем случае t(N) = 33. Затем для этих строчек находится содержимое гр. 6 как разность между гр. 7 и 3 Имеем: 

      t_po(10.11) = 33 - 9 = 24. 
 

      Далее просматриваются строки, оканчивающиеся на номер события, которое непосредственно предшествует завершающему событию (10). Для определения гр. 7 этих строк (работы (5,10), (7,10), (8,10), (9,10)) просматриваются все строчки гр. 6, лежащие ниже и начинающиеся с номера 10. 

      В гр. 6 среди них выбирается минимальная  величина, которая переносится в гр. 7 по обрабатываемым строчкам. В нашем случае она одна — (10,11), поэтому заносим  во все строки указанных работ цифру «24». Процесс повторяется до тех пор, пока не будут заполнены все строки по гр. 6 и 7. 

      Содержимое  гр. 8 равно разности гр. 6 и 4 или гр. 7 и 5 . Гр. 9 проще получить, воспользовавшись формулой. 

      Учитывая, что нулевой резерв времени имеют  только события и работы, которые принадлежат критическому пути, получаем, что критическим является путь

      LKp = (1,2,4,5,10,11), а t_кр = 33 дня. 

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

      K_H=(i,j)=t(Lmax)-t_kp  /t_kp - t_kp`= 1- R<sub>n</sub> - R<sub>n</sub> (i,j)/ t<sub>kp</sub> - t<sub>kp</sub>` 

      где t(L max) — продолжительность максимального пути, проходящего через работу (i,j); 

      t_kp`— продолжительность отрезка рассматриваемого пути, совпадающего с критическим путем. 

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

      •   напряженные (K_H(i,j) > 0,8); 

      •   под критические (0,6 < K_H(i,j) < 0,8);  

      •   резервные ( K_H (i,j) < 0,6). 

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

      При расчете этих показателей целесообразно  пользоваться графиком СМ. Итак, для  работ критического пути (1,2), (2,4), (4,5),(5,10),(10,11) Kн=1. Для других работ: 

      Kн(2,3) = 1 - (6: (33 - (6 + 9)) = 1- 0,33 = 0,67

      Kн (4,9) - 1 - (5: (33 - (6 + 3 + 9)) = 1 - 0,33 = 0,67

      Kн (5,8) = 1 - (2: (33 - (6 + 3 + 6 + 9)) = 1 - 0,22 = 0,78 и т.д. 

      В соответствии с результатами вычислений Кн для остальных работ, которые  представлены в последней графе табл.1, можно утверждать, что оптимизация СМ возможна в основном за счет двух резервных работ: (6,11) и (2,5). 
 
 
 
 
 
 
 
 
 
 

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

 

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

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

      t_ож(i,j)=(3t_min (i,j) + 2t _max(i,j)): 5. 

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

      S² (i,j) = (t _max (i,j) – t _min (i,j) ² :5 ²  =

      = 0.04 ( t _max (i,j) – t _min (i,j)² 

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

      Кроме обычных характеристик СМ, при  вероятностном задании продолжительности работ можно решить две дополнительные задачи: 

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

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

      Первая  задача решается на основе интеграла  вероятностей Лапласа Ф(г) использованием формулы: 

      P (t _kp < T) = 0,5 + 0,5 Ф(z), 

      Где нормированное отклонение случайной  величины: z = (Т - t_Kp)/S _Kp;

      S_Kp — среднее квадратическое отклонение, вычисляемое как корень квадратный из дисперсии продолжительности критического пути. 

      Соответствие  между z и симметричным   интегралом   вероятностей  приведено в табл. 2. Более точно соответствие между этими величинами (когда z вычисляется более чем  с одним знаком в дробной части) можно найти в специальной статистической литературе.

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

      Для решения второй задачи используется формула: 

      Т = t _ож (L_kp )+ z *S _kp 
 

Таблица 2. Фрагмент таблицы стандартного нормального распределения 

 
 

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

3. Построение  сетевой модели

 
 
 

      Структура сетевой модели и оценки продолжительности работ (в сутках) заданы в табл. 3. Требуется: 

      а) получить все характеристики СМ; 

      б) оценить вероятность выполнения всего комплекса работ за 35 дней, за 30 дней; 

      в) оценить максимально возможный  срок выполнения всего комплекса работ с надежностью 95% (т. е. р = 0,95). 

      Три первые графы табл. 3. содержат исходные данные, а две последние графы  — результаты расчетов по формулам Так, например, 
 
 

      t_ож(i,j)=(3t_min (i,j) + 2t _max(i,j)): 5

      t_ож(1,2)=(3*5 +2*7,5):5 =6

      t_ож(2,3)=(3*4 +2*6,5):5 =5 

      S² (i,j) = (t _max (i,j) – t _min (i,j) ² :5 ²  =

      = 0.04 ( t _max (i,j) – t _min (i,j)² 

      S² (1,2) = (7,5 - 5) ² :25  =0,25

      S² (2,3) = (6,5 - 4) ² :25  =0,25