Розрахунок та аналіз мережевих графіків. Ранній термін настання події

Основні параметри мережного графіка

До основних параметрів мережного графіка відносяться:

Критичний шлях

Резерви часу здійснення подій

Резерви часу для виконання робіт

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

Повний шлях - Шлях, початком якого є вихідна подія, а кінцем завершальне.

Тривалість, довжина колії, дорівнює сумі тривалостей робіт. Його складових.

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

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

Повні шляхи можуть проходити поза критичним або частково збігатися з ним. Ці менші за тривалістю шляху називаються ненапруженими.Особливості в тому. Що мають резерви часу. А критичний шлях – ні. Для кожної i-ї події визначається:

t pi– ранній термін наступу– мінімальний із можливих термінів настання цієї події при заданій тривалості робіт.

t п i– пізній термін наступу– максимальний термін настання цієї події, за якого ще можливе виконання всіх наступних робіт, з дотриманням встановленого строку настання події.

R i – резерв часу для події– проміжок часу, який може бути відстрочено наступ цієї події без порушення терміну розробки планованого комплексу загалом. Визначається як різницю між пізнім ( t п i) та раннім ( t р i) термінами здійснення даної події.

Резерви події критичного шляху дорівнюють нулю, тому що на ньому t п i = t р i

Для кожної роботи ( t ij) визначається:

ранній термін початку (t р.н. ij)- Мінімальний з можливих термінів початку даної роботи.

ранній термін закінчення (t р.о. ij)– мінімальний із можливих термінів закінчення даної роботи, при заданій тривалості робіт

пізній термін початку (t п.н. ij)– максимальний із допустимих термінів початку цієї роботи

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

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

t р.н. ij = t р i

t р.о. ij = t р i + t ij

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

t п.о. ij = t п j

t п.н. ij = t п j - t ij

Повний резерв часу для виконання роботи R nij– максимальний період часу, на який можна відкласти початок або збільшити тривалість роботи, не змінюючи встановлений термін настання завершальної події.

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

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

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

3.Розрахунок мережевих моделей

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

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

Верхній сектор – резерв часу настання події R i

лівий сектор – ранній термін настання події t pi

правий сектор – пізній термін настання події t п i

внизу – номер події

Методика розрахунку параметрів

1) Ранні терміни здійснення подій . Ранній термін здійснення вихідної (першої або нульової) події приймається рівним нулю. Ранні терміни здійснення всіх інших подій визначається в суворій послідовності за зростаючими номерами подій. Для визначення раннього терміну звершення будь-якої події j розглядаються всі роботи, що входять до цієї події, по кожній роботі визначається ранній термін звершення кінцевої події як сума раннього терміну звершення початкової події роботи та тривалості цієї роботи t ij ,з отриманих значень вибирається максимальний час раннього терміну здійснення j-ї події

t pj = (t pi +t ij) max та записується на графік (лівий сектор події)

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

3) Тривалість критичного шляху дорівнює ранньому терміну настання завершальної події.

4) Резерви часу подій . При визначенні резервів часу для подій слід відняти від числа, записаного в правому секторі даної події, число, записане в лівому секторі і поставити його у верхній сектор.

5) При визначенні повного резерву часу для роботи слід відняти від числа, записаного в правому секторі кінцевої події, число, записане в лівому секторі початкової події, та тривалість самої роботи.

6) При визначенні вільного резерву для роботи слід відняти від числа, записаного в лівому секторі кінцевої події, число, записане в лівому секторі початкової події, та тривалість самої роботи.

Вихідні дані:

Табличний метод

Коди робіт у таблиці записуються за зростанням індексу i.

Стовпці 2 та 3 заповнюються допоміжними даними: кодами попередніх та наступних робіт. Ці дані будуть потрібні для розрахунків. Якщо роботи початкові, тобто попередніх робіт немає, чи кінцеві, тобто наступних робіт немає, то відповідних графах ставляться прочерки. Попередніх і наступних робіт може бути дещо відповідно до кількості векторів, що закінчуються або починаються в цій події./

У стовпці 4 розмішають значення тривалості робіт.

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

Раннє початок робіт, які мають попередніх (у графі 2 – прочерк), може бути прийнято за 0, а то й задано якесь інше значення. Раннє закінчення роботи визначається згідно з формулою t р.о. ij = t рн ij + t ij та записується до графи 6.

Раннє початок інших можна визначити як, якщо розглядається, наприклад робота 2,5, яка має початкова подія 2, то час її раннього початку дорівнює часу раннього закінчення роботи 12, так як у неї кінцева подія 2. Значення з графи 6 переписується в графу 5 Коди попередніх робіт зазначені у графі 2. Раннє закінчення також визначається за формулою t р.о. ij = t рн ij + t ij

Якщо, у графі 2 зазначено, що певній роботі передує більше, ніж одна робота (роботі 5,6 передують роботи 2,5 і 3,5), необхідно вибрати значення раннього початку з кількох варіантів значення (9 – за часом закінчення роботи 2 ,5 чи 13 – за часом закінчення роботи 3,5). Правило вибору відповідає формулі t p . ij = (t pi + t ij) max , тобто вибирається максимальне значення (у прикладі – 16). Ранні закінчення визначаються як зазначалося вище.

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

Другий прохід уздовж рядків таблиці від роботи, записаної в останньому рядку, до роботи, записаної в першому рядку, дозволяє визначити значення пізніх показників робіт. Для робіт, які не мають наступних робіт (у графі 3 – прочерк, у прикладі роботи 46, 5,6) у графу пізнього закінчення (8) записується значення критичного шляху. Для цих робіт значення пізнього початку обчислюється за формулою t п.н. ij t по ij - t ij

Пізніше закінчення інших можна визначити як, якщо розглядається, наприклад робота 3,5, яка має кінцеву подію 5, то час її пізнього закінчення дорівнює часу пізнього початку роботи 5,6, так як у неї кінцева подія 5. Значення з графи 7 переписується в графу 8. Коди наступних робіт зазначені у графі 3. Пізній початок також визначається за формулою t п.н. ij t по ij - t ij .

Якщо, у графі 3 зазначено, що певній роботі слід більше, ніж одна робота (роботі 0,1 слідують роботи 1,2 і 1,3), необхідно вибрати значення пізнього закінчення з кількох варіантів значення (3 – за часом початку роботи 1 ,3 чи 7 – за часом початку роботи 1,2), вибирається мінімальне значення (у прикладі – 3). Пізніше початок визначаються як зазначалося вище за формулою t п.н. ij t по ij - t ij .

Значення повного резерву часу (стовпець 9) розраховується за формулою

R nij = t по ij - t рн ij - t ij.

Значення вільного резерву часу (стовпець 10) розраховується за формулою

R з ij = t ро ij - t рн ij - t ij

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

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

Шлях від вихідної події до будь-якого взятого передуєцій події. Попередній події шлях, що має найбільшу довжину, називається максимальним попереднім. Він позначається L 1 (i), яке тривалість t.

Шлях, що поєднує будь-яку взяту подію з завершальною, називається наступнимшляхом. Такий шлях із найбільшою довжиною називається максимально наступнимі позначається L 2 (i), яке тривалість t.

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

Роботи критичного шляху виділяються жирними лініями чи подвійними. Тривалість критичного шляху вважається основним параметром графіка.

Розглянемо алгоритм визначення критичного шляху на мережевому графіку, який використовує алгоритм методу динамічного програмування.

Упорядкуємо вершини графіка за рангами і пронумеруємо їх з кінця на початок. Це дозволить поєднати номери рангів з етапами зворотного руху при знайденні умовно-оптимальних управлінь на останньому, двох останніх і т.д. етапах. Знаходження критичного шляху розберемо з прикладу мережного графіка, зображеного на рис. 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) і т.д. На графіку він виділений жирною лінією:

X1-X3-X4-X7-X8-X10-X11-X12-X13-X15-X16.

Ранні та пізні терміни здійснення подій. Резерв часу подій

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

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

або

Щоб знайти ранній термін здійснення події j, потрібно знати критичний шлях орієнтованого підграфа, що складається з безлічі шляхів, що передують даній події j. Ранній термін вихідної події дорівнює нулю: t p (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 дорівнює: . Резерви інших подій дорівнюють нулю, оскільки ці події критичні.

Ранні та пізні терміни початку та закінчення робіт. Визначення резервів часу робіт. Повний резерв часу робіт.

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

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

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

Пізній термін закінчення роботизбігається з пізнім терміном здійснення її кінцевої події: .

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

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

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

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

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

Розрахунок мережного графіка табличним способом проводиться у разі формулам, раніше викладеним у розділі 4 (1-10). Під час визначення параметрів мережевих моделей аналітичним способом розрахунок виконується у формі таблиці. Розглянемо особливості розрахунку мережевих моделей даним способом (приождення 1) на прикладі розрахунку параметрів мережного графіка, зображеного в завданні до цієї курсової роботи (варіант 15).

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

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

Раннє початок робіт 2-6 і 2-7 (відповідно до формули 3) дорівнює ранньому закінченню роботи 1-2.

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

Пізніше початок роботи 20-21 визначається відповідно до формули 5 (= 34)

Пізніше початок роботи 20-21 є пізнім закінченням попередньої роботи 15-20 (=).

Далі розрахунок пізніх параметрів виконується аналогічно, крім випадків, коли в роботи є кілька наступних робіт (наприклад, у роботи 6-9 є дві наступних - 9-10 і 9-14). У цьому випадку, відповідно до формули 4, пізнє закінчення роботи 6-9 дорівнює мінімальному значенню пізніх почав наступних робіт 9-10 і 9-14.

Для знаходження положення критичного шляху необхідно визначити значення загального та приватного резервів часу для кожної роботи та залежності мережного графіка та занести їх значення відповідно до 7 та 8 граф розрахункової таблиці.

Загальний резерв часу робіт, згідно з формулами 8-9, визначається як різниця пізнього та раннього закінчення або як різниця пізнього та раннього почав відповідних робіт. Корисно визначити значення загального резерву часу обома способами збіг отриманих значень може розглядатися як додаткова перевірка. Наприклад, для роботи 6-7:

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

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

Графічний метод розрахунку мережевих графіків

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

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

Для перевірки правильності виконаних розрахунків слід переконатися, що:

• * Виявлено безперервний критичний шлях;
• * Розраховані резерви часу мають невід'ємне значення;
• * значення приватного резерву часу для всіх робіт менше або дорівнює значенню загального резерву часу для даних робіт;
• * хоча б одне значення пізнього початку робіт (роботи), що виходять з першої події, дорівнює нулю.

Відомі два методу розрахунку параметрів мережного графа.обчислення безпосередньо на мережевому графі; аналітичний (табличний).

Розрахунок основних показників мережевої моделіможе зробити так.

• 1. Розрахунок ранніх термінів:
  • ? ранній термін початку робітвизначається тривалістю найдовшого шляху від вихідної події до початку виконання цієї роботи,
  • ? ранні терміни закінчення робіт- це найбільш ранній термін із можливих термінів закінчення роботи. Ранній термін закінчення робіт дорівнює сумі раннього терміну початку роботи і тривалості самої роботи.
• 2.Розрахунок критичного шляху.Його тривалість окреслюється сумарний час робіт, що лежать на критичному шляху, тобто. час завершення всього комплексу робіт при найбільшому запаралелювання всіх робіт. Цей час дорівнює найбільшому з часів ранніх закінчень завершальних робіт мережевого графа. Критичний шлях проходить через події, які мають резервів часу (через критичні роботи).
• 3.Розрахунок пізніх термінів початку та закінчення робітвизначаються з можливостей граничного зсуву вправо числової осі строків виконання робіт так, щоб не було змінено час критичного шляху. Тому логічно розрахунки вести від останньої події до першої та визначати спочатку час пізнього закінчення робіт, а потім розраховувати час пізнього початку робіт:
  • ?пізній термін початку робіт (ij) визначається як різниця між пізнім терміном закінчення робіт та тривалістю самої роботи,
  • ? пізній термін закінчення робітвизначається величиною шляху мінімальної тривалості, що веде до нього від завершальної події, і розраховується як різницю критичного шляху та максимальної тривалості роботи від завершальної події мережного графіка до кінцевої події даної роботи.
• 4. Розрахунок резервів часу.

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

• ? приватні (вільні) резерви часу.
• 1)приватний резерв часу першого видувизначається можливістю змінити пізній початок роботи ( ij)більш ранні терміни без зміни пізніх термінів закінчення безпосередньо попередніх робіт,
• 2) приватний резерв часу другого видувизначається можливістю змінити раннє закінчення роботи (ij)більш пізні терміни без зміни ранніх термінів початку безпосередньо наступних робіт; визначається різницею між раннім початком подальшої роботи та раннім закінченням даної роботи.

Розглянемо порядок розрахунку параметрів з прикладу. Мережевий графік представлений на рис. 7.5.

Мал. 7.5.

Для розрахунку параметрів скористаємося табличним методом і з метою спрощення сприйняття зведемо все в одну табл. 7.1.

Правила застосування резервів часу у мережевому плануванні.

• 1. Для того щоб повний і приватні резерви роботи (у) були рівні, необхідно й достатньо, щоб кінцева подія розглядуваної роботи була подією критичного шляху.
• 2. Якщо повний резерв (Я і]1)деякої роботи дорівнює нулю, то приватний резерв другого виду (г"ф)також дорівнює нулю. Між цими резервами завжди має місце співвідношення R(IJ) > r" ijyПовний та приватні резерви часу завжди більші або рівні нулю.
• 3. Для того щоб приватний резерв часу роботи (у) дорівнював нулю, необхідно і достатньо, щоб ця робота лежала на шляху максимальної довжини від першої події до події у.
• 4. Якщо тривалість роботи (у) збільшити величину р, тобто. р то ранній термін початку наступної роботи збільшиться на величину р - г" ("уу
• 5. Якщо тривалість роботи збільшити на величину повного резерву часу цієї роботи, то утворюється новий критичний шлях, тривалість якого дорівнює тривалості старого.
• 6. Повний резерв часу роботи (у) дорівнює сумі приватного резерву часу другого виду цієї роботи та мінімального із сукупності повних резервів усіх безпосередньо наступних робіт.

Результати розрахунку параметрів мережного графіка

Таблиця 7.1

	Тривалість	Ранні	терміни, год	Пізні терміни, год		Резерви часу, год
	робіт, год	Початок	Закінчення	Початок	Закінчення	Повні	Вільні
	Критичний шлях, ч		(роботи 1-3

7. Якщо тривалість роботи (г/) збільшити на величину р, то з'явиться новий критичний шлях, тривалість якого перевищить тривалість старого критичного шляху на величину р -

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

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

Рішення

Для вирішення задачі застосуємо такі позначення.

Елемент мережі	Найменування параметру	Умовне позначення параметра
Подія i	Ранній термін здійснення події
Пізній термін події
Резерв часу події
Робота (i, j)	Тривалість роботи
Ранній термін початку роботи
Ранній термін закінчення роботи
Пізній термін початку роботи
Пізній термін закінчення роботи
Повний резерв часу роботи
	Тривалість шляху
Тривалість критичного шляху
Резерв часу шляху

Для визначення резервів часу за подіями мережі розраховують найбільш ранні t p і пізніші t п терміни здійснення подій. Будь-яка подія не може наступити перш, ніж відбуватиметься всі попередні події і не будуть виконані всі попередні роботи. Тому ранній (або очікуваний) термін tp(i) здійснення i-ої події визначається тривалістю максимального шляху, що передує цій події:

t p (i) = max(t(L ni)) (1)

де L ni - будь-який шлях, що передує i-й події, тобто шлях від вихідної до i-ої події мережі.

Якщо подія j має кілька попередніх шляхів, а отже, кілька попередніх подій i, то ранній термін здійснення події j зручно знаходити за формулою:

t p (j) = max (2)

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

t п (i) = t kp - max(t(L ci)) (3)

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

Якщо подія i має декілька наступних шляхів, а отже, кілька наступних подій j, то пізній термін здійснення події i зручно знаходити за формулою:

t п(i) = min

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

R(i) = tп(i) - tp(i)

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

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

При визначенні ранніх термінів здійснення подій tp(i) рухаємося за мережевим графіком зліва направо і використовуємо формули (1), (2).

Розрахунок термінів здійснення подій.

Для i=0 (початкової події) очевидно tp(0)=0.

i = 1: t p (1) = t p (0) + t (0,1) = 0 + 0 = 0.

i = 2: t p (2) = t p (1) + t (1,2) = 0 + 8 = 8.

i = 3: t p (3) = t p (1) + t (1,3) = 0 + 3 = 3.

i=4: max(t p(2) + t(2,4);t p(3) + t(3,4)) = max(8 + 6;3 + 3) = 14.

i=5: tp(5) = tp(4) + t(4,5) = 14 + 0 = 14.

i = 6: max (t p (4) + t (4,6); t p (5) + t (5,6)) = max (14 + 5; 14 + 3) = 19.

i = 7: t p (7) = t p (6) + t (6,7) = 19 + 9 = 28.

i=8: max(t p (2) + t(2,8);t p (6) + t(6,8);t p (7) + t(7,8)) = max(8 + 18;19 + 5; 28 + 4) = 32.

i = 9: max (t p (5) + t (5,9); t p (7) + t (7,9)) = max (14 + 2; 28 + 4) = 32.

i=10: max(t p (4) + t(4,10);t p (7) + t(7,10);t p (9) + t(9,10)) = max(14 + 4;28 + 2; 32 + 0) = 32.

i = 11: max (t p (8) + t (8,11); t p (10) + t (10,11)) = max (32 + 12; 32 + 4) = 44.

Довжина критичного шляху дорівнює ранньому терміну звершення завершальної події 11: kp =tp(11)=44

При визначенні пізніх термінів здійснення подій t п (i) рухаємося по мережі у зворотному напрямку, тобто праворуч наліво і використовуємо формули (3), (4).

Для i=11 (завершальної події) пізній термін здійснення події повинен дорівнювати його ранньому терміну (інакше зміниться довжина критичного шляху): t п (11) = t р (11) = 44

i = 10: t п (10) = t п (11) - t (10,11) = 44 - 4 = 40.

i = 9: t п (9) = t п (10) - t (9,10) = 40 - 0 = 40.

Проглядаються усі рядки, що починаються з номера 8.

i = 8: t п (8) = t п (11) - t (8,11) = 44 - 12 = 32.

Проглядаються усі рядки, що починаються з номера 7.

i=7: min(t п (8) - t(7,8);t п (9) - t(7,9);t п (10) - t(7,10)) = min(32 - 4; 40 - 4; 40 - 2) = 28.

i = 6: min (t п (7) - t (6,7); t п (8) - t (6,8)) = min (28 - 9; 32 - 5) = 19.

Проглядаються усі рядки, що починаються з номера 5.

i = 5: min (t п (6) - t (5,6); t п (9) - t (5,9)) = min (19 - 3; 40 - 2) = 16.

i=4: min(t п (5) - t(4,5);t п (6) - t(4,6);t п (10) - t(4,10)) = min(16 - 0; 19 - 5; 40 - 4) = 14.

Проглядаються усі рядки, що починаються з номера 3.

i = 3: t п (3) = t п (4) - t (3,4) = 14 - 3 = 11.

i = 2: min (t п (4) - t (2,4); t п (8) - t (2,8)) = min (14 - 6; 32 - 18) = 8.

i = 1: min (t п (2) - t (1,2); t п (3) - t (1,3)) = min (8 - 8; 11 - 3) = 0.

(0,1): 0 - 0 = 0;

Таблиця 1 - Розрахунок резерву подій

Номер події	Терміни здійснення події: ранній tp(i)	Терміни здійснення події: пізній tп(i)	Резерв часу, R(i)

Наповнення таблиці 2.

Перелік робіт та їх тривалість перенесемо у другу та третю графи. При цьому роботи слід записувати до графи 2 послідовно: спочатку починаючи з номера 0, потім з номера 1 і т.д.

У другій графі поставимо число, що характеризує кількість безпосередньо попередніх робіт (КПР) тієї події, з якої починається робота, що розглядається.

Так, до роботи (1,2) до графи 1 поставимо число 1, т.к. на номер 1 закінчуються 1 роботи: (0,1).

Графу 4 отримуємо з таблиці 1 (t p (i)). Графу 7 одержуємо з таблиці 1 (t п (i)).

Значення у графі 5 виходять у результаті підсумовування граф 3 та 4.

У графі 6 пізній початок роботи визначається як різниця пізнього закінчення цих робіт та їх тривалості (із значень графи 7 віднімаються дані графи 3);

Вміст графи 8 (повний резерв часу R(ij)) дорівнює різниці граф 6 і 4 або граф 7 і 5. Якщо R(ij) дорівнює нулю, то робота є критичною

Таблиця 2 - Аналіз мережевої моделі за часом

Робота (i,j)	Кількість попередніх робіт	Тривалість tij	Ранні терміни: початок tijР.М.	Ранні терміни: закінчення tijР.О.	Пізні терміни: початок tijП.Н.	Пізні терміни: закінчення tijп.о.	Резерви часу: повний RijП	Незалежний резерв часу RijН	Приватний резерв I роду, Rij1	Приватний резерв ІІ роду, RijC

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

R (i, j) = R п (i, j) - R (i)

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

R (i, j) = R п (i, j) - R (j)

Значення вільного резерву часу роботи свідчить про розташування резервів, необхідні оптимізації.

Незалежний резерв часу Rн роботи (i,j) - частина повного резерву, одержувана для випадку, коли попередні роботи закінчуються в пізні терміни, проте наступні починаються ранні терміни. Rн знаходиться за формулою:

R(i,j) = Rп(i,j) - R(i) - R(j)

Критичний шлях: (0,1)(1,2)(2,4)(4,6)(6,7)(7,8)(8,11)

Тривалість критичного шляху: 44

Знайдемо коефіцієнт напруженості передостанньої роботи. Оскільки довжина критичного шляху 44, максимальний шлях, що проходить через роботу (1,10) дорівнює 32, тоді

К(1,10)=(32-28)/(44-28)=0,296.

4. Інтернет-провайдер у невеликому місті має 5 виділених каналів обслуговування. В середньому на обслуговування одного клієнта потрібно 25 хвилин. У систему в середньому надходить 6 акзаів на годину. Якщо вільних каналів немає, слід відмова. Визначити характеристики обслуговування: ймовірність відмови, середня кількість зайнятих обслуговуванням ліній зв'язку, абсолютну та відносну пропускну здатність, ймовірність обслуговування. Знайти число виділених каналів, у якому відносна пропускна спроможність системи буде щонайменше 0,95. Вважати, що потоки заявок та обслуговувань найпростіші

Інтенсивність потоку обслуговування:

Інтенсивність навантаження:

с = л * t обс = 6 * 25/60 = 2.5

Інтенсивність навантаження с=2.5 показує ступінь узгодженості вхідного та вихідного потоків заявок каналу обслуговування та визначає стійкість системи масового обслуговування.

Імовірність того, що обслуговуванням:

зайнятий 1 канал:

p 1 = з 1/1! p 0 = 2.5 1/1! * 0.0857 = 0.214

зайняті 2 канали:

p 2 = з 2/2! p 0 = 2.5 2/2! * 0.0857 = 0.268

зайняті 3 канали:

p 3 = з 3/3! p 0 = 2.53/3! * 0.0857 = 0.223

зайняті 4 канали:

p 4 = з 4/4! p 0 = 2.54/4! * 0.0857 = 0.139

зайняті 5 канали:

p 5 = з 5/5! p 0 = 2.5 5/5! * 0.0857 = 0.0697

Імовірність відмови - це частказаявок, які отримали відмову:

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

Імовірність обслуговування заявок, що надходять-ймовірність того, що клієнт буде обслужений:

У системах з відмовами події відмови та обслуговування становлять повну групу подій, тому:

p отк + p обс = 1

Відносна пропускна здатність Q = p обс .

p обс = 1 - p отк = 1 - 0.0697 = 0.93

Отже, 93% з числа заявок, що надійшли, будуть обслужені. Середня кількість каналів, зайнятих обслуговуванням

n з = с * p обс = 2.5 * 0.93 = 2.326 каналу.

Середня кількість каналів, що простоюють..

n пр = n – n з = 5 – 2.326 = 2.7 каналу.

Коефіцієнт зайнятості каналів обслуговуванням.

Отже система на 50% зайнята обслуговуванням.

Абсолютна пропускна спроможність

A = pобс * л = 0.93 * 6 = 5.581 заявок/год.

Середній час простою СМО.

t пр = p отк * t обс = 0.0697 * 0.417 = 0.029 год.

Середня кількість заявок, що обслуговуються..

L обс = с * Q = 2.5 * 0.93 = 2.326 од.

Середній час перебування заявки до СМО(Формула Літтла).

Число заявок, які отримали відмову протягом години: л * p 1 = 0.418 заявок на годину.

Номінальна продуктивність СМО: 5/0.417 = 12.002 заявок на годину.

Фактична продуктивність СМО: 5.581/12.002 = 47% від номінальної продуктивності.

Визначимо кількість каналів, необхідні забезпечення працездатності системи з ймовірністю P ? 0.95

Для цього знаходимо n із умови:

Знайдемо ймовірність того, що якщо в системі буде 6 каналів і всі вони будуть зайняті: