Багато великі проекти, такі як будівництво будинку, виготовлення верстата, розробка автоматизованої системи бухгалтерського обліку тощо, можна розбити на велику кількість різних операцій (робіт). Деякі з цих операцій можуть виконуватися одночасно, інші - тільки послідовно: одна операція після закінчення інший. Наприклад, при будівництві будинку можна поєднати в часі внутрішні оздоблювальні роботи та роботи з благоустрою території, проте зводити стіни можна тільки після того, як буде готовий фундамент.
Завдання планування робіт з здійсненню деякого проекту полягають у визначенні часу можливого закінчення як усього проекту в цілому, так і окремих робіт, що утворюють проект; у визначенні резервів часу для виконання окремих робіт; у визначенні критичних робіт, тобто таких робіт, затримка у виконанні яких веде до затримці виконання всього проекту в цілому; в управлінні ресурсами, якщо такі маються і т.п.
Нехай деякий проект 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). p> Зрозуміло, що мережевий графік будь-якого проекту не повинен містити контурів. Дійсно, нехай вузли 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
Кінцевою метою побудови мережевої моделі є отримання інформації про можливі терміни виконання як окремих робіт, так і про можливий термін виконання всього проекту в цілому. Позначимо через 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) дає найбільш ранній можливий т...
