Елементи мережних графіків і способи їх побудови

Основними елементами мережних графіків є роботи (операції) і події. Термін "робота" застосовується в широ- кому сенсі і може мати такі значення: а) робота у прямому розумінні слова (наприклад, термообробка частин кокілю), що вимагає витрат праці, матеріальних ресурсів і часу; б) очікування, що не вимагає витрат праці і матеріальних ре- сурсів, але що займає якийсь час (наприклад, охолодження заготовки після термообробки); в) залежність – зв'язок між двома або більше подіями, що не вимагає витрат праці, ма- теріальних ресурсів і часу, але вказуючи, що можливість

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

Тривалість виконання робіт, як правило, вимірюється в одиницях часу і показується під або над стрілкою, що поз- начає певну роботу.

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

Всяка робота в мережі поєднує дві події: попередня їй (є для неї початковою подією) і наступна за нею (кінцева подія). Якщо дати кожній події номер, то будь-яку роботу можна закодувати подіями.

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

Тривалість події в часі завжди дорівнює нулю. При цьому слід пам'ятати, що подію визначає стан, а не процес.

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

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

При складанні мережних графіків необхідно дотримуватися таких правил:

- необхідно прагнути, щоб максимальна кількість робіт, незалежних одна від одної, виконувалися паралельно;

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

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

- якщо які-небудь роботи можуть бути початі після часткового виконання попередньої до них роботи (роботи 1-2 на рис. 1 г), то її слід розбити на ряд послідовно виконуваних робіт, результати яких необхідні і достатні для початку наступних за ними робіт (рис. 1 д);

- у мережі не повинно бути подій, з яких не виходить жодної роботи, якщо тільки цієї події немає для даного завершального графіка;

- у мережі не повинно бути подій, в які не входить жодна робота, якщо тільки ці події не є початковими;

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

 

Рисунок 1 – Позначення на мережних графіках:

а, в, г – неправильно; б, д – правильно

 

Параметри мережних моделей

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

Визначення параметрів мережних графіків подані нижче і ілюстровані прикладом (рис. 2):

- тривалість (довжина) шляху дорівнює сумі тривалості робіт, його складових і позначається T (Li ) .

Для прикладу на рисунку 2:

- всього на цьому рисунку можна знайти сім шляхів різної довжини;

- критичний шлях – шлях, що має найбільшу тривалість, позначається Ткр .

 

 

Рисунок 2 - Мережний графік

 

Для графіка на рисунку 2

 

Ткр (1,2,7,9,11,12,13,14) = 7 + 3 + 5 + 5 + 7 + 10 + 2 = 39 .

У мережах іноді буває декілька критичних шляхів, що мають однакову тривалість; ранні строки початку і закінчення робіт – найранніший термін початку роботи, визначений через Трнi, і найранніший термін закінчення роботи, що позначається Tpoi .

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

Ранній термін закінчення роботи дорівнює її ранньому терміну початку плюс її тривалість Троi = Трнi + Тi .

Робота 8 – 12 на рисунку 2 може початися, якщо бу- дуть виконані всі попередні нею роботи, що лежать на шляхах L 3(1,3,8) .

Тривалість цих шляхів T(L1) = 17 , T (L2) = 11; T(L3) = 9 , отже, ранній термін початку роботи 8–12 Трн (8 - 12) = 17 .

 

Ранній термін закінчення роботи 8–12:

Тро (8 - 12) = Трн (8 - 12) + Т(8 - 12) = 17 + 7 = 24 ;

Пізні терміни початку і закінчення робіт – найпізніший з можливих термінів початку роботи i, що позначається через Тпнi і найпізніший термін закінчення роботи, що позначається Тпоi  Оскільки основним завданням служб є в найкоротший строк провести той або інший процес виготовлення, тобто виконати останню роботу в мережі якомога раніше, то найбільш пізній допустимий термін її закінчення буде дорівнювати найбільш ранньому з можливих термінів закінчення. Отже, для останньої роботи Тпо = Тро  Пізні терміни закінчення решти всіх робіт у мережному графіку розраховуються виходячи з того, щоб виконувалася ця умова - вони дорівнюють різниці між тривалістю критичного шляху і сумарної тривалості робіт, що лежать на максимальному із шляхів, що ведуть від даної роботи до завершальної роботи мережного графіка. Якщо позначити максимальний шлях, наступний за роботою i через, то отримаємо Tпоi = Ткр - Т(Lic )max. Очевидно, що термін пізнього початку будь-якої роботи мережі дорівнює різниці терміну пізнього закінчення і тривалості виконання даної роботи, тобто Тпнi = Тпоi - Тi . Наприклад, для роботи 2–7 графіка на рисунку 2 можна виділити два шляхи, що ведуть до закінчення  комплексу робіт L2 (7,9,11,12,13,14) і

L1(7,8,12,13,14).

Оскільки Ткр = 39 , Т(L2)с =5+ 5+7+10+ 2=29 більше Т(L1)с = 7 + 5 + 10 + 2 = 24 , то Т по (2 - 7) = Т кр  - Т (2 - 7)с  = 39 - 29 = 10 , Тпн(2 - 7) = Тпо(2 - 7) - Т(2 - 7) =10- 3 = 7.

Для роботи 8–12 Тпо = 27 - 7 = 20;

- резерв години шляху – різниця між тривалістю критичного шляху і даного шляху R(L) = Ткр - Т(L).

 

Для шляху L1 (рис. 2) R(L1 ) = Ткр - Т (L1 ) = 39 - 34 = 5 ;

- повний резерв часу роботи – граничний час, на який можна збільшити тривалість даної роботи, не змінюючи при цьому тривалість критичного шляху, що дорівнює величині резерву часу максимального з шляхів, що проходять через дану роботу. Розраховується як різниця між її пізнім терміном початку (закінчення) і раннім терміном її початку (закінчення) Rni = Тпнi - Трнi або Rni = Тпоi - Троi.

Для роботи 8–12 (рис. 2)

Rn(8 - 12) = Тпн (8 - 12) -  Трн(8 - 12) = 20 - 15 = 5 або Rn(8 - 12) = Тпо (8 - 12) - Тро (8 - 12) = 27 - 22 = 5 .

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

Для роботи 3–9 Tрн (9 - 11) = 15 і, тоді

R c (3 - 9) = Tрн (9 - 11) - Tро (3 - 9) = 15 - 9 = 6 .

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

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

 

 

де T(L)max – відстань максимальногошляху, що проходить через дану роботу; Tк¢р – тривалість ділянки шляху, що проходить через дану роботу і збігається з критичним шляхом.

Для роботи 3–9 T(L)max = 33 , Tк¢р = 24 і тоді