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

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

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

(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_nT_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)):

а)

б)

в)

г)