2.Структура та правила побудови мережі
Мережа CPU/PERT має наступну структуру:
кожна дуга мережі представляє операцію та обов’язково має певну орієнтацію;
мережа проекту є безконтурною;
не припускається ймовірнісне розгалуження (як у стохастичних лотерей);
робота не може початися, поки всі попередні не будуть виконані;
робота позначається парою подій, що її однозначно ідентифікують.
Побудова мережі відбувається на основі заданого відношення слідування (передування) на множині операцій (робіт) проекту. Це відношення є транзитивним. Операціям проекту відповідають дуги мережі, вузлам — події. Подія вважається такою, що звершилася, якщо всі роботи, що входять в неї, виконані.
Мережа будується за наступними правилами:
кожній роботі проекту відповідає одна і лише одна дуга;
кожна робота однозначно ідентифікується парою подій;
при побудові мережі необхідно знати: які роботи повинні бути завершені безпосередньо перед початком наступної, або які роботи безпосередньо слідують за кожною з робіт проекту; які роботи можуть виконуватися одночасно.
Послідовність побудови мережі включає наступні кроки:
структуризація проекту до множини взаємнопов’язаних робіт, виконання яких означатиме реалізацію проекту;
отримання відношення безпосереднього передування (слідування) на множині робіт задачі шляхом аналізу її змістовної постановки;
визначення множин початкових та завершальних робіт проекту;
побудова мережі проекту з включенням у необхідних випадках фіктивних робіт. Фіктивні роботи мають нульову тривалість та не потребують для свого виконання ніяких ресурсів і вводяться з метою забезпечення логічних умов слідування робіт проекту та для їх однозначної ідентифікації парою подій;
нумерація вузлів (подій) мережі таким чином, щоб будь-яка робота виходила з події з меншим номером і входила в подію з більшим номером (
).
Розглянемо на прикладах основні випадки введення фіктивних робіт.
Приклад 1.
Заданий наступний фраґмент відношення
передування для мережі:
(запис
означає, що робота
безпосередньо передує роботі
).
Необхідно побудувати відповідний
фраґмент мережі проекту.
Якщо спробувати безпосередньо побудувати відповідний фраґмент мережі, то ми отримаємо а):
У випадку а роботи B та D ідентифікуються
однією парою подій
,
що неприпустимо. Тому вводимо фіктивну
роботу Е — позначена на b пунктиром, в
результаті чого кожна з робіт фраґменту
однозначно ідентифікується різними
парами подій.
Приклад 2.
Заданий наступний фрагмент відношення
передування:
. Побудуємо відповідний фраґмент мережі
Варіант а є неприпустимим, тому що він
реалізує інше, ніж задане, відношення
передування, а саме
.
У варіанті b проблема розв’язана за
рахунок введення фіктивної роботи
.
Приклад 3. Необхідно побудувати мережу проекту за наступними відношеннями передування:
.
Визначимо множину початкових робіт мережі. Перед початковими роботами немає ніяких інших, які б їм передували, і тому вони можуть бути лише в лівій частині відношення передування (надкреслені роботи). Аналогічно завершальними є роботи, після яких ніяких інших немає, тобто знаходяться лише в правій частині відношення передування (підкреслені роботи).
.
Будуємо мережу з початкової події, з
якої виходять всі початкові роботи, та
з кінцевої події, в яку входять всі
завершальні роботи. Для уникнення
неоднозначності вводимо фіктивну роботу
,
а для забезпечення виконання логіки
виконання робіт — фіктивну роботу
.
Події нумеруємо таким чином, щоб робота завжди виходила з події з меншим номером, і входила в подію з більшим номером. Оскільки таких способів існує декілька (і відповідні алгоритми нумерації) то обирається будь-який з них.