10.4.1. Види шляхів мережного графіка. Критичний шлях і алгоритм його знаходження. Будь-яка послідовність робіт мережного графіка, в якій кінцева подія кожної роботи співпадає з початковою подією наступної за нею роботи, називається шляхом .
Шлях мережного графіка, в якому початкова точка співпадає з початковою подією, а кінцева – з завершальним подією, називається повним.
Шлях від вихідної події до будь-якого взятого передує даній події. Передує події шлях, що має найбільшу довжину, називається максимальним попереднім. Він позначається L1 (i), а його тривалість t[L1 (i)].
Шлях, що з'єднує будь-яке взяте подія з завершальним, називається подальшим шляхом. Такий шлях з найбільшою довжиною називається максимально подальшим і позначається L2 (i), а його тривалість t[L2 (i)].
Повний шлях, що має найбільшу довжину, називається критичним. Шляхи, відмінні від критичного, називаються ненапряженними. Вони мають резерви часу.
Роботи критичного шляху виділяються жирними лініями або подвійними. Тривалість критичного шляху вважається головним параметром графіка.
Розглянемо алгоритм визначення критичного шляху на мережевому графіку, що використовує алгоритм методу динамічного програмування.
Впорядкуємо вершини графіка по рангах і пронумеруємо їх з кінця до початку. Це дозволить поєднати номери рангів з етапами назаднього руху при відшуканні умовно-оптимальних управлінь на останньому, двох останніх і т. д. етапах. Знаходження критичного шляху розберемо на прикладі мережевого графіка, зображеного на рис. 10.7.
Відповідно до принципу оптимальності Беллмана, оптимальне управління на кожному етапі визначається метою управління і станом на початок етапу. Стан системи – це події, що лежать на ранги. Для здійснення кінцевого події Х16 необхідно вчинення попередніх подій. Можливі стани системи на початок останнього етапу робіт – вчинення подій Х14 і Х15. В гуртках біля точок Х14 і Х15 поставимо максимальну тривалість робіт на останньому етапі: Х14 5. Х15 7. Знайдемо максимальну тривалість робіт на двох останніх етапах. Стан системи на початок передостаннього етапу обумовлено подією Х13. Максимальна тривалість шляху, що веде з Х13 до Х
16 дорівнює . Отже, в гуртку у події Х13 потрібно поставити число 14 і т. д. Проводячи етапи від кінця до початку, дізнаємося довжину критичного шляху tкр =96. Щоб знайти критичний шлях, процес обчислень пройдемо від початкового події Х1 до кінцевого Х16. Число 96 на першому етапі (від початку) ми отримали, додавши 16 до 80. Отже, критичний шлях на цьому етапі буде дорівнює (Х1. Х3 ). Число 80=16+64. Отже, критичний шлях на другому етапі проходить через роботу (Х3. Х4 ) і т. д. На графіку він виділений жирною лінією:
10.4.2. Ранні та пізні строки звершення подій. Резерв часу подій. Всі шляхи, відмінні за тривалістю від критичного, мають резерви часу. Різниця між довжиною критичного шляху і будь-якого некритичного називається повним резервом часу даного некритичного шляху і позначається : .
Раннім терміном звершення події називається найбільш ранній момент часу, до якого завершуються всі попередні цій події роботи, тобто визначається тривалістю максимального шляху, що передує події , тобто:
Щоб знайти ранній термін настання події j. потрібно знати критичний шлях орієнтованого подграфа, що складається з безлічі шляхів, що передують даній події j. Ранній термін вихідної події дорівнює нулю: tp (1)=0.
Пізнім терміномздійснення події називається самий пізній момент часу, після якого залишається рівно стільки часу, скільки необхідно для завершення всіх робіт, наступних за цією подією. Найбільш пізній з допустимих строків звершення події в сумі з тривалістю виконання всіх наступних робіт не повинен перевищувати довжини критичного шляху. Пізній термін звершення події обчислюється як різниця між тривалістю критичного шляху і тривалістю максимального наступних за подією шляхів :
Для подій, що лежать на критичному шляху, ранній і пізній терміни звершення цих подій збігаються .
Різниця між пізнім і раннім терміном звершення події становить резерв часу події : . Інтервал називається інтервалом свободи події . Резерв часу події показує максимально допустимий час, на яке можна відсунути момент його звершення, не збільшуючи критичний шлях. Так як сума визначає тривалість шляху максимальної довжини, що проходить через цю подію, то , тобто резерв часу будь-якої події дорівнює повного резерву часу максимального шляху, що проходить через цю подію .При розрахунку часових параметрів вручну зручно користуватися четирехсекторним способом. При цьому способі гурток мережевого графіка, що позначає подію, ділиться на чотири сектора. У верхньому секторі ставиться номер події, у лівому – найбільш ранній з можливих час звершення події ( ), у верхньому – найбільш пізній з допустимих час звершення події , у нижньому секторі - резерв часу події : .
Для обчислення раннього терміну звершення подій: , застосовуємо формулу , розглядаючи події в порядку зростання номерів, від початкового до завершального, що входять у цю подію робіт. Пізній термін звершення подій обчислюємо за формулою , починаючи з кінцевого події, для якого ( - номер кінцевого події), що виходять з нього робіт.
Критичні події мають резерв часу дорівнює нулю. Вони і визначають критичні роботи та критичний шлях.
Приклад 10.2. Нехай задано мережевий графік, зображений на рис. 10.8.
Рішення. Обчислимо ранні строки звершення подій :
Отже, завершальна подія може відбутися лише на 14-ий день від початку виконання проекту. Це максимальний час, за який можуть бути виконані всі роботи проекту. Воно визначається найдовшим шляхом. Ранній термін звершення роботи 6 =14 збігається з критичним часом кр - сумарною тривалістю робіт, що лежать на критичному шляху. Тепер можна виділити роботи, що належать критичного шляху, повертаючись від завершального події до вихідного. З двох робіт, що входять в подію 6. , довжина критичного шляху визначила роботи (5, 6), так як 5 + 56 )=14. Тому робота (5, 6) – критична і т. д. Роботи (1, 3), (3, 4), (4, 5), (5, 6) визначили критичний шлях: кр = (1-3-4-5-6).
Обчислимо тепер пізні строки звершення подій . Покладемо . Скористаємося методом динамічного програмування. Всі розрахунки будемо вести від завершального події до початкового події. Пізні строки звершення подій дорівнюють:
, так як після події 5 для завершення проекту потрібно виконати роботу (5, 6) тривалістю 3 дні. Події 4 виходять дві роботи, тому:
Резерв часу події 2 дорівнює: . Резерви інших подій дорівнюють нулю, так як ці події критичні.
10.4.3. Ранні і пізні терміни початку і закінчення робіт. Визначення резервів часу робіт. Повний резерв часу робіт. Подія, що безпосередньо передує даній роботі, будемо називати початковим і позначати , а подія, безпосередньо наступне за нею, – кінцевим і позначати . Тоді будь-яку роботу будемо позначати . Знаючи терміни звершення подій, можна визначити тимчасові параметри робіт.
Ранній термін початку роботи дорівнює раннього терміну звершення події : .
Ранній термін закінчення роботи дорівнює сумі раннього терміну звершення початкового події та тривалості цієї роботи: або .
Пізній термін закінчення роботи збігається з пізнім терміном звершення її кінцевого події : .
Пізній термін початку роботи дорівнює різниці між пізнім терміном звершення її кінцевого події і величиною цієї роботи:
Оскільки терміни виконання робіт знаходяться в межах, визначених і , то вони можуть мати різного виду резерви часу.
Повний резерв часу роботи - це максимальний час, необхідний для виконання будь-якої роботи без перевищення критичного шляху. Він обчислюється як різниця між пізнім терміном звершення кінцевого події і раннім терміном часу для виконання самої роботи: . Так як , то .
Таким чином, повний резерв часу роботи – це максимальний час, на яке можна збільшити її тривалість, не змінюючи тривалості критичного шляху. Всі некритичні роботи мають повний резерв часу відмінний від нуля.
Вільний резерв часу роботи – це запас часу, яким можна розташовувати при виконанні даної роботи за умови, що початкове і кінцеве її події настануть у свої ранні терміни: .
Вільний резерв притаманний тільки даній роботі, та його використання ніяк не вплине на виконання наступних робіт. Лише окремі роботи проекту володіють вільним резервом часу.
Незалежний резерв часу - це запас часу, яким можна розташовувати при виконанні даної роботи за умови, що її початкове подія настане у свій пізній термін, а кінцеве – в ранній термін:
. Використання незалежного резерву часу на роботі, яка його має, не впливає на ранні та пізні строки звершення всіх подій та робіт мережі. Якщо , то це показує недолік часу для виконання даної роботи до самого раннього терміну звершення її кінцевого події, якщо початкова сталося в пізній термін.
Незалежний резерв часу роботи (якщо він є) являє собою залишок від її повного резерву, якщо за рахунок останнього повністю збережені резерви часу початкового події даної роботи і кінцевого : . Величина незалежного резерву часу роботи показує тривалість вимушеного очікування настання кінцевого події даної роботи. Це дозволяє зняти з роботи частина ресурсів з тим, щоб перекинути їх на інші більш напружені роботи.
Для невеликих проектів зручним доповненням до мережного графіка є лінійний графік (графік Ганта). На лінійному графіку кожна робота зображується в прив'язці до осі часу горизонтальним відрізком, довжина якого у відповідному масштабі дорівнює тривалості роботи . Початок кожної роботи збігається з раннім терміном звершення її початкового події. Роботи зображуються в тій же послідовності, що і на мережевому графіку.
Приклад 10.3. Розглянемо мережевий графік, заданий на рис. 10.8. Обчислимо тимчасові параметри робіт.
Ранні терміни початку робіт:
Ранні строки закінчення робіт:
Пізні терміни закінчення робіт:
Пізні строки початку робіт:
Повні резерви часу робіт:
Вільні резерви часу робіт:
Незалежні резерви часу робіт:
, так як ці роботи належать критичного шляху.
Складемо лінійний графік Ганта. Початок кожної роботи збігається з очікуваним терміном звершення її початкового події.
Роботи зображені в тій же послідовності, що і на мережі.