Сітьове планування з урахуванням вартості робіт та умов ризику щодо тривалостей операцій

     Після побудови сітьового графіка комплексу  робіт обчислюють часові характеристики його вершин і дуг, тобто часові характеристики подій та робіт проекту. 

1.2. Алгоритм задачі сітьового планування

     Графічний спосіб побудови і аналізу плану робіт є зручний у випадку коли комплекс, який ми плануємо не є дуже складний. На практиці часто зустрічаються комплекси робіт, які складаються з великої кількості елементів. Звичайно, в таких випадках  використання сітьового графіка не є оптимальним рішенням, адже втрачається наочність і чіткість. Для аналізу і вдосконалення плану робіт в таких випадках використовують комп’ютери .

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

     Розглянемо  один з можливих алгоритмів.

     Перш  за все виконується впорядкування структурної таблиці. При цьому роботи роз приділяються на ранги по ознаці числа і рангу робіт, на які вони опираються.   
 

     

      Запишемо у вигляді математичних формул систему зв’язків:

                                                                  T_i = τ_i + t_{i   ,}                                                                              (1)

де, τ_i – мінімально можливий термін початку роботи а_i ;

      T_i –мінімально можливий термін її закінчення;

       t_i – час виконання роботи а_i .

     За  допомогою даного позначення можна  записати всі зв’язки між роботами комплексу. Нехай робота а_i опирається на роботи а_j ,а_e ,а_k  . Тоді робота а_i не може розпочатися раніше, ніж завершиться та з робіт, яка завершується останньою:

                                                          τ_i =max{ T _j ,T_e ,T _k }                                           (2)

     Застосовуючи  такі формули до всіх робіт з комплексу, ми знайдемо всі моменти завершення робіт T_i  і, врешті решт, мінімальний термін виконання всього комплексу робіт T .

     В нашому випадку вираховуємо величини  τ_i і T_i  для всіх робіт. Для робіт першого рангу а₁ , а₂ , а₃ маємо:   

                                                            τ₁=0   ,   T₁= t₁;                                                   (3)

                                                            τ₂=0   ,   T₂= t₂;   

                                                            τ₃=0   ,   T₃= t₃.

     Робота  а₄ опирається на роботи а₁ ,а₂ і вона може розпочатись в момент τ₄ , коли закінчиться остання робота з а₁ , а₂ :

                                                        τ₄=max { T ₁ ,T₂}.                                                  (4)

     Момент закінчення роботи а₄:

     T₄= τ₄ + t ₄ .

     Аналогічно  для решти робіт:

     

     τ₅=max { T ₁ ,T₃ ,T₄ };

     T₅= τ₅ + t ₅ ;

     τ₆=max { T ₂ ,T₃ };

     T₅= τ₅ + t ₅ ;

     τ₇=max {T ₄ };

     T₇= τ₇ + t ₇ ;

     τ₈=max { T ₄ ,T₅ };  (5)

     T₈= τ₈ + t ₈ ;

     τ₉=max { T ₄ ,T₅ ,T₆ };

       T₉= τ₉ + t ₉ ;

     τ₁₀=max { T ₈ ,T₉ };

       T₁₀= τ₁₀ + t ₁₀ ;  

     Таким чином ми знайшли  моменти початку  τ_i і закінчення T_i всіх робіт. Термін закінчення всього комплексу робіт дорівнює максимальному із всіх термінів закінчення:                                T= max { T ₁ ,T₂ ,…, T ₁₀ }.                                           (6)

     Щоб знайти критичні роботи ( а значить  і критичний шлях ), треба зробити  наступне: по-перше, знайти роботу а_i, для якої час закінчення T_i = T максимальний; ця робота буде критичною. Потім серед формул (5) знайти ту, яка визначає момент початку цієї роботи τ_i . Величина τ_i представлена у вигляді максимуму якихось моментів T _j ,T_e ,T _k …;треба знайти той з них, при якому досягається максимум. Та робота а_m,при якій досягається цей максимум буде другою роботою з кінця на критичному шляху. Так само визначають третю і т.д. роботи. Таким чином, критичною буде робота з найпізнішим терміном закінчення і всі роботи, на час закінчення яких досягається максимум у визначенні терміну початку наступної критичної роботи. Звичайно, максимум в деяких із формул (5) можна отримати не на одній ,а на декількох роботах; відповідно на кожному кроці ми можемо отримати не один, а кілька критичних шляхів [2, 306] .  

1.3. Часові характеристики подій та тривалості виконання комплексу робіт.

     Часовими  характеристиками подій – вершин сітьового графіка – є ранні та пізні терміни настання відповідних подій, пов’язаних із виконанням проекту, та резерви часу цих подій [4, 180].

     Ранній  термін настання події – це такий момент часу, коли буде завершено усі роботи, що обумовлюють цю подію. Ранні терміни настання подій обчислюється рекурентно за формулами:

                                                    (7)

де n – загальна кількість вершин сітьового графіка;

  U – множина його дуг;

  (i,j)єU – позначення такої дуги, яка виходить з вершини і та входить у j-ту вершину графа ;

  - тривалість виконання роботи i →j ;

   E(i) – ранній термін настання і -ої події;

  E(j) – ранній термін настання j–ої події ( i, j =1,2,…,n).

     Тривалість  виконання комплексу робіт Т* дорівнює ранньому терміну настання його кінцевої події. Таким чином,

           Т*=Е(n).      (8)

     Пізній  термін настання події – це момент часу, перевищення якого при настанні цієї події призведе до затримки з виконання проекту в цілому. Пізні терміни настання подій обчислюється рекурентно за формулами:

                                      (9)

де, як і раніше, i та j – номери вершин сітьового графіка; ( ) – пізній термін настання і -ої ( j–ої) події (i, j =1,2,…,n).

     Резерв  часу R(i) події i  визначається як різниця між її пізнім та раннім термінами настання :

                                                                                     (10)

     Події, які  не допускають аніякої затримки з їх настання, називаються критичними. Для кожної критичної події її резерв часу дорівнює нулю:

             якщо j* - критична подія.      (11)

     Після обчислення часових характеристик  подій визначають часові характеристики кожної з робіт проекту [4, 183].

     За  аналогією до подій усі роботи проекту також розподіляються на критичні та некритичні. Критичні роботи не мають резерву часу на виконання . Навпаки, некритичні роботи мають певний резерв часу, тобто деяке запізнення з їх завершенням не призводитиме до затримки із виконанням проекту в цілому. Серед часових характеристик робіт розрізняють повний, вільний та незалежний резерви. Усі ці резерви обчислюються на основі даних про ранні та пізні терміни настання відповідних подій.

     Повний  резерв часу M(i, j) роботи (i,j) – це максимально можлива затримка у виконанні цієї роботи, яка не призведе до затримки із виконанням усього проекту за умов, що тривалість інших робіт не змінюватиметься:

     M(i,j)=L(i,j)-E(i)-t(i,j),

де L(j)- пізній термін настання j-ої  події, яка є кінцевою, для роботи (i,j);

    E(i)- ранній термін настання і-ої події, яка є вихідною для цієї роботи;

   t(i,j )- нормативна тривалість виконання відповідної роботи.

          Для кожної критичної роботи  її повний резерв часу дорівнює  нулю:

                                 M(i*,j*)=0 для всіх (i*,j*)єU*                                            (12)

де  U* - множина усіх критичних робіт проекту.

     Повний  резерв часу роботи дорівнює резерву  максимального із шляхів, що проходить  через цю роботу. Цей резерв можна  використовувати при виконанні даної роботи, якщо її початкова подія завершиться в самий ранній період і можна допустити завершення кінцевої події в її самий пізній період.

     Важливою  властивістю повного резерву  часу роботи є те, що він належить не тільки даній роботі, але і  всім повним шляхам, які проходять через неї. При використанні повного резерву часу тільки для однієї роботи резерви часу решти робіт, які належать максимальному шляху, що проходить через неї, будуть повністю вичерпані. Резерви часу робіт, які лежать на інших (не максимальних по довжині) шляхах, які проходять через цю роботу, скоротяться відповідно на величину використаного резерву [5,304].

     Вільний резерв часу N(i,j) роботи (i,j)- це така максимально можлива затримка із виконанням цієї роботи, яка не впливає на терміни виконання усіх наступних робіт:

                                                               N(i,j)=E(j)-E(i)-t(i,j).                                            (13)  Вільний резерв часу можна використовувати для зниження ризику, який може виникнути по ходу виконання робіт. Якщо планувати виконання робіт по ранніх термінах їх виконання і завершення, то завжди при необхідності буде можливість перейти на пізні терміни початку і закінчення робіт [5, 306] .

     Незалежний  резерв часу P(i, j) роботи (i, j) характеризує таку максимально можливу затримку із виконанням цієї роботи, яка не впливає на терміни виконання усіх інших робіт проекту :