Информатика · объяснение и практика
Как вычислить резервы работ двумя проходами по зависимостям
Определить ранние и поздние сроки работ ациклического проекта, общую длительность и резервы при неограниченной параллельности ресурсов.

Вузовский уровень · Все вузовские темы
В теме Графы и маршруты · Учебная карта
Главная мысль
Критический путь определяется зависимостями и длительностями, а не просто самой длинной отдельной работой. Прямой проход даёт ранние сроки, обратный поздние; разность стартов показывает резерв работы в модели без ограничений исполнителей.
Метод и условия
Сначала убедитесь, что граф зависимостей не содержит цикла. Дуга i→j означает, что работа j может начаться лишь после окончания i. Длительность относится к вершине-работе. Топологический порядок позволяет вычислять сроки так, чтобы все предшественники уже были обработаны. У работы без предшественников ранний старт равен нулю; у остальных он равен максимуму ранних окончаний непосредственных предшественников.
Прибавьте длительность и получите раннее окончание. Общая минимальная длительность проекта равна максимуму этих окончаний, если независимые работы могут выполняться параллельно. Суммирование длительностей всех работ решало бы другую задачу — полностью последовательное исполнение. Для несвязных частей проекта общий срок определяется самой долгой частью, но короткие части тоже должны получить поздние сроки относительно общего завершения проекта.
Проверка и типичная ошибка
Обратный проход начинается с работ без последователей: их позднее окончание равно общему сроку проекта. Для остальных выберите минимум поздних стартов непосредственных последователей. Вычитая собственную длительность, получите поздний старт. Общий резерв равен разности позднего и раннего стартов. Нулевой резерв выделяет критические работы при данной структуре; положительный показывает допустимую задержку без переноса общей даты окончания в базовой модели.
Не заключайте, что критический путь обязательно единственный. Несколько ветвей могут иметь одну и ту же длительность и нулевые резервы. Также нулевой резерв не превращается автоматически в календарную дату: нужны единица длительности, начало проекта и правила рабочего календаря. Ограниченный состав исполнителей, перерывы, выходные и ресурсные конфликты здесь не учитываются. Добавление таких ограничений способно увеличить минимальный срок и изменить расписание. Для проверки пройдите каждую дугу: ранний старт последователя не должен быть меньше окончания предшественника, а позднее окончание предшественника не должно выходить за поздний старт последователя. В отчёте полезно показывать обе системы сроков вместе с резервом.
Пример
Работы имеют длительности (2,3,4,1). Первая предшествует второй и третьей, обе предшествуют четвёртой. Ранние старты равны (0,2,2,6), общий срок семь.
Поздние старты равны (0,3,2,6), резервы (0,1,0,0). Вторая работа может задержаться на единицу, а ветвь первой, третьей и четвёртой задаёт критическую длительность.
От чтения к действию
А теперь — вы
Частые вопросы
Здесь учитываются ограниченные исполнители?
Нет. Работы без зависимости могут выполняться параллельно; ограничения ресурсов потребовали бы отдельной задачи расписания.
Критический путь обязательно один?
Нет. Несколько ветвей одинаковой длительности могут давать несколько критических путей.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Матрица достижимости: как проверить сжатие ориентированного графа
Пошагово замыкаем матрицу смежности логическими переходами, выделяем взаимно достижимые группы и проверяем, почему путь между группами не всегда является прямой дугой конденсации.
Открыть темуКак подтвердить максимальный поток минимальным разрезом
Найти поток увеличивающими путями, сохранить обратные остаточные дуги и проверить оптимальность равенством ёмкости разреза.
Открыть темуСколько полных назначений разрешает совместимость: перманент без знаков перестановок
Посчитать все полные взаимно однозначные назначения по матрице совместимости и объяснить формулу Райзера через включения и исключения.
Открыть тему