📋 Метод критичного шляху (CPM/PERT)

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

Оберіть готовий проєкт зі спадного списку (Підручниковий DAG, Паралельні гілки або Майже нічия), щоб завантажити орієнтований ациклічний граф задач. Натисніть на будь-який вузол, щоб вибрати його, потім перетягніть повзунок тривалості, щоб змінити її довжину, і спостерігайте, як критичний шлях перераховується в реальному часі. Використовуйте кнопку «Крок», щоб анімувати прямий, а потім зворотний прохід по одній задачі за раз, або «Авто», щоб відтворити повну анімацію. Перемкніться в режим PERT, щоб побачити очікувані тривалості, і встановіть дедлайн, щоб отримати ймовірність завершення вчасно.

Резерв, також званий запасом часу, — це час, на який задачу можна затримати без затримки завершення проєкту. Він обчислюється як пізній старт мінус ранній старт (або еквівалентно — пізнє завершення мінус раннє завершення). Задачі з нульовим резервом є критичними; задачі з додатним резервом можна затримати або перерозподілити ресурси на критичні задачі — техніка, яка називається вирівнюванням ресурсів і є центральною для практичного управління проєктами.

PERT моделює тривалість кожної задачі як бета-розподіл, параметризований трьома оцінками часу: оптимістичною (o, найкращий випадок), найбільш імовірною (m, мода) та песимістичною (p, найгірший випадок). Очікувана тривалість дорівнює t_e = (o + 4m + p) / 6 — це зважене середнє, яке надає найбільш імовірній оцінці вагу вчетверо більшу за інші. Дисперсія для кожної задачі становить σ² = ((p − o) / 6)². Для всього критичного шляху дисперсії підсумовуються (задачі вважаються незалежними), даючи дисперсію шляху, яка використовується для обчислення Z-показника ймовірності дотримання дедлайну.

Коли відомі очікувана тривалість проєкту μ та сумарна дисперсія критичного шляху σ², ймовірність дотримання дедлайну обчислюється за допомогою нормального наближення: Z = (дедлайн − μ) / σ, де σ = √σ². Кумулятивний нормальний розподіл у точці Z дає P(T ≤ дедлайн). Симулятор використовує поліноміальне наближення Абрамовіца й Стегуна функції помилок (erf), щоб обчислити це без зовнішніх бібліотек. Дедлайн, що дорівнює очікуваній тривалості, дає приблизно 50% ймовірності; додавання одного σ підвищує її приблизно до 84%.

Так. Кілька шляхів у мережі можуть мати однакову максимальну тривалість, стаючи критичними одночасно. Це ілюструє готовий проєкт «Майже нічия» в симуляторі, де два паралельні маршрути мають майже однакову довжину — невелика зміна будь-якої задачі на будь-якому з маршрутів може змінити, який шлях є критичним. Наявність кількох критичних шляхів вважається вищим ризиком, оскільки будь-яка затримка на будь-якому з цих шляхів безпосередньо впливає на дату завершення проєкту.

CPM був розроблений у 1957 році Морганом Волкером (DuPont) і Джеймсом Келлі (Remington Rand) для планування капітальних ремонтів хімічних заводів. PERT був розроблений незалежно й майже одночасно (1957–1958) Управлінням спеціальних проєктів ВМС США спільно з Booz Allen Hamilton для програми балістичних ракет «Поларіс», яка вимагала координації тисяч підрядників і субпідрядників. Обидва методи вперше опубліковані в 1959 році, і їм широко приписують скорочення графіка програми «Поларіс» на два роки.

CPM і PERT потребують орієнтованого ациклічного графа (DAG) — орієнтованого графа без циклів, — оскільки циклічна залежність (A залежить від B, B залежить від A) зробила б планування логічно неможливим. Топологічне сортування, що використовується в прямому та зворотному проходах, є коректним лише для DAG. Реальні мережі проєктів завжди є DAG за визначенням: задача не може розпочатися раніше, ніж завершиться сама. Симулятор гарантує це, використовуючи лише готові ациклічні структури.

CPM вбудований в інструменти на кшталт Microsoft Project, Primavera P6 та відкритих альтернатив на кшталт ProjectLibre. У будівництві Асоціація розвитку інженерії витрат (AACE) вимагає планування за CPM для великих проєктів; у програмних проєктах CPM лежить в основі побудови діаграм Ганта в Jira та подібних платформах. Триточкова оцінка PERT також є основою для вдосконалень Planning Poker та прогнозування за еталонним класом, що використовуються в оцінюванні історій у agile.

CPM припускає детерміновані тривалості, що рідко відповідає дійсності на практиці. PERT частково вирішує цю проблему, але все одно припускає незалежність тривалостей задач (кореговані ризики ігноруються) і апроксимує розподіл тривалості шляху як нормальний, що недооцінює ймовірність затримки — так зване «зміщення злиття» або «зміщення PERT». Сучасним засобом усунення цієї проблеми є симуляція Монте-Карло (вибірка тисяч випадкових сценаріїв), яка використовується в інструментах планування з урахуванням ризику. Крім того, жоден із методів не враховує обмежень ресурсів; для цього потрібне планування проєктів з обмеженими ресурсами (RCPS), яке в загальному випадку є NP-складним.

Планування проєктів з обмеженими ресурсами (RCPS) додає до CPM обмеження ресурсів, роблячи задачу NP-складною. Управління критичним ланцюгом (CCPM), запропоноване Еліяху Голдраттом, переносить буфери з окремих задач у кінець ланцюга та в живильні ланцюги. Компроміс «час-вартість» (стиснення проєкту) розширює CPM, дозволяючи витрачати додаткові кошти на скорочення тривалості задач і відповідаючи на питання: який найдешевший спосіб скоротити проєкт на задану величину? Ці розширення є активними напрямами досліджень у дослідженні операцій та науці управління.