Багато великих проекти, такі як
будівництво будинку, виготовлення
верстата, розробка автоматизованої системи бухгалтерського обліку і т.д., можна розбити на велику кількість різних операцій (робіт). Деякі з цих операцій можуть виконуватися одночасно, інші - тільки послідовно: одна
операція після закінчення іншої. Наприклад, при будівництві будинку можна поєднати в часі внутрішні оздоблювальні
роботи та
роботи з благоустрою території, проте зводити стіни можна тільки після
того, як буде готовий фундамент.
Завдання
планування робіт по здійсненню деякого проекту полягають у визначенні часу можливого закінчення як всього проекту в цілому, так і окремих робіт, що утворюють проект; у визначенні резервів часу для виконання окремих робіт; у визначенні критичних робіт, тобто таких робіт, затримка у виконанні яких веде до затримки виконання всього проекту в цілому; в управлінні ресурсами, якщо такі є і т.п.
Нехай деякий проект W складається з робіт V
1 ,..., V
n; для кожної роботи V
k, відомо, чи може бути досить точно оцінений час її виконання t (V
k). Крім того, для кожної роботи V
k відомий, можливо порожній, список предше (V
k) робіт, які безпосередньо передують виконанню роботи V
k. Інакше кажучи,
робота V
k може почати виконуватися тільки після завершення всіх робіт, що входять до списку предше (V
k). Для зручності, в список робіт проекту W додамо два фіктивні роботи s і p, де робота s позначає початок всього проекту W. а робота p - завершення робіт за проектом W. При цьому будемо вважати, що робота s передує всім тим
роботам vÎW, для яких список предше (v) порожній, інакше кажучи, для всіх таких робіт vÎW покладемо предше (v) = {s}. Покладемо далі предше (s) = Æ, предше (p) = {vÎW: v не входить до жодного списку предше (w)}, тобто вважаємо, що роботу p передують всі ті роботи, які можуть виконуватися самими останніми. Час виконання робіт s і p
природно покласти рівними нулю: t (s) = t (p) = 0.
Весь проект W тепер зручно представити у вигляді
мережі G = (V, E, c). Орієнтований зважений граф G = (V, E, c) називається мережею.
Мережа може бути представлена матрицею ваг дуг, масивами смежностей СЛІД або предше, або списками СЛІД [v] або пе [v]. При цьому записи в списках суміжності складаються з трьох компонент: поля назви вузла, поля ваги
відповідної дуги і поля посилання на наступний запис), де
мережа G = (V, E, c) визначимо за правилами:
1. V = W, тобто безліччю вузлів оголосимо безліч робіт;
2. E = {(v, w): vÎПРЕДШ (w)}, тобто відношення передування задає дуги в мережі;
3. c (v, w) = t (w).
Так побудовану мережу G часто називають мережевим графіком виконання робіт за проектом W. Легко бачити, що списки смежностей цієї мережі предше [v] збігаються із заданими для проекту списками попередніх робіт предше (v).
Зрозуміло, що мережевий графік будь-якого проекту не повинен містити контурів. Дійсно, нехай вузли V
k 1, V
k 2 ,..., V
kr = V
k 1 утворюють контур в мережі G. Це означає, що робота V
k 2 не може початися раніше, ніж буде завершено роботу V
k 1, робота V
k 3 - раніше, ніж завершиться робота V
k 2, і т.д., і, нарешті, V
kr = V
k 1 - раніше, ніж буде завершено роботу V
kr -1. Але тоді ніяка з робіт V
k 1 ,..., V
kr ніколи не зможе бути виконана. А кожен реальний проект повинен допускати можливість його завершення. Отже, в мережевому графіку немає контурів.
Відсутність контурів в мережі G дозволяє пронумерувати роботи проекту W таким чином, щоб для кожної дуги (V
i, V
j) мережі G виконувалася умова i <j, тобто кожна дуга йде з вузла з меншим номером у вузол з великим номером. Здійснити таку нумерацію вузлів мережі G можна за допомогою алгоритму топологічного сортування. Тому надалі будемо вважати, що вузли в мережі G топологічно відсортовані.
Кінцевою метою побудови мережевої моделі є отримання інформації про можливі
терміни виконання як окремих робіт, так і про можливий термін виконання всього проекту в цілому. Позначимо через PBИП (v) (
відповідно PHAЧ (v)) найбільш ранній можливий термін виконання роботи v (відповідно найбільш ранній можливий термін початку роботи v). Зручно вважати, що PBИП (s) = PHAЧ (s) = 0. Оскільки почати виконувати роботу v можна тільки після того, як будуть виконані всі роботи, що передують даній роботі v, то отримаємо такі формули для розрахунку значень PHAЧ (v) і PBИП (w):
PHAЧ (v) = МАКС {PBИП (w): wÎПРЕДШ (v)},
PBИП (v) = PHAЧ (v) + t (v).
Значення PBИП (p) дає найбільш ранній можливий термін завершення всього проекту в цілому. Наведемо запис алгоритму, безпосередньо обчислює характеристики РНАЧ і РВИП.
АЛГОРИТМ 1.
Дані: Мережевий графік G робіт V, заданий списками предше (v), vÎV.
Результати: Найбільш ранні можливі терміни початку і виконання робіт РНАЧ (v), РВИП (v), vÎV.
Крок 1. Оголосити можливі ранні терміни початку РНАЧ (v) та виконання РВИП (v) робіт рівними нулю. Поточною вершиною оголосити першу вершину v
k = v
1. Крок 2. Всім вершин v попереднім поточної вершині v
k, значення РНАЧ (v
k) присвоїти максимум зі значень РВИП (v) і РНАЧ (v
k). Значення РВИП (v
k) покласти рівним значенням РНАЧ (v
k) плюс час виконання самої роботи поточної вершини t (v
k). Крок 3. Якщо є наступна вершина (робота) після поточної, то оголосити її поточної вершиною v
k, інакше перейти в Крок 5.
Крок 4. Повернутися в Крок 2.
Крок 5. Видати найбільш ранні можливі терміни початку і виконання робіт РНАЧ (v), РВИП (v), vÎV, кінець роботи алгоритму.
Нехай T - плановий термін виконання проекту W. Ясно, що Т має задовольняти
нерівності Т> = РВИП (V
n +1). Через ПВИП (v) (відповідно ПНАЧ (v)) позначимо найбільш пізній допустимий термін виконання (початку)
роботи v, то є
такий термін, який не збільшує термін Т реалізації всього проекту.
Значення можливих і допустимих
термінів виконання робіт дозволяють визначити резерви часу для виконання тієї чи іншої роботи. Повний резерв (іноді його називають сумарний) часу виконання робіт визначається за формулою:
PE3EPB (v) = ПHAЧ (v)-PHAЧ (v).
Значення PE3EPB (v) дорівнює максимальній затримці у виконанні роботи v, не впливає на плановий термін Т. Зрозуміло, що справедливо і така рівність: РЕЗЕРВ (v) = ПВИП (v)-РВИП (v).
Роботи, які мають нульовий резерв часу, називаються критичними. Через будь-яку таку роботу проходить деякий максимальний sp-шлях у мережі G. Критичні праці характеризуються тим, що будь-яка затримка в їх виконанні
автоматично веде до збільшення часу виконання всього проекту.
Наведемо запис алгоритму, безпосередньо обчислює характеристики ПВИП і ПНАЧ.
АЛГОРИТМ 2.
Дані: Мережевий графік G робіт V, заданий списками предше (v), vÎV, плановий термін закінчення проекту - Т.
Результати: Найбільш пізні допустимі строки виконання і початку робіт ПВИП (v) і ПНАЧ (v).
Крок 1. Оголосити для всіх робіт vÎV значення найбільш пізнього строку виконання робіт рівним Т - значенням планового терміну закінчення проекту і вершину v
p фіктивної роботи p оголосити поточної v
k. Крок 2. Присвоїти значення ПНАЧ поточної роботи v
k рівним значенням ПВИП роботи і відняти час виконання поточної роботи.
Крок 3. Присвоїти значенням ПВИП (v) для всіх робіт vÎПРЕДШ (v) попередніх поточній роботі v
k мінімальне значення із значень ПВИП виконання роботи v або ПНАЧ виконання поточної роботи v
k, якщо таких немає перейти в Крок 4.
Крок 4. Якщо є попередня вершина (робота) до поточної, то оголосити її поточної, інакше перейти в Крок 6.
Крок 5. Перейти в Крок 2.
Крок 6. Видати найбільш пізні допустимі строки виконання і початку робіт ПВИП (v) і ПНАЧ (v), кінець роботи алгоритму.
Проілюструємо роботу наведених алгоритмів на наступних прикладах:
Приклад 1: Проект гаража для стоянки автонавантажувачів.
n
| Найменування роботи
| Предшеству ющіе роботи
| Час ви-конання t (v k)
|
1
| Початок проекту (фіктівн. робота)
| Ні
| 0
|
2
| Зрізування рослинного шару грунту
| 1
| 5
|
3
| Монтаж каркаса
| 2
| 30
|
4
| Обшивка стін профнастилом
| 3
| 15
|
5
| Покрівля з профнастилу
| 3
| 12
|
6
| Заповнення отвору воротами
| 4
| 5
|
7
| Масляна забарвлення воріт і профнастилу
| 5,6
| 10
|
8
| Щебеневе підстава під підлоги
| 7
| 3
|
9
| Асфальтове покриття
| 8
| 3
|
10
| Прибирання будівельного сміття після будує.
| 7
| 3
|
11
| Кінець проекту (фіктивна робота)
| 9,10
| 0
|
Рис 1. Проект гаража для стоянки автонавантажувачів.
Знайдемо значення найбільш раннього початку та виконання робіт проекту за допомогою алгоритму 1. Роботу алгоритму викладемо у вигляді
послідовності виконуваних кроків.
Крок n
| Дії виконуються кроком
|
1
| Оголошення значень РНАЧ (v) і РВИП (v), vÎV рівними нулю. Поточна вершина v k = 1.
|
2
| Вершин попередньої першої немає. РВИП (1) = РНАЧ (1) + t (1). {РНАЧ (1) стало рівним 0}
|
3
| Поточна вершина v k = 2.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (2) = МАКС {РВИП (1), РНАЧ (2)} {РНАЧ (2) стало рівним 0} РВИП (2) = РНАЧ (2) + t (2) {РВИП (2) стало рівним 5}.
|
3
| Поточна вершина v k = 3.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (3) = МАКС {РВИП (2), РНАЧ (3)} {РНАЧ (3) стало рівним 5} РВИП (3) = РНАЧ (3) + t (3) {РВИП (3) стало рівним 35}.
|
3
| Поточна вершина v k = 4.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (4) = МАКС {РВИП (3), РНАЧ (4)} {РНАЧ (4) стало рівним 35} РВИП (4) = РНАЧ (4) + t (4) {РВИП (4) стало рівним 50}.
|
3
| Поточна вершина v k = 5.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (5) = МАКС {РВИП (3), РНАЧ (5)} {РНАЧ (5) стало рівним 35} РВИП (5) = РНАЧ (5) + t (5) {РВИП (5) стало рівним 47}.
|
3
| Поточна вершина v k = 6.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (6) = МАКС {РВИП (4), РНАЧ (6)} {РНАЧ (6) стало рівним 50} РВИП (6) = РНАЧ (6) + t (6) {РВИП (6) стало рівним 55}.
|
3
| Поточна вершина v k = 7.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (7) = МАКС {РВИП (5), РНАЧ (7)} {РНАЧ (7) стало рівним 47} РНАЧ (7) = МАКС {РВИП (6), РНАЧ (7)} {РНАЧ (7) стало рівним 55} РВИП (7) = РНАЧ (7) + t (7) {РВИП (7) стало рівним 65}.
|
3
| Поточна вершина v k = 8.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (8) = МАКС {РВИП (7), РНАЧ (8)} {РНАЧ (8) стало рівним 65} РВИП (8) = РНАЧ (8) + t (8) {РВИП (8) стало рівним 68}.
|
3
| Поточна вершина v k = 9.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (9) = МАКС {РВИП (8), РНАЧ (9)} {РНАЧ (9) стало рівним 68} РВИП (9) = РНАЧ (9) + t (9) {РВИП (9) стало рівним 71}.
|
3
| Поточна вершина v k = 10.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (10) = МАКС {РВИП (7), РНАЧ (10)} {РНАЧ (10) стало рівним 65}
|
3
| Поточна вершина v k = 11.
|
4
| Перехід в Крок 2.
|
2
| РНАЧ (11) = МАКС {РВИП (9), РНАЧ (11)} {РНАЧ (11) стало рівним 71} РНАЧ (11) = МАКС {РВИП (10), РНАЧ (11)} {РНАЧ (11) стало рівним 71}
|
3
| Перехід в Крок 5.
|
5
| Кінець роботи алгоритму, видача значень найбільш раннього початку та виконання робіт.
|
Таблиця результатів роботи алгоритму.
n
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
|
РНАЧ (v)
| 0
| 0
| 5
| 35
| 35
| 50
| 55
| 65
| 68
| 65
| 71
|
РВИП (v)
| 0
| 5
| 35
| 50
| 47
| 55
| 65
| 68
| 71
| 68
| 71
|
Отримали, що мінімальний час, необхідний для виконання проекту одно Т = РВИП (11), Т = 71. Тепер знайдемо за допомогою алгоритму 2 значення часу найбільш пізнього початку і виконання робіт. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Крок n
| Дії виконуються кроком
|
1
| Оголошення значень ПВИП (v), vÎV рівним Т. Поточна вершина v k = 11.
|
2
| ПНАЧ (11) = ПВИП (11)-t (11) {ПНАЧ (11) стало рівним 71}.
|
3
| ПВИП (9) = МІН {ПВИП (9), ПНАЧ (11)} {ПВИП (9) стало рівним 71} ПВИП (10) = МІН {ПВИП (10), ПНАЧ (11)} {ПВИП (10) стало рівним 71}
|
4
| Поточна вершина v k = 10.
|
5
| Перехід в Крок 2.
|
2
| ПНАЧ (10) = ПВИП (10)-t (10) {ПНАЧ (10) стало рівним 68}
|
3
| ПВИП (7) = МІН {ПВИП (7), ПНАЧ (10)} {ПВИП (7) стало рівним 68}
|
4
| Поточна вершина v k = 9.
|
5
| Перехід в Крок 2.
|
2
| ПНАЧ (9) = ПВИП (9)-t (9) {ПНАЧ (9) стало рівним 68}
|
3
| ПВИП (8) = МІН {ПВИП (8), ПНАЧ (9)} {ПВИП (8) стало рівним 68}
|
4
| Поточна вершина v k = 8.
|
5
| Перехід в Крок 2.
|
2
| ПНАЧ (8) = ПВИП (8)-t (8) {ПНАЧ (8) стало рівним 65}
|
3
| ПВИП (7) = МІН {ПВИП (7), ПНАЧ (8)} {ПВИП (7) стало рівним 65}
|
4
| Поточна вершина v k = 7.
|
5
| Перехід в Крок 2.
|
2
| ПНАЧ (7) = ПВИП (7)-t (7) {ПНАЧ (7) стало рівним 55}
|
3
| ПВИП (5) = МІН {ПВИП (5), ПНАЧ (7)} {ПВИП (5) стало рівним 55} ПВИП (6) = МІН {ПВИП (6), ПНАЧ (7)} {ПВИП (6) стало рівним 55}
|
4
| Поточна вершина v k = 6.
|
5
| Перехід в Крок 2.
|
2
| ПНАЧ (6) = ПВИП (6)-t (6) {ПНАЧ (6) стало рівним 50}
|
3
| ПВИП (4) = МІН {ПВИП (4), ПНАЧ (6)} {ПВИП (5) стало рівним 50}
|
4
| Поточна вершина v k = 5.
|
5
| Перехід в Крок 2.
|
2
| ПНАЧ (5) = ПВИП (5)-t (5) {ПНАЧ (5) стало рівним 43}
|
3
| ПВИП (3) = МІН {ПВИП (3), ПНАЧ (5)} {ПВИП (3) стало рівним 43}
|
4
| Поточна вершина v k = 4.
|
5
| Перехід в Крок 2.
|
2
| ПНАЧ (4) = ПВИП (4)-t (4) {ПНАЧ (4) стало рівним 35}
|
3
| ПВИП (3) = МІН {ПВИП (3), ПНАЧ (4)} {ПВИП (3) стало рівним 35}
|
4
| Поточна вершина v k = 3.
|
5
| Перехід у крок 2.
|
2
| ПНАЧ (3) = ПВИП (3)-t (3) {ПНАЧ (3) стало рівним 5}
|
3
| ПВИП (2) = МІН {ПВИП (2), ПНАЧ (3)} {ПВИП (2) стало рівним 5}
|
4
| Поточна вершина v k = 2.
|
5
| Перехід в Крок 2.
|
2
| ПНАЧ (2) = ПВИП (2)-t (2) {ПНАЧ (2) стало рівним 0}
|
3
| ПВИП (1) = МІН {ПВИП (1), ПНАЧ (2)} {ПВИП (1) стало рівним 0}
|
4
| Поточна вершина v k = 1.
|
5
| Перехід в Крок 2.
|
2
| ПНАЧ (1) = ПВИП (1)-t (1) {ПНАЧ (1) стало рівним 0}
|
3
| Перехід в Крок 4.
|
4
| Перехід в Крок 6.
|
6
| Кінець роботи алгоритму, видача значень часу найбільш пізнього початку і виконання робіт.
|
Дамо таблицю результатів роботи алгоритму з результатами попереднього алгоритму і порахуємо резерв часу для кожної роботи за формулою PE3EPB (v) = ПНАЧ (v)-PHAЧ (v) або РЕЗЕРВ (v) = ПВИП (v)-РВИП (v).
є 1, 2, 3, 4, 6, 7, 8, 9, 11, які і утворюють в мережі G критичний шлях.
виконані при Т = 71.
у приміщення виробничого цеху.
Рис 2. Проект складу сажі та інших матеріалів у приміщення виробничого цеху.
Знайдемо значення найбільш раннього початку та виконання робіт проекту за допомогою алгоритму 1. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Таблиця результатів роботи алгоритму.
Отримали, що мінімальний час, необхідний для виконання проекту одно Т = РВИП (11), Т = 29. Тепер знайдемо за допомогою алгоритму 2 значення часу найбільш пізнього початку і виконання робіт. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Дамо таблицю результатів роботи алгоритму з результатами попереднього алгоритму і порахуємо резерв часу для кожної роботи за формулою PE3EPB (v) = ПHAЧ (v)-PHAЧ (v) або РЕЗЕРВ (v) = ПВИП (v)-РВИП (v).
З табл видно, що критичними роботами є 1, 2, 6, 8, 10, 11, які і утворюють в мережі G критичний шлях.
виконані при Т = 29.
Приклад 3: Проект водопостачання та зовнішньої каналізації при забудови кварталу по вул. Токарів-Синяева в м. Єкатеринбурзі.
Рис 3. Проект водопостачання та зовнішньої каналізації при забудови кварталу по вул. Токарів-Синяева в м. Єкатеринбурзі.
Знайдемо значення найбільш раннього початку та виконання робіт проекту за допомогою алгоритму 1. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Таблиця результатів роботи алгоритму.
Отримали, що мінімальний час, необхідний для виконання проекту одно Т = РВИП (11), Т = 64. Тепер знайдемо за допомогою алгоритму 2 значення часу найбільш пізнього початку і виконання робіт. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.