Часові характеристики подій, тривалість виконання комплексу робіт

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

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

(10.1)

де n – загальна кількість вершин сітьового графіка;

U - множина його дуг;

(i, j) U – позначення такої дуги, яка виходить з вершин і та входить у j-ту вершину графа;

t(i, j) – тривалість виконання роботи i →j:

Е(і) – ранній термін настання і-ої події, відповідно;

Е(j) – ранній термін настання j-ої події (i, j= 1,2,…,n).

Тривалість виконання комплексу робіт Т^* дорівнює ранньому терміну настання його кінцевої події. Таким чином,

Т^* = Е(n) (10.2)

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

(10.3)

(10.4)

Події, які не допускають аніякої затримки з їх настанням, називаються ктиричними. Для кожної критичної точки її резерв часу дорівнює нулю:

R(j^*)= 0, якщо j^* - критична подія. (10.5)

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

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

Е(1) = 0.

Е(2) = Е(1) +t(1, 2) = 0+12,

E(3) = max { E(1) + t (1,3);E(2) + t(2,3)}= max {0+20;12+0} = 20,

E(4) = max { E(1) + t (1,4);E(2) + t(2,4)}= max {0+27;12+0} = 27,

E(5) = E(3) + t (3,5) = 20+7 = 27,

E(6) = E(4) + t (4,6) = 27+14 = 41,

E(7) = max { E(5) + t (5,7);E(6) + t(6,7)}= max {27+13; 41+0} = 41,

E(8) = max { E(6) + t (6,8);E(7) + t(7,8)}= max {41 + 11; 41 + 15} = 56.

Тривалість виконання комплексу робіт співпадає з раннім терміном настання останньої – восьмої – події. Отже,

Т^* = 56

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

L(8) = Т^* = 56,

L(7) = L(8)- t (7,8) = 56 – 15 = 41,

L(6) = min {L(8) + t (6,8); L(7) - t(6,7)}= min {56-11; 41-0} = 41,

L(5) = L(7) – t(5,7) = 41 – 13 = 28,

L(4) = L(6) – t(4,6) = 41 – 14 = 27,

L(3) = L(5) – t(3,5) = 28 – 7 = 21,

L(2) = min {L(4) + t (2,4); L(3) - t(2,3)}= min {27-0; 21-0} = 21,

L(1) = min {L(4) + t (1,4); L(3) - t(1,3); L(2) - t(1,2)}= min {27-0; 21—20; 21-12} = 0.

Покажемо терміни настання подій на сітьовому графіку (рис. 10.12). На цьому рисунку також виділено вершини, які від­повідають критичним подіям (для таких подій ранній термін на­стання Е співпадає з їх пізнім терміном настання L).

Рис. 10.12

На рис. 10.12. для кожного комплексу робіт надано ранній (Е) та пізні (L)терміни настання подій (критичні події 1, 4, 6, 7 та 8 виділено).

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

Табл. 10.3

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

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

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

M(I,j)=L(j)-E(i)-t(i,j) (10.6)

де: L(j) – пізній термін настання j-ої події, яка є кінцевою для роботи (i, j);

Е (і) – ранній термін настання і-ої події, яка є вихідною для цієї роботи;

t (i, j)- нормативна тривалість виконання відповідної роботи.

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

для всіх (10.7)

де U * — множина усіх критичних робіт проекту.

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

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

Вільний резерв часу N(i, j) роботи (і, j) — це така максималь­но можлива затримка із виконанням цієї роботи, яка не впливає на терміни виконання усіх наступних робіт:

N(i,j) = E(J)-E(i)-t(iJ). (10.8)

Незалежний резерв часу Р{і, j) роботи (і, j) характеризує таку максимально можливу затримку із виконанням цієї роботи, яка не впливає на терміни виконання усіх інших робіт проекту:

Р(і, j) = max {0; E(j) – L(i) - t(i, j)}. (10.9)

Для кожної з робіт усі три види резервів часу задовольняють нерівність:

М{і, j) N(i, j) Р(і, j) 0. (10.10)

Приклад 10.3.Зведемо разом усі часові характеристики робіт (дуг) сітьового графіка, наведеного на рис. 10.13. Такими характе­ристиками роботи (/, j) є:

• тривалість — t(i, j);

• ранній термін початку — раніше якого розпочати роботу

неможливо — Е(ї);

• пізній термін закінчення — перевищення якого призведе до
затримки із завершенням проекту в цілому — L(j);

• усі резерви часу — М(і, j), N(i, j) та Р(і, j), які розраховують­ся за формулами (10.6), (10.8), (10.9).

для роботи (3, 5) маємо:

t<(3,5) = 7;E(3) = 20;L(5) = 28;

М(3, 5) = 28 - 20 - 7 = 1; N (3, 5) = 27 - 20 - 7 = 0;

Р(3, 5) = max {0; 27-21-7} = 0.

Резерви часу усіх дуг сітьового графіка та критичний шлях показано на рис. 10.13. Часові характеристики усіх робіт проекту, що розглядається, наведено у табл. 10.4.

На сітьовому графіку комплексу робіт застосовано позначен­ня: ранній та пізній терміни настання подій ;

резерви часу робіт: V, N, P, де М - повний резерв; N - вільний; Р - незалежний; роботи критичного шляху (1—4; 4—6; 6—7; 7—8) виділено.

.

Рис. 10.13

Табл. 10.4

Завершений сітьовий графік (рис. 10.13) і таблиці про часові характеристики подій та робіт (табл. 10.2 і 10.3) є зручними інстру­ментами при обговоренні та затвердженні календарного плану і подальшому контролі за виконанням проекту.

10.3 Сітьове планування з урахуванням вартості виконання робіт

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

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

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

Рис. 10.14

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

Нехай {1, 2,..., п) — множина вершин сітьового графіка, U — множина його дуг. Припустимо, що тривалість t_lt роботи (i,j є и) може змінюватись у певних межах часу, де Djj — тривалість виконання цієї роботи, скажімо, у від d_tj до D_tj одиниць нормативно­му режимі, a dy — тривалість її виконання у максимально при­скореному режимі.

Нехай c_tj — вартість виконання роботи (i,j) у нормальному режимі, а С_ij + ΔC_ij — витрати на її виконання у максимально прискореному режимі. Припустимо, що залежність вартості z_ij від тривалості виконання t_ij є лінійною:

(10.11)

Що ілюструє рисунок 10.15

Рис. 10.15

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

Знайти t_ij,z_ij, T_i, T_j, i,j = , що належать області G , ви­значеної умовами:

(10.12)

(10.13)

(10.14)

і мінімізірують функцію цілі:

Задача (10.12)—(10.15) є задачею лінійного програмування з двосторонніми обмеженнями на t_tj. Якщо її розв'язок існує, тоб­то коли є можливість виконати проект за директивний термін T_d, результатом розв'язування задачі будуть такі тривалості вико­нання кожної з робіт t_ij*, (і,j) є U, за яких вартість виконання z* всього проекту буде найменшою.

У загальному випадку задачу оптимізації сітьового графіка з урахуванням часу та вартості можна розглядати як двоцільову

, (10.16)

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

Таким чином, задачу (10.12)—(10.15) слід розглядати лише як спрощений підхід до розв'язання цільової проблеми оптимізації сітьового графіка. Наступним кроком здійснення цільової опти­мізації буде дослідження задачі (10.12)—(10.15) як параметричної відносно директивного терміну виконання проекту T_d . Це дозво­лить визначити залежність оптимальної вартості z* від T_d (рис. 10.16), що є корисним для узгодження термінів виконання проекту та необхідних для цього витрат.

Рис. 10.16

Приклад 10.4 Розглянемо проект, сітьова модель якого наведена на рис.10.17, а показники тривалості та вартості кожного із робіт надані у табл. 10.5.

Табл. 10.5

Необхідно визначити тривалість та вартість виконання проек­ту за умов:

—тривалість кожної із робіт буде максимальною;

—тривалість кожної роботи буде мінімальною.

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

Розв'язування. 1. Побудуємо сітьовий графік проекту, обра­вши за тривалості робіт максимально можливі терміни їх вико­нання. Обчислимо також часові характеристики L, Е усіх подій та повні резерви часу М усіх робіт подій проекту (рис. 10.18).

Рис. 10.18

Таким чином, максимальна тривалість виконання проекту Т^max = 9 (місяців). Оскільки кожна з робіт виконуватиметься з мінімальною вартістю, робимо висновок, що оптимальна вартість проекту при T_d > 9 дорівнюватиме 6 + 12 + 5 = 23 (тис. грн).

2. Проаналізуємо тепер проект за умов, коли тривалість вико­нання кожної з робіт буде мінімальною (рис. 10.19).

Рис.10.19

Мінімальна тривалість виконання проекту = 6 місців. Проте оптимальна вартість виконання проекту за 6 місяців не дорівнюва­тиме сумі максимальних вартостей виконання кожної із робіт 10 + + 15 + 8 = 33 (тис. грн). Це пояснюється тим, що робота (1, 3) не є критичною та має резерв часу М{1, 3) = 1 міс. Отже, якщо цю ро­боту виконати не за 5, а за 6 міс, тривалість виконання проекту не збільшиться. Але зменшиться вартість виконання роботи (1, 3) оскільки z₁₃ (5 міс.) = 15 тис. грн (табл. 10,5), a z₁₃ (6 міс.) = = 12 + (15-12) = 14 (тис. грн) (формула (10.11) та вихідні дані з табл. 10.11, тобто оптимальна вартість виконання проекту за 6 міс. дорівнюватиме 10 + 14 + + 8 = 32 (тис. грн).

3. Щоб побудувати графік залежності оптимальної вартості виконання проекту z^*від директивної тривалості його виконання T_d(6<T_d <9), складемо задачу параметричного лінійного програ­мування, обравши за параметр T_d:

Знайти t₁₂, t₁₃,t₂₃,T₁ Т₂,Т₃, що належать області G , визначеної умовами:

3 ≤ t₁₂ ≤ 5, 5≤ t₁₃ ≤ 8, 3 ≤ t₂₃ ≤ 4

T₁ + t₁₂ ≤ T₂, T₁ + t₁₃ ≤ T₃, T₂ + t₂₃ ≤ T₃ ; T₁ ≥ 0, T₃ ≤ T_d

і мінімізують функцію цілі:

z = z₁₂ + z₁₃ + z₂₃,

Розв'язок задачі параметричного програмування наведено на рис. 10.20. Бачимо, зокрема, що коли директивну тривалість прое­кту обрати такою, що дорівнює 8 міс. (T_d = 8), оптимальна вар­тість виконання проекту дорівнюватиме 25 тис. грн (z* = 25).

Рис. 10.20

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

Отже, нехай T_d — нормативний термін завершення проекту, s — втрати, що пов'язані із затримкою закінчення проекту на одиницю часу понад нормативний термін його виконання.

Час затримки із виконанням проекту t обчислюється за фор­мулою:

t = ,

де Т_n - термін настання кінцевої n-ої події сітьового графіка.

Тому додаткові витрати через затримку завершення проекту складуть величину st грошових одиниць. Щоб врахувати ці ви­трати при оптимізації сітьового графіка за показником мінімізації загальної вартості, до економіко-математичної моделі (10.12)— (10.16) слід ввести такі корективи:

1)замінити цільову функцію (10.16) на функцію:

яка враховує як витрати, що пов'язані із виконанням проекту (пе­рший доданок), так і втрати внаслідок закінчення проекту із запі­зненням понад нормативний термін T_d (другий доданок);

2) обмеження (10.14) (Т_n Т_d) замінити умовами, які відбива­ють можливість запізнення із закінченням проекту на термін t.

T_n T_d + t, t 0.

В оптимальному плані скоригованої задачі значення t змінної t задовольнятиме умову:

=max {0; }

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

10.4 Сітьове планування за умов ризику щодо тривалостей операцій

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

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

f(t) = B (t – a_ij)^a(b_ij – t)^y, a_ij ≤ t ≤ b_ij,

де В, α, γ > 0; В визначається через параметри розподілу α та γ за формулою:

Графік цієї функції наведено на рис. 10.21

Рис. 10.21

Статистичні характеристики β - розподіленої випадкової ве­личини обчислюються за формулами:

- очікуване значення:

- стандартне відхилення:

де m_ij – модальне (найімовірніше) значення цієї випадкової величини.

У методі PERT параметри α і γ приймають значення:

α = 2 ± , γ = 2 .

Таким чином, для знаходження статистичних характеристик випадкової величини t_ij тривалості роботи і j потрібно визна­чити (як правило, експертним методом) лише три її оцінки:

—оптимістичну (найменше значення) — а_ij,

—песимістичну (найбільше значення) — b_ij,

—модальну (найімовірніше значення) — m_ij

На основі наведених оцінок статистичні характеристики випа­дкової тривалості t_ij роботи і j обчислюються за формулами:

- очікуване значення:

- стандартне відхилення:

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

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

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

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

—правило однієї сигми:

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

Потрібно визначити:

— очікувану тривалість виконання проекту;

— імовірність події, що фактична тривалість не перевищуватиме очікувану більше ніж на 2 тижні.

Табл. 10.6

Розв'язування. Побудуємо сітьову модель проекту (рис. 10.22) та обчислимо за формулами (10.17), (10.18) статистичні характери­стики (очікувані значення і стандартні відхилення) випадко­вих величин — тривалостей виконання кожної із робіт (див. табл. 10.7).

Рис. 10.22

Табл. 10.7

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

Рис. 10.23

Критичний шлях проекту утворюють дуги 1→ 4, 4→ 6 та 6 → 7 . Тому очікувана тривалість виконання проекту дорівнює:

Обчислимо дисперсію σ²(Т) випадкової величини Т-тривалості виконання проекту:

σ²(Т) = 0,83² + 1,83² + 1,83² = 7,4467.

Запитання і завдання для самоконтролю

1. Назвіть основні характеристики задач упорядкування та коор­динації.

2. Сформулюйте задачу календарного планування та назвіть осно­вні методи їх розв 'язування.

3. Назвіть сфери застосування сітьових графіків.

4. Назвіть основні елементи сітьового графіку та запишіть мето­дику побудови сітьового графіку.

5. Дайте визначення понять: критичний шлях, часовий резерв.

6. Яка основна ідея методу гілок та меж? В чому його особливість?

7. Як виконується розгалуження?

8. Як змінюються значення оцінок при розгалуженні множини допустимих розв 'язків на підмножині в методі гілок та меж?

9. Назвіть ознаки одержання замкнутого і оптимального маршру­тів у задачі комівояжера.

10. Як визначається критичний шлях проекту?

11. Розрахуйте часові характеристики робіт сітьових графіків ((Е(і), L(j), M(i,j), N(i,j) P(i,j)):

а)

б)

в)

г)