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

Сітьова модель комплексу робіт — це наочне відображення взаємозв'язку між окремими роботами та послідовності їх вико­нання. Сітьову модель будують у вигляді орієнтованого графа. Елементами графа є вершини та дуги. Вершини графа відпові­дають певним подіям, пов'язаним із виконанням проекту. Дуги графа відповідають окремим роботам. Вважається, що роботи, які витікають із деякої події, не можна розпочинати раніше, аніж бу­де закінчено всі роботи, які притікають до цієї події. Інколи по ряд з реальними до сітьової моделі необхідно включити фіктив­ні роботи. Фіктивні роботи не вимагатимуть витрат часу або ре­сурсів, а використовуються лише для того, щоб показати, що пе­вна подія (група подій) не може статися раніше, аніж відбудеться деяка інша подія (група подій).

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

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

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

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

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

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

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

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

Наведемо деякі поради щодо побудови сітьової моделі.

Правило побудови сітки:

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

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

Робота 1

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

Рис. 10.2

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

Рис. 10.3

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

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

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

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

Рис. 10.5

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

Рис. 10.6

Кожна робота позначається номером подій, які відповідають їх початку і завершенню, робота 2 на рис. 10.6 позначається j k, робота 3 — i j.

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

У невеликих сітках критичний шлях легко визначається, якщо задані моменти часу настання всіх подій і всі роботи характери­зуються найбільш раннім (допустимим) моментом початку.

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

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

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

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

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

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

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

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

Табл. 10.1

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

Рис. 10.7

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

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

Рис. 10.8

Рис. 10.9

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

Рис. 10.10

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

Рис. 10.11

Табл. 10.2

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