Информатика · объяснение и практика

Как вычислить резервы работ двумя проходами по зависимостям

Определить ранние и поздние сроки работ ациклического проекта, общую длительность и резервы при неограниченной параллельности ресурсов.

Синие фигурные скобки держат между собой оранжевый квадрат.

Вузовский уровень · Все вузовские темы

В теме Графы и маршруты · Учебная карта

Главная мысль

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

Метод и условия

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

Прибавьте длительность и получите раннее окончание. Общая минимальная длительность проекта равна максимуму этих окончаний, если независимые работы могут выполняться параллельно. Суммирование длительностей всех работ решало бы другую задачу — полностью последовательное исполнение. Для несвязных частей проекта общий срок определяется самой долгой частью, но короткие части тоже должны получить поздние сроки относительно общего завершения проекта.

Проверка и типичная ошибка

Обратный проход начинается с работ без последователей: их позднее окончание равно общему сроку проекта. Для остальных выберите минимум поздних стартов непосредственных последователей. Вычитая собственную длительность, получите поздний старт. Общий резерв равен разности позднего и раннего стартов. Нулевой резерв выделяет критические работы при данной структуре; положительный показывает допустимую задержку без переноса общей даты окончания в базовой модели.

Не заключайте, что критический путь обязательно единственный. Несколько ветвей могут иметь одну и ту же длительность и нулевые резервы. Также нулевой резерв не превращается автоматически в календарную дату: нужны единица длительности, начало проекта и правила рабочего календаря. Ограниченный состав исполнителей, перерывы, выходные и ресурсные конфликты здесь не учитываются. Добавление таких ограничений способно увеличить минимальный срок и изменить расписание. Для проверки пройдите каждую дугу: ранний старт последователя не должен быть меньше окончания предшественника, а позднее окончание предшественника не должно выходить за поздний старт последователя. В отчёте полезно показывать обе системы сроков вместе с резервом.

Пример

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

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

От чтения к действию

А теперь — вы

Две параллельные ветви имеют одинаковую максимальную длительность. Что возможно?

Частые вопросы

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

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

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

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться