Критический путь: ранние и поздние сроки работ

Рассчитать минимальную длительность проекта с зависимостями, резервы работ и все критические вершины в ациклической сети.

Ваш пример

Дроби вводите как 1/3, десятичные числа — 0.5 или 0,5. Таблицы: числа через пробел, строки с новой строки. Формулы не выполняются.

Разбор примера

Длительность проекта = 7

Проверяемый расчёт
РаботаРанний стартРанний финишПоздний стартРезерв
10200
22531
32620
46760
  1. Зависимости проверены на цикл.
  2. Ранние сроки получены по максимуму предшественников, поздние — по минимуму последователей.
  3. Критические работы: 1, 3, 4.

Метод и условия расчёта

Прямой проход задаёт ранний старт как максимум окончаний предшественников.

Обратный проход задаёт поздний старт; нулевой резерв означает критическую работу при заданной модели.

Теория к методу

Критический путь определяется зависимостями и длительностями, а не просто самой длинной отдельной работой. Прямой проход даёт ранние сроки, обратный поздние; разность стартов показывает резерв работы в модели без ограничений исполнителей.

Сначала убедитесь, что граф зависимостей не содержит цикла. Дуга i→j означает, что работа j может начаться лишь после окончания i. Длительность относится к вершине-работе. Топологический порядок позволяет вычислять сроки так, чтобы все предшественники уже были обработаны. У работы без предшественников ранний старт равен нулю; у остальных он равен максимуму ранних окончаний непосредственных предшественников.

Пример: Работы имеют длительности (2,3,4,1). Первая предшествует второй и третьей, обе предшествуют четвёртой. Ранние старты равны (0,2,2,6), общий срок семь.

Поздние старты равны (0,3,2,6), резервы (0,1,0,0). Вторая работа может задержаться на единицу, а ветвь первой, третьей и четвёртой задаёт критическую длительность.

Вопросы по теме

Здесь учитываются ограниченные исполнители?

Нет. Работы без зависимости могут выполняться параллельно; ограничения ресурсов потребовали бы отдельной задачи расписания.

Критический путь обязательно один?

Нет. Несколько ветвей одинаковой длительности могут давать несколько критических путей.

Графы и маршруты: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.