Майже в будь-якій мережі від вихідної події до завершального веде кілька шляхів. Кожному шляху відповідає послідовність якихось робіт. Шлях в мережі від вихідної події до завершального називається повним шляхом. Позначається порожнистий шлях буквою L. Тривалістю шляху в мережевому графіку називається час, необхідний для виконання всіх робіт, що лежать на цьому шляху. Тривалість повного шляху позначимо t (L).
Шлях, що має найбільшу протяжність, називається критичним шляхом. Протяжність критичного шляху позначаємо t () або.
Зауваження. У мережі може бути кілька критичних шляхів.
Роботи, що лежать на критичному шляху, називаються критичними. Від їх тривалості залежить загальний термін завершення всіх робіт. Некритичні роботи допускають деяке запізнювання в їх виконанні, яка не затримає термінів реалізації всього проекту.
Раннім терміном (j) звершення події j називається найраніший момент часу, до якого завершуються всі попередні цій події роботи. Відлік часу ведеться від моменту настання початкового події. Ранній термін початкового події дорівнює 0. (0) = 0. Ранній термін будь-якого іншого j-гo події визначається тривалістю найтривалішого з попередніх шляхів. Визначаємо ранні терміни звершення подій по рекурентному співвідношенню:
Повний термін настання події - час, при якому планований термін закінчення проекту не змінюється. Позначається (i) - для i -гo події.
Зауваження. Для завершального події До пізній термін настання збігається з раннім, т. Е.
При визначенні пізніх термінів настання події розрахунок ведуть від завершального події до вихідного. Кожну вершину орграфа (подія мережевий моделі) розіб'ємо на 3 сектора. в нижньому проставляем номер події; в лівому - ранній термін; в правому - пізній термін.
Резерви часу кожної події знаходяться за формулою:
Зауваження. Для подій i, що лежать на критичному шляху, ранні та пізні терміни настання збігаються, т. Е. (I) = (i).
Поняття ранніх і пізніх термінів настання подій грають важливу роль в процесі виконання проекту. Якщо всі події i наступають не пізніше (i). то це означає, що проект здійсниться не пізніше встановленого терміну.
Якщо якась подія i настає пізніше (i). то вживають заходів для прискорення робіт в цій частині проекту. Якщо прискорити роботу не вдається, то повний термін виконання проекту буде перевищено. Час, на яке затримуються всі роботи, можна теж обчислити по мережевому графіку.
Метод розрахунку мережевих графіків виконується в чотири етапи:
1. Визначення ранніх строків настання подій (i)
2. Знаходження критичного шляху
3. Визначення пізніх термінів настання події (i)
4. Визначення резерву временісобитія.
Зауваження. Використання незалежного резерву часу на i-й роботі, яка його має, не впливає на ранні та пізні терміни здійснення всіх подій і робіт мережі. Його не можна передати ні попереднім, ні подальших робіт.
Оптимізація СМ виражається в перерозподілі ресурсів з ненапружених робіт на критичні для прискорення їх виконання. Для цього необхідно якомога точніше оцінити ступінь труднощів своєчасного виконання всіх робіт, а також всіх «ланцюжків» шляху. Більш точним інструментом вирішення цього завдання, в порівнянні з повним резервом, є коефіцієнт напруженості. Його можна обчислити за такими формулами:
де t () - тривалість максимального шляху, що проходить через роботу (i, j);
- тривалість відрізка розглянутого шляху, що збігається з критичним шляхом.
Коефіцієнт напруженості змінюється від 0 до 1. Чим ближче він до 1. тим складніше виконати дану роботу у встановлений термін.
Найбільш напруженими є роботи критичного шляху, для яких = 1.
На основі цього коефіцієнта всі роботи мережевого графіка поділяються на три групи:
В результаті перерозподілу ресурсів намагаються максимально зменшити загальну тривалість робіт. Для цього необхідно всі роботи перевести в першу групу.
Приклад 1. Ставропольський кондитерський цех вирішив закупити нове обладнання. Вихідні дані по основних операціях проекту представлені в таблиці. Необхідно побудувати мережеву модель проекту, визначити часові параметри моделі, критичний шлях і проаналізувати, як впливає на хід виконання проекту затримка певного типу обладнання на 12 годин.
Рішення. Побудуємо мережеву модель за умовою задачі.
Работиівведени для усунення паралельності робіт Г і Д. Розрахунок критичного шляху включає два етапи. Перший називається прямим проходом. Обчислення починають з вихідного собьпія і продовжують до тих пір, поки не буде досягнута завершальна подія. Для кожної події обчислює одне число, яке представляє ранній термін його настання. На другому етапі, званому зворотним проходом, обчислення починають з завершального події і продовжують, поки не буде досягнуто вихідне подія. Для кожної події обчислюється пізній термін його настання.
Знайдемо ранні терміни настання подій:
При пошуку критичних шляхів на мережевому графіку будемо використовувати такі умови його критичності:
• необхідна умова - нульові резерви подій, що лежать на критичному шляху;
• достатня умова - нульові повні резерви робіт, що лежать на критичному шляху.
Згідно необхідній умові два повних шляху мережевий моделі можуть бути критичними:
L1 = 1, 3, 4, 5, 6 і L2 = 1, 4, 5, 6. Перевіримо достатня умова критичності для робіт (1, 3) і (1, 4)
Шлях L2. що починається з роботи (1, 4) не є критичним, так як мінімум одна (1, 4) з його робіт не є критичною. Робота (1, 4) має не нульовий повний резерв, а значить, може бути затримана з виконанням, що є неприпустимим для критичних робіт.
Таким чином, мережева модель має єдиний критичний шлях, = 1, 3, 4, 5, 6, тривалістю
= 52 години. За виконанням робіт цього шляху необхідний особливий контроль, так як будь-яке збільшення їх тривалості порушить термін виконання проекту в цілому.
Робота А чи (1, 2) не є критичною, її повний резерв дорівнює 1 годині.
Це означає, що при затримці роботи в межах 1 години термін виконання проекту не буде порушений. Тому, якщо відповідно до умови робота А затримається на 12 годин. то весь проект затримається на 11 годин.
Приклад 2. Компанія «АВC» реалізує проекти серійного виробництва різних видів продукції. Кожен проект забезпечує отримання в тиждень 100 тис. У. д. е. доларів додаткового прибутку. Перелік робіт і їх характеристики представлені в таблиці.
