Розрахунок мережного графіка

Граф, деякі вершини якого виділені, називається мережею. Виділені вершини називаються полюсами мережі. Наприклад, дерево з коренем можна розглядати як однополюсну мережу. Ізоморфізмом мереж називається ізоморфне відображення їхніх графів, при якому полюси обов'язково переходять у полюси.

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

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

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

Розглянемо основні розрахункові параметри мережного графіка і формули для їхнього розрахунку. Позначимо: t _p - ранній термін настання події; t _n ­- пізній термін настання події; t _{i j} - час операцій; i - номер попередньої подiї; j - номер наступної події; R _п - повний резерв часу операції (i, j); R - резерв часу події; t _{p o} - ранній термін закінчення операції (i, j); t _{п о} - пізній термін закінчення операції (i, j).

Основні тимчасові параметри мережного графіка з детермінованим часом виконання операцій розраховуються за такими формулами:

1) ранній термін настання події j

æ t ⁱ _p + t _{i j} , якщо до події j підходить одна

t ^j _p = í операція;

è max {t ⁱ _p + t _{i j}}, якщо до події j підходить декілька опе-

{i} рацій;

2) пізній термін настання події j

æ t ^j _п - t _{i j}, якщо від події j відходить одна

t ⁱ _п = í операція;

è min {t ^j _п - t _{i j}}, якщо від події j відходить

{j} декілька операцій;

3) резерв часу події

R = t _n - t _p ;

4) ранній термін закінчення операції (i, j)

t _{p о} = t _p + t _{i j,} при t _{p o} = 0;

5) пізній термін закінчення операції (i, j)

t _{n о} = t _n ;

6) повний резерв часу операції (i, j)

R _n = t_n - t_p - t _{i j} ,

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

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

Розрахунок t _{p o} і t _p ведеться від початку мережного графіка до кінця, а розрахунок t _n і t _{n о} - від кінця до початку. При цьому для кінцевої події t _p = t _n .

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

Приклад. У таблиці записані роботи (i, j) і час їхнього виконання t_ij.

i, j	1, 2	1, 3	2, 3	2, 5	3, 4	3, 6	4, 5	4, 6	4, 7	5, 7	6,7
tij

Представимо мережний графік (рис. 2.11) і визначимо його параметри за подіями і роботами.

Розв'язання. За даними роботами i, j будуємо мережний графік. Подій усього 7, значить рисуємо 7 вершин. Треба так розташувати вершини, щоб роботи i, j не перетиналися.

27

2 4 5 2

2 2 29 10

3

2 12 39

7 0

0 15 39

1 0 5 4 2 5

0 17 8

7 8

8 8

3 0 23 31

8 6 0

t _p 31

N R

t _n

Рис. 2.11. Мережний графік

Знаходимо параметри за подіями.

1. Ранній термін настання події i, t_p (i). Це максимальний шлях від початкової події до i-ї події:

t_p(1) = 0; t_p(2) = t1_,2 = 2.

У третю подію входять 2 роботи: (2, 3) і (1, 3), значить

t_p(3)=max{t_p(2) + t_2,3 ; t_p(1) + t_1,3}=max{2+5, 8}= 8.

У четверту подію входить одна робота (3, 4)

t_p(4) = t_p(3)+t_3,4 = 8+7=15.

У п'яту подію входять 2 роботи: (2, 5) і (4, 5), значить

t_p(5)=max{t_p(2) + t_2,5 ; t_p() + t_4,5}=max{2+4, 15+12}= 27.

У шосту подію входять дві роботи: (4, 6) і (3, 6), значить

t_p(6)=max{t_p(4) + t_2,5 ; t_p(3) + t_3,6}=max{15+4, 8+23}= 31.

У сьому подію входять три роботи: (5, 7); (4, 7); (6, 8) значить

t_p(7)=max{t_p(5) + t_5,7 ; t_p(4) + t_4,7; t_p(6) + t_6,7}=

max{5+5, 27+10,31+8}= 39.

2. Пізній термін настання події i, t_n (i) - це різниця між тривалістю максимального шляху l_max і шляху найбільшої тривалості від даної події i до кінцевої.

Розраховується t_n (i) за оберненою схемою t_p (i). Значить, розрахунок починаємо від кінцевої події, орієнтуємося на вихідні роботи, беремо мінімум різниці.

Для кінцевої події

t_n(7) = t_p(7)=39.

З шостої події виходить одна робота (6, 7)

t_n(6) = t_n(7) - t_6,7 = 39 - 8 = 31.

З п'ятої події виходить одна робота (5, 7)

t_n(5) = t_n(7) - t_5,7 = 39 - 10 = 29.

З четвертої події виходить 3 роботи (4, 5), (4, 6), (4, 7)

t_n(4) = min{ t_n(5) - t_4,5 ; t_n(6) - t_4,6 ; t_n(7) - t_4,7 }=

min{29 - 12; 31 - 4; 39 - 5}= 17.

З третьої події виходить 2 роботи: (3, 4), (3, 6)

t_n(3)=min{t_n(4) - t_3,4 ; t_n(6) - t_3,6}=min{17 - 7; 31 - 23}= 8.

З другої події виходить 2 роботи: (2, 5); (2, 3)

t_n(2)=min{t_n(5) - t_2,5 ; t_n(3) - t_1,3}=min{8 - 5; 29 - 4}= 3.

З початкової події виходить 2 роботи: (1, 2); (1, 3)

t_n(1)=min{t_n(2) - t_1,2 ; t_n(3) - t_1,3}=min{3 - 2; 8 - 8}= 0.

Для початкової події повинна виконуватися умова:

t_p(1) = t_n (1) = 0.

3. Знаходимо резерв часу за подіями:

R(i) = t_n(i) - t_p(i);

R(1) = 0; R(2) = 3-2 =1; R(3) = 8-8 = 0;

R(4) = 17-15 = 2; R(5) = 29-27 = 2; R(6) = 31-31 = 0;

R(7) = 39-39 = 0.

4. Критичний шлях проходить за подіями з нульовим резервом часу R(i) = 0, тобто 1, 3, 6, 7 (виділено на графі). Довжина критичного шляху L_кр - це самий довгий шлях від початкової події до кінцевої:

L_кр = t_p(7) = 39.

Розрахуємо необхідні параметри за роботами.

5. Ранній термін закінчення роботи (i, j):

t_{p. o}(i, j)=t_p(i) + t_i,j;

t_{p. o}(1,2)=t_p(1) + t_1,2 = 0+2 = 2;

t_{p. o}(1,3)=t_p(1) + t_1,3 = 0+8 = 8;

t_{p. o}(2,3)=t_p(2) + t_2,3 = 2+5 = 7;

t_{p. o}(2,5)=t_p(2) + t_2,5 = 2+4 = 6;

t_{p. o}(3,4)=t_p(3) + t_3,4 = 8+7 = 15;

t_{p. o}(3,6)=t_p(3) + t_3,6 = 8+23 = 31;

t_{p. o}(4,5)=t_p(4) + t_4,5 = 15+12 = 27;

t_{p. o}(4,6)=t_p(4) + t_4,6 = 15+4 = 19;

t_{p. o}(4,7)=t_p(4) + t_4,7 = 15+5 = 20;

t_{p. o}(5,7)=t_p(5) + t_5,7 = 27+10 = 37;

t_{p. o}(6,7)=t_p(6) + t_6,7 = 31+8 = 39.

6. Пізній термін настання закінчення роботи (i, j):

t_{n. o} (1,2) = t_n(2) = 3; t_{n. o} (2,3) = t_n(3) = 8;

t_{n. o} (1,3) = t_n(3) = 8; t_{n. o} (2,5) = t_n(5) = 29;

t_{n. o} (3,4) = t_n(4) = 17; t_{n. o} (4,5) = t_n(5) = 29;

t_{n. o} (3,6) = t_n(6) = 31; t_{n. o} (4,6) = t_n(6) = 31;

t_{n. o} (5,7) = t_n(7) = 39; t_{n. o} (4,7) = t_n(7) = 39;

t_{n. o} (6,7) = t_n(7) = 39.

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

R_n(i, j) = t_n (j) - t_p(i) - - t_i,j;

R_n(1,2) = t_n (2) - t_p(1) - t_1,2 = 3-0-2 = 1;

R_n(1,3) = t_n (3) - t_p(1) - t_1,3 = 8-0-8 = 0;

R_n(2,3) = t_n (3) - t_p(2) - t_2,3 = 8-2-5 = 1;

R_n(2,5) = t_n (5) - t_p(2) - t_2,5 = 8-2-4 = 2;

R_n(3,4) = t_n (4) - t_p(3) - t_3,4 = 17-8-7 = 2;

R_n(3,6) = t_n (6) - t_p(3) - t_3,6 = 31-8-23 = 0;

R_n(4,5) = t_n (5) - t_p(4) - t_4,5 = 29-15-12 = 2;

R_n(4,6) = t_n (6) - t_p(4) - t_4,6 = 31-15-4 = 12;

R_n(5,7) = t_n (7) - t_p(5) - t_5,7 = 39-27-10 = 2;

R_n(6,7) = t_n (7) - t_p(6) - t_6,7 = 39-31-8 = 0.

Робота (4, 7) має великий резерв часу (12), значить можна з цієї роботи зняти на даному етапі ресурси і перекинути їх на роботи, що лежать на критичному шляху. Аналогічно, роботи (2, 5), (3, 4), (4, 5), (5, 7) мають резерв часу рівний 2. Роботу (2, 3) вважаємо під критичною, а роботи з нульовим резервом часу - критичні. На рис. 2.11 критичний шлях відзначений жирною лінією.

Дата добавления: 2014-11-29