Побудова моделі та розрахунок її параметрів

Нехай маємо послідовність операцій, наведених в таблиці 2.1. Побу­дуємо для них мережевий граф (рис. 2.1).

Таблиця 2.1

Код операції	Операції, що передують даній	Тривалість операції	Потреба в трудових ресурсах
A	–
B	–
C	–
D	C
E	C
F	A
G	A
H	B, F
I	E, H
K	D, E, H, G

Рис. 2.1 – Граф мережі

Оскільки три роботи починаються одночасно, то початковою для них буде одна подія. Позначимо її індексом 1. Відповідні кінцеві події цих робіт позначимо індексами 2, 3, 4. Робота A є попередньою для робіт F та G, тому вони починаються з події 2. Аналогічно роботи B та F безпосередньо пере­дують роботі H, тому остання починається з події 3. Для робіт E та D безпо­середньо передуючими є роботи A та C. Тому ці роботи не можуть почи­натись з події 2. Для правильного відображення послідовності робіт уведемо фіктивну операцію A' від події 2 до події 4. Вона не має терміну і на графі позначена пунктирною лінією.

Робота F так само, як і робота B, передує лише роботі H, тому вони мають спільну завершальну подію з індексом 3. Аналогічно подія 5 є кінцевою для операцій E та H, а подія 6 – для D та G. Операція I розпочинається з події 5, а операція K – з події 6. Однак оскільки роботі K крім цих робіт передують ще й E та H, то від події 5 до події 6 також уведемо фіктивну операцію.

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

Остаточно граф мережі зображений на рис. 2.1.

Розрахуємо основні параметри подій мережі. Обчислимо спочатку ранні терміни настання подій, починаючи з початкової події. Для вихідної вершини i = 1 очевидно t_p(i) = 0. Для i = 2 маємо t_p(2) = 3, бо існує лише одна робота, завершення якої відповідає події 2. Для обчислення t_p(3) скористає­мося формулою (1.5) і заданими величинами t(2; 3) = 9 та t(1; 3) = 8:

t_p(3) = max{t_p(l) + t(1; 3); t_p(2) + t(2;4)} = max{0 + 8; 3 + 9} = 12.

Отже, t_р(3) = 12.

Аналогічно розрахуємо t_p(4), t_p(5), t_p(6), t_p(7):

t_p(4) = max{t_p(1) + t(1; 4); t_p(2) + t(2; 4)} = max{0 + 4; 3 + 0} = 4.

t_p(5) = max{t_p(3)+t(3; 5); t_p(4) + t(4;5)}= max{4 + 6; 12 + 7} = 19.

t_p(6) = max{t_p(2) + t(2; 6); t_p(5) + t(5; 6); t_p(3) + t(3; 6)} = max{3 + 5; 19 + 0; 4 + 10} = 19.

t_p(7) = max{t_p(5) + t(5;7); t_p(6) + t(6; 7)} = max{19 + 8; 19 + 6} = 27.

Отже, термін критичного шляху дорівнює 27 одиницям виміру часу.

Обчислені терміни запишемо в ліві сектори подій (рис. 2.2).

При розрахунку пізніх термінів здійснення подій t_п(i) розглядаємо вершини графу в послідовності зменшення їх нумерації. Для завершальної події пізній термін її звершення дорівнює ранньому, тому t_n(7) = 37. Пізні терміни інших подій обчислюємо, користуючись при потребі формулою (1.7):

t_n(6) = t_n(7) – t(6;7) = 27 – 6 = 21, бо для події 6 існує лише один наступний шлях (6; 7).

t_n(5) = min{t_n(7) – t(5; 7); t_n(6) – t(5; 6)} = min{27 – 8; 21 – 0} = 19.

t_n(4) = min{t_n(5) – t(4; 5); t_n(6) – t(4; 6)} = mіn{19 – 6; 21 – 10} = 11.

t_n(3) = t_n(5) – t(3; 5) = 19 – 7 = 12, бо для події 3 існує лише один нас­тупний шлях, який починається з операції (4; 5).

t_n(2) = mіn{t_n(3) – t(2; 3); t_n(6) – t(2;6)} = mіn{12 – 9; 21 – 5} = 3.

t_n(1) = 0.

Розраховані терміни запишемо в праві сектори подій. За формулою (1.8) обчислюємо резерв часу для кожної події:

R(1) = 0 – 0 = 0; R(3) = 12 – 12 = 0; R(6) = 21 – 19 = 2;

R(2)=3 – 3 = 0; R(4) = 11 – 4 = 7; R(7) = 27 – 27 = 0.

R(5) = 19 – 19 = 0;

Аналізуючи результати розрахунків, знаходимо події, які належать критичному шляху. В даному випадку він має вигляд A–F–H–I. На рис. 2.2 він позначений жирними лініями.

Рис. 2.2 – Граф мережі з обчисленими параметрами подій та критичним шляхом

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

Таблиця 2.2 – Обчислення параметрів робіт мережі

Операція (i, j)	Тривалість tij	Ранні роботи	Пізні роботи	Резерв
поч. tpn(i, j)	закінч. tpз(i, j)	поч. tпn(i, j)	закінч. tnз(i, j)	повний Rn(i, j)	вільний R2(i, j)
A (1, 2)
B (1, 3)
C (1, 4)
F (2, 3)
A' (2, 4)
G (2, 6)
H (3, 5)
D (4, 5)
E (4, 6)
H' (5, 6)
I (5, 7)
K (6, 7)

Пізній початок та раннє завершення роботи обчислимо, скористав­шись формулами (1.10) та (1.12).

Для обчислення повного резерву скористаємось формулою (1.14). Вільний резерв роботи зручно обчислити за формулою (1.17). Результати розрахунків занесемо до таблиці 2.2. Жирним виділені ті рядки, які відно­сяться до критичних операцій.

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

Таблиця 2.3 – Розрахунок резервів операцій графу мережі

Робота	Термін	Rn, (1.14)	R1, (1.15)	R2, (1.17)	Rн, (1.19)
(1; 2)		3 – 0 – 3 = 0	3 – 0 – 3 = 0	3 – 0 – 3 = 0	3 – 0 – 3 = 0
(1; 3)		12 – 0 – 8 = 4	12 – 0 – 8 = 4	12 – 0 – 8 = 4	12 – 0 – 8 = 4
(1; 4)		11 – 0 – 4 = 7	11 – 0 – 4 = 7	4 – 0 – 4 = 0	4 – 0 – 4 = 0
(2; 3)		12 – 3 – 9 = 0	12 – 3 – 9 = 0	12 – 3 – 9 = 0	12 – 3 – 9 = 0
(2; 4)		11 – 3 – 0 = 8	11 – 3 – 0 = 8	4 – 3 – 0 = 1	4 – 3 – 0 = 1
(2; 6)		21 – 3 – 5 = 13	21 – 3 – 5 = 13	19 – 3 – 5 = 11	19 – 3 – 5 = 11
(3; 5)		19 – 12 – 7 = 0	19 – 12 – 7 = 0	19 – 12 – 7 = 0	19 – 12 – 7 = 0
(4; 5)		19 – 4 – 6 = 9	19 – 11 – 6 = 2	19 – 4 – 6 = 9	19 – 11 – 6 = 2
(4; 6)		21 – 10 = 7	21 – 11 – 10 = 0	19 – 4 – 10 = 5	19 – 11 – 10 = – 2
(5; 6)		21 – 19 – 0 = 2	21 – 19 – 0 = 2	19 – 19 – 0 = 0	19 – 19 – 0 = 0
(5; 7)		27 – 19 – 8 = 0	27 – 19 – 8 = 0	27 – 19 – 8 = 0	27 – 19 – 8 = 0
(6; 7)		27 – 19 – 6 = 2	27 – 21 – 6 = 0	27 – 19 – 6 = 2	27 – 21 – 6 = 0

За результатами розрахунків можна зробити такі висновки. Частко­вий резерв першого виду часу роботи може бути використаний на збільшення терміну виконання даної та наступних робіт. Частковий резерв другого виду часу роботи може бути використаний на збільшення терміну виконання даної та попередніх робіт без зміни (порушення) резерву часу наступних робіт. Не­залежний резерв часу може бути використаний для збільшення терміну вико­нання лише даної роботи.

Побудуємо календарний графік виконання робіт. На ньому кожній роботі буде відповідати три лінії:

– перша – ранньому початку та ранньому завершенню роботи;

– друга (основна) – ранньому початку та пізньому завершенню роботи;

– третя – пізньому початку та пізньому завершенню роботи.

Сама верхня лінія відповідатиме критичним роботам. Оскільки для цих робіт ранні та пізні терміни збігаються, то лінія лише одна. Календарний графік зображений на рис. 2.3. Фіктивні роботи на графіку відображати не будемо.

Рис. 2.3 – Календарний графік

Виконання робіт допускає використання трудових ресурсів (табл. 2.1).

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

Побудова плану здійснюється таким чином. У початковий момент часу розпочинаються три роботи – A, B, C. Для їх виконання потрібні сумар­ні ресурси 4 + 1 + 3 = 8 од. Через три одиниці часу робота A завершується. При цьому вивільняються 4 трудові одиниці. Однак розпочинаються роботи F (критична) і G, які потребують 4 та 7 одиниць відповідно. Отже, сумарна потреба в ресурсах становить 8 – 4 + 4 + 7 = 15 од.

При t = 4 завершується операція С, при цьому вивільняються три тру­дових одиниці. Однак розпочинаються роботи E та D. Тому сумарна потреба в ресурсах буде становити 15 – 3 + 4 + 2 = 18 од. Така потреба буде необхідна до t = 7, коли завершуються роботи B та G. При цьому потреба в ресурсах буде становити 18 – 1 – 7 = 10. Продовжуючи такий аналіз, отримаємо весь ранній календарний план виконання робіт (рис. 2.4). Зауважимо, що фіктивні роботи не впливають на побудову плану, оскільки не потребують ресурсів, і на плані не відображені.

В нижній частині подвійною лінією відмічена потреба в ресурсах для критичних операцій.

Аналогічно побудуємо пізній календарний план (рис. 2.5).

Рис. 2.4 – Ранній календарний план

Враховуючи що, тепер всі роботи розпочинаються в пізній термін, то з моменту часу t = 0 розпочинається лише операція A (критична). Витрати ресурсів становлять 4 од. У момент часу t = 3 вона закінчується і розпочина­ється операція F. Решта операцій мають більший термін пізнього початку, тому ще не розпочинаються. Оскільки операція F також потребує 4-х одиниць трудових ресурсів, то їх загальна потреба не змінилась. В момент часу t = 4 роз­починається робота B, яка потребує одну одиницю трудових ресурсів, тому загальні потреби в ресурсах зросли до п’яти одиниць. В момент часу t = 7 розпочинається робота C, що призводить до подальшого збільшення загаль­них потреб ресурсів до 8 одиниць. Продовжуючи аналіз календарного графі­ка, побудуємо весь календарний план.

Аналіз обох планів показує, що для раннього плану максимальна потреба в трудових ресурсах становить 18 одиниць, а для пізнього – 16 оди­ниць. Поліпшити плани можна шляхом зміщення початку виконання некри­тичних операцій.

Рис. 2.5 – Пізній календарний план

Розглянемо ранній план. Якщо початок операції G перенести в мо­мент часу t = 14, то в період часу з t = 3 до t = 8 потреба в ресурсах змен­шиться на 7 од, а в період з t = 14 до t = 19 збільшиться на 7 од. В результаті максимальна потреба в ресурсах зменшиться до 11 од. Ранній план матиме наступний вигляд (рис. 2.6).

Якщо аналогічно перенести початок роботи E в момент часу t = 8, то максимальна потреба в трудових ресурсах зменшиться ще на одну одиницю і становитиме 10 од. (рис. 2.7).

Подальші переміщення початків робіт до поліпшення плану не приз­веде. Отриманий останній план більш рівномірно використовує трудові ресурси.

Рис. 2.6 – Оптимальний ранній план

Рис. 2.7 – Поліпшений ранній план

ЗАВДАННЯ КУРСОВОЇ РОБОТИ

3.1. Загальні вказівки до оформлення

Номер варіанта завдання студент обирає відповідно до його порядко­вого номера в списку групи.

При захисті курсової роботи кожен студент повинен представити пояс­нювальну записку. В ній необхідно вказати мету роботи, надати короткий теоретичний опис досліджуваної предметної області, обґрунтування обраних шляхів і прийнятих рішень, а також відобразити хід роботи. Пояснювальна записка повинна містити вихідні дані завдання; усі проміжні розрахунки із необхідними поясненнями; кінцеві результати розрахунків; аналіз отриманих результатів і висновки.

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

Текстова частина роботи виконується згідно з прийнятим в універси­теті стандартом щодо оформлення документів (Текстові документи. Загальні вимоги СОУ 207.01:2004).

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