6.4. Сітьова модель та сітьовий графік


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 

Загрузка...

Сіть’еа модель комплексу робіт — це наочне відображення взаємозвязку між окремими роботами та послідовності їх вико-

дають певним подіям, пов’язаним із виконанням проекту. Дуги графа відповідають окремим роботам. Вважається, що роботи, які витікають із деякої події, не можна розпочинати раніше, аніж бу-де закінчено всі роботи, які притікають до цієї події. Інколи по-

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

При побудові сітьової моделі слід дотримуватися таких шести правил:

1)         кожна робота повинна бути представлена однією і лише од-нією дугою;

2)         довільні дві роботи повинні розрізнятися принаймні або по-чатковими, або кінцевими подіями;

3)         кожну пару вершин не можна з’єднувати двома дугами;

4)         не повинно бути вершин, крім однієї — початкової, у які не входить жодна дуга;

5)         не повинно бути вершин, крім однієї — кінцевої, 3 яких не виходить жодна дуга;

6)граф не повинен містити замкнених контурів (замкнений контур — це така неперервна послідовність дуг, яка починається та закінчується в одній і тій самій вершині).

Спрямовувати дуги рекомендується зліва направо — так, щоб початкова вершина кожної дуги була розміщеною ліворуч від її кінцевої вершини. Бажано також, щоб дуги сітьової моделі не пе-ретиналися між собою (при побудові складних сітьових моделей це правило є бажаним, але не обов’язковим).

^rr;ri,rrzr°по6удови сітьової моделі [4].

1. Ніякі дві роботи не можуть бути ідентифіковані одними і тими ж подіями.

Це означає, що дільниця сітки вигляду (рис. 6.4) неправильно відтворює дві одночасно завершувані роботи.

робота 1

A   )     (   В   )

робота 2

Рис. 6.4.

У такому випадку дільниця сітки повинна мати фіктивну ро-боту і наступний вигляд (рис. 6.5).

 

 

фіктивна робота

 

Рис. 6.5.

Фіктивна робота не вимагає ні часу, ні ресурсів і вводиться з метою однозначності подій, що зв’язані з завершенням робіт. Та-кий прийом використовується в ситуаціях, коли ро’оти 3 і 4 по-винні наступати за роботою 2, але робота 1 не обовязково пови-нна передувати роботі 4 (рис. 6.6).

 

 

(  !  Г

 

робота 1

 

робота 3

 

 

 

робота 2

 

j Рис. 6.6.

 

робота 4

 

3 дільниці сітки (рис. 6.6) виходить, що роботи 3 і 4 можуть початися тільки після завершення обох робіт 1 і 2.

робота 3

 

 

М   J

робота1

 

 

робота 2

 

робота 4

 

Рис. 6.7.

3 сітки (рис. 6.7) виходить, що робота 3 може початися після роботи 1, а робота 4 — після роботи 2.

 

слідування повинні дотримува-

2. Відношення перебування тися на всій сітці.

Розглянемо дві дільниці сітки (рис. 6.8, рис. 6.9).

 

 

 

 

робота 3

робота 2

робота 4

робота 5

 

Рис. 6.8.

На рис. 6.8 робота 5 наступає за роботами 2 і 4, для яких попе-редньою є робота 3.

 

робота 4

 

т

 

робота 5

робота 2

робота 3

>і     і     і         >і    j

 

Рис. 6.9.

Кожна робота позначається номером подій, які відповідають їх початку і завершенню, робота 2 на рис. 6.9 позначаєтьсяу' —> к, робота 3 — /' -+j.

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

ZumuTn^ шл7хомКИй ВКЛЮЧаЄ КРИТИЧШ Р°б0ТИ, НаЗИВаЄТЬСЯ У невеликих сітках критичний шлях легко визначається, якщо

задані моменти часу настання всіх подій і всі роботи характери-

зуються найбільш раннім (допустимим) моментом початку.

У великих системах критичний шлях — це шлях з нульовим

резервом часу.

Резере часу — це кількість часу, на протязі якого робота може за-тримуватися, не викликаючи збільшення часу завершення проекту.

Завершує побудову сітьової моделі нумерація вершин графа, який відповідає послідовності виконання робіт. Нумерація вер-шин повинна бути такою, щоб зростання номерів відповідало процесу виконання проекту. Це означає, що після нумерації вер-шин для кожної дуги / —»■/■ повинна виконуватися умова: /' < j.

Алгоритм нумераціїеершин:

Крок 1. Присвоїти початковій вершині номер 1.

Крок 2. Присвоїти черговий номер довільній не занумерованій вершині, для якої всі попередні вершини вже занумеровані.

Крок 2 слід повторювати до тих пір, доки усі вершини не бу-дуть занумеровані. Кінцева вершина завжди отримає останній (найбільший) номер.

Приклад 6.2. Нехай маємо комплекс робіт, структурна схема якого показана у табл. 6.3 потрібно побудувати сітьову модель цього комплексу робіт.

Таблиця 6.3

 

Робота            Роботи, які безпосередньо передують заданій      Тривалість виконання, днів

Р-1      —        20

Р-2      —        12

Р-3      —        27

Р-4      Р-1,Р-2           7

Р-5      Р-2, Р-3          14

Р-6      Р-4      13

Р-7      Р-5, Р-6          15

Р-8      Р-5      11

Побудуємо сітьову модель. Насамперед уведемо початкову вершину, яка означатиме початок виконання комплексу робіт. 3 цієї вершини можуть витікати три дуги, які відповідають робо-там Р-1, Р-2 та Р-3, оскільки кожній з них не передує жодна з ро-біт комплексу. Уведемо далі три вершини, які означатимуть за-

кінчення кожної з цих робіт. Тоді початковий фрагмент сітьової моделі матиме такий вигляд, як це показано на рис. 6.10.

 

Рис. 6.10.

Врахуємо, що роботу Р-4 можна розпочинати після закінчення робіт Р-1 та Р-2, а роботу Р-5 — після закінчення робіт Р-2 і Р-3. Тому для зображення робіт Р-4 та Р-5 до сітьової моделі слід до-датково ввести фіктивні роботи Ф-1 та Ф-2. Черговий фрагмент сітьової моделі показано на рис. 6.11.

 

Рис. 6.11.

178

Роботу Р-6 можна розпочинати після закінчення роботи Р-4. Тому початок дуги, яка відповідатиме Р-6, може співпадати з вершиною, яка відповідає закінченню Р-4. Робота Р-7 слідує після закінчення Р-5 та Р-6, а робота Р-8 — після закінчення лише Р-5. Тому для відбиття можливості розпочинати Р-7 по-трібно ввести фіктивну роботу Ф-3. Роботи Р-7 та Р-8 не пере-дують жодній з інших робіт. Отже, їх кінцеві вершина можна об’єднати, що відповідатиме події завершення усіх робіт. По-вністю граф послідовності виконання всіх робіт комплексу на-ведено на рисунку 6.12.

Р-4      ґ  N    P-6     ґ  \

 

P-1

/Ф-1

Ґ  \^P-2        (      ]

ч Ф-2

P-3

P-5 Рис. 6.12.

 

Для графа, наведеного на рис. 6.12 алгоритм нумерації вершин призведе до сітьової моделі, показаної на рис. 6.13. Ця сітьова модель містить 11 дуг та 8 вершин.

 

 

(1 \

Р-5 Рис. 6.13.

Щоб перетворити сітьову модель на сітьовий графік, потрібно на її дугах зазначити тривалості виконання відповідних робіт (наведено у табл. 6.3), після чого для отриманого сітьового гра-фіка (рис. 6.14) доцільно побудувати таблицю з характеристикою усіх його дуг (табл. 6.4).

 

1   \

 

ґ~3      7          5~\   13    /—

14 Рис. 6.14.

Таблиця 6.4

 

Дуга    Робота            Тривалість виконання, днів

(1, 2)   Р-2      12

(1, 3)   P-1      20

(1, 4)   Р-3      27

(2, 3)   фіктивна         0

(2, 4)   фіктивна         0

(3, 5)   Р-4      7

(4, 6)   Р-5      14

(5, 7)   Р-6      13

(6, 7)   фіктивна         0

(6, 8)   Р-8      11

(7, 8)   Р-7      15

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

Часовими характеристиками подій — вершин сітьового графі-ка —    є  ранні  та  пізні  терміни  настання   відповідних  подій,

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

 

£■(1) = 0,   E\j) = max \E(l) + t(i, j)},

i-(i,jhu

 

J

 

2,3,

 

П

 

(6.7)

 

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

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

If, j)eU - — позначення такої дуги, яка виходить з вершини / та входить уу'-ту вершину графа;

Примітка: дугу і —> j сітьового графіка, яка виходить з вершини з номером і та за-кінчується у вершині з номерому', зручно позначати також через (i,f).

t(i,j) — тривалість виконання роботи / —>j\ Е(і) — ранній термін настання і-ої події, відповідно; Е (/) — ранній термін настанняу'-ої події (i, j = 1, 2,..., п). Тривалість виконання комплексу робіт Т* дорівнює ранньому терміну настання його кінцевої події. Таким чином,

7* = Е(п).       (6-8)

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

L(n) = Т*,   L\i) =  min \L[j) - t(i, j)},   j = n -1, n - 2,..., 1,       (6.9)

f-(i,jhu

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

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

R(i)= L[i) -Е{ї), і = 1, 2,..., п.  (6.10)

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

R(j*) = 0, якщо j* —критичнаподія.           (6.11)

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

Ранні терміни настання подій розшукуються за сітьовим гра-фіком методом обчислень у прямому порядку -f- від початкової до кінцевої події:

£■(1) = 0,

Е(1) = Е(\) + t(\, 2) = 0 + 12,

£■(3) = max{£"(1) + t(\, 3); £(2) + t(2, 3)} = max {0 + 20; 12 + 0} = 20,

£(4) = max {£(1) + t(\, 4); £(2) + t(2, 4)} = max {0 + 27; 12 + 0} = 27,

£(5) = £(3) + t(3, 5) = 20 + 7 = 27,

£(6) = £(4) + t(4, 6) = 27 + 14 = 41,

£(7) = max {£(5) + t(5, 7); £(6) + t(6, 7)} = max {27 + 13; 41 + 0} = 41,

£(8) = max {£(6) + t(6, 8); £(7) + t(J, 8)} = max {41 + 11; 41 + 15} = 56.

Тривалість виконання комплексу робіт співпадає з раннім те-рміном настання останньої — восьмої — події. Отже,

Т* = 56.

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

Д8) = Т* = 56,

Д7) = Д8) - 7(7,8) = 56 - 15 = 41,

Д6) = min {Д8) - 7(6,8); Д7) - 7(6,7)} = min {56 - 11; 41 - 0} = 41,

Д5) = Д7) - 7(5,7) = 41 - 13 = 28,

Д4) = Д6) - 7(4,6) = 41 - 14 = 27,

ДЗ) = Д5) - 7(3,5) = 28 - 7 = 21,

L(2) = min {Д4) - 7(2,4); ДЗ) - 7(2,3)} = min {27 - 0; 21 - 0} = 21,

Д1) = min {Д4) - 7(1,4); ДЗ) - 7(1,3); Д2) - 7(1,2)} = min {27 - 27; 21 -- 20; 21 - 12} = 0.

Покажемо терміни настання подій на сітьовому графіку (рис. 6.15). На цьому рисунку також виділено вершини, які від-повідають критичним подіям (для таких подій ранній термін на-стання Е співпадає з їх пізнім терміном настання L).

 

21

20

 

 

28                    41

27       

            41

 

 

Рис. 6.15. На рисунку 6.15 для кожного комплексу робіт надано ранній

(критичні події 1, 4, 6,

(Е) та пізні (L) терміни настання подій 7 та 8 виділено).

Ранні та пізні терміни настання подій, а також їхні резерви ча-су наведено у табл. 6.5.

Таблщя 6.5

 

По-

діяг'     Ранній термін

настання

Е(і)      Пізній термін настання        Резерв часу = Z, (г) - Дї)       Примітка

1          0          0          0          Критична подія

2          12        21        9         

3          20        21        1         

4          27        27        0          Критична подія

5          27        28        1         

6          41        41        0          Критична подія

7          41        41        0          Критична подія

8          56        56        0          Критична подія, її ранній термін настання визначає тривалість виконання усьо-го комплексу робіт

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

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

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

М(і, j) = L(j) —Е(і) - t(i, j),     (6-12)

де: L(j) — пізній термін настанняу'-ї події, яка є кінцевою для ро-

боти(/,т);

Е(ї) — ранній термін настання г-ої події, яка є вихідною для

цієї роботи;

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

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

M(i*,j*) = 0 для всіх (г*,у*)є£/*,      (6.13)

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

Шлях від початкової вершини до кінцевої, який складається лише із критичних робіт, £азиває?ься критичним шляхом сі-тьоеого графіка. Довжина критичного шляху збігається із трива-лістю виконання усього комплексу робіт Т*.

Примітка. Сітьовий графік може мати декілька різних крити-чних шляхів. Довжина кожного з них також дорівнює тривалості

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

Щі, j) = E(j) - Е(і) - t(i, j).        (6-14)

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

Р(і, j) = max {0; E(j) - L(i) - t(i, j)}.     (6.15)

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

М(і, j) > N(i, j)>P(i, j)>0.        (6.16)

Приклад 6.4. Зведемо разом усі часові характеристики робіт (дуг) сітьового графіка, наведеного на рис. 6.16. Такими характе-ристиками роботи (/', j) є:

•          тривалість — t(i, j);

•          ранній термін початку — раніше якого розпочати роботу неможливо — Е(і)',

•          пізній термін закінчення — перевищення якого призведе до затримки із завершенням проекту в цілому — L(j);

•          yci резерви часу — М(і, j), N(i, j) та Р(і, j), які розраховують-ся за формулами (6.12), (6.14), (6.15).

ля роботи (3, 5) маємо:

t (3, 5) = 7; Е (3) = 20; L (5) = 28;

М(3, 5) = 28 - 20 - 7 = 1; N (3, 5) = 27 - 20 - 7 = 0;

Р (3, 5) = max {0; 27 - 21 - 7} = 0.

Резерви часу усіх дуг сітьового графіка та критичний шлях 1 ^ 4 ^ 6 ^ 7 ^ 8 показано на рис. 6.16. Часові характеристики усіх робіт проекту, що розглядається, наведено у табл. 6.6.

На сітьовому графіку комплексу робіт застосовано позначен-

 

ня: ранній та пізній терміни настання подій

 

;

 

резерви часу робіт: @й ^, де М— повний резерв; N — вільний; Р — незалежний;

роботи критичного шляху (1—4; 4—6; 6—7; 7—8) виділено.

 

21

 

 

28                    41

27       

            41

 

 

 

Рис. 6.16.

 

Таблщя 6.6

 

 

Робота

(і)         Трива-лість    Ранній

термін

настання

Е(і)      Пізній те-рмін за-кінчення

m         Резерви часу  Примітки

 

           

           

           

            повний M(i, j)            вільний          не залежний 

 

(1, 2)   12        0          21        9          0          0         

(1, 3)   20        0          21        1          0          0         

(1, 4)   27        0          27        0          0          0          критична

(2, 3)   0          12        21        9          8          8          фіктивна

(2, 4)   0          12        27        15        15        6          фіктивна

(3, 5)   7          20        28        1          0          0         

(4, 6)   14        27        41        0          0          0          критична

(5, 7)   13        27        41        1          1          0         

(6, 7)   0          41        41        0          0          0          фіктивна, критична

(6, 8)   11        41        56        4          4          4         

(7, 8)   15        41        56        0          0          0          критична

Завершений сітьовий графік (рис. 6.16) і таблиці про часові характеристики подій та робіт (табл. 6.5, 6.6) є зручними інстру-ментами при обговоренні та затвердженні календарного плану і подальшому контролі за виконанням проекту.