Метод критичного шляху

Проект – це графік, а не список

Метод критичного шляху, який незалежно розробили компанії DuPont та Remington Rand наприкінці 1950-х років, моделює проект як направлений циклічний граф (НЦГ): кожне завдання є вузлом з тривалістю, а ребро від завдання A до завдання B означає, що завдання B не може розпочатися, поки завдання A не завершиться. Графік проекту – це не послідовність, а мережа цих залежностей: деякі завдання можуть виконуватися паралельно, інші повинні чекати, і кінцева дата встановлюється найдовшим ланцюгом залежних завдань, що виконуються від початку до кінця.

Попередня передача: коли може розпочатися кожне завдання?

Проходячи через DAG (графі залежностей) у топологічному порядку, найраніший початок (NP) кожного завдання – це пізній час найпізнішого завершення його попередників, а найраніший кінець (НК) – це просто NP плюс тривалість цього завдання. Ця попередня передача поширює через весь мережу максимально можливий графік і дозволяє визначити найранішу дату, коли проект може закінчитися – НК останнього завдання.

жива демонстрація · пов'язана симуляція● LIVE

Повернення назад: наскільки пізно може розпочатися кожне завдання?

Тепер рухайтеся назад від фіксованої дати завершення проєкту. Найпізніший кінець (НК) кожного завдання – це найраніше з часових меж завершення наступних за ним завдань, а найпізніший початок (НП) – НК мінус тривалість цього завдання. Цей етап відповідає на інше питання: на скільки пізно може відсунутися початок кожного завдання, не впливаючи на загальний дедлайн?

forward pass (topological order):
  ES(task) = max( EF(pred) for pred in predecessors ), 0 if none
  EF(task) = ES(task) + duration(task)

backward pass (reverse topological order):
  LF(task) = min( LS(succ) for succ in successors ), projectFinish if none
  LS(task) = LF(task) − duration(task)

slack(task) = LS(task) − ES(task)     // = LF(task) − EF(task)
critical path = every task with slack(task) == 0

Розтяг, і шлях, що не рухається

Віднімання ES з LS дає величину розтягу (також відому як float) для кожної задачі: скільки днів її можна відкласти, не впливаючи на дату завершення проєкту. Задачі з позитивним розтягом мають запас часу – задача з розтягом у два дні може розпочатися на два дні пізніше, і проєкт все одно завершиться вчасно. Задачі з нульовим розтягом не мають жодного: будь-яке запізнення там призведе до запізнення всього проєкту. Пов'язані разом, задачі з нульовим розтягом утворюють критичний шлях – за конструкцією, це єдина найдовша траса через граф залежностей, і тому найкоротший можливий час виконання проєкту. Проєкт може мати більше одного критичного шляху, якщо дві або більше ланцюжків змагаються за найбільшу тривалість.

PERT: перетворення однієї тривалості на ймовірність

CPM припускає, що кожне завдання має єдину відому тривалість, що рідко відповідає дійсності. Метод оцінки та аналізу перспектив (PERT), розроблений для Військово-морського флоту США під час програми Polaris ракети «Полярник» приблизно в той же час, замість цього просить надати три оцінки на завдання – оптимістичну (o), найбільш вірогідну (m) та песимістичну (p), і об’єднує їх за допомогою апріорного розподілу Бета у очікувану тривалість та дисперсію:

очікувана тривалість: te = ((o + 4m + p) / 6 дисперсія: v = (((p − o) / 6)² варіація проекту ≈ сума дисперсій завдань на критичному шляху P(завершення ≤ дедлайн) ≈ Φ( (дедлайн − Σte) / √(Σv) ) // нормальне наближення Підсумовуючи очікувані тривалості та дисперсії вздовж критичного шляху, а потім застосовуючи нормальне наближення, що випливає з теореми Гауса про центральний ліміт, перетворюється єдиний детермінований графік у оцінку ймовірності того, що весь проект завершиться до цільової дати - справді корисна відповідь на питання «наскільки впевнено ми в цій даті» замість однієї оптимістичної цифри.

expected duration:  te = (o + 4m + p) / 6
variance:           v  = ((p − o) / 6)²

project variance ≈ sum of variances of tasks on the critical path
P(finish ≤ deadline) ≈ Φ( (deadline − Σte) / √(Σv) )   // normal approximation

Frequently asked questions

Що таке критичний шлях насправді?

Це найдовший ланцюг залежних завдань від початку проєкту до його завершення, виміряний у загальній тривалості, а не в кількості завдань. Кожне завдання на ньому має нульовий запас часу – затримка будь-якого з них на один день затримує весь проєкт на ту ж саму величину, тому менеджери з проєктів уважать критичний шлях більше за будь-який інший показник.

Чи може проєкт мати більше одного критичного шляху?

Так. Якщо дві або більше ланцюгів завдань додають разом точно однакову найдовшу тривалість, вони всі є критичними одночасно, і затримка будь-якого завдання в будь-якому з них затримує проєкт. Це часто зустрічається у тісно оптимізованих графіках та є крихким – невеликий внесок, що прискорює один шлях, може просто передати статус критичності іншому.

Що PERT додає, чого CPM само по собі не має?

CPM передбачає, що кожне завдання має одну фіксовану тривалість. PERT замість цього запитує оптимістичну, найбільш ймовірну та песимістичну оцінки для кожного завдання, об'єднує їх у очікувану тривалість і дисперсію, використовуючи біномірний розподіл, і підсумовує їх вздовж критичного шляху, щоб оцінити ймовірність того, що весь проєкт завершиться до певної дати – перетворюючи графік з однією цифрою на оцінку ризиків.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Critical Path Method і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.

▶ Відкрити симуляцію Critical Path Method

Метод критичного шляху: Знаходження ланцюга, який не може прослизнути