Что проверяет задание
Дана совокупность процессов: у каждого есть длительность и зависимости «нельзя начать, пока не завершатся указанные процессы». Нужно найти время окончания, длительность простоя, критический путь или наибольшее число одновременно идущих процессов.
Определения
Процесс (работа), отрезок времени фиксированной длительности. Он либо ещё не начат, либо выполняется непрерывно, либо уже завершён. Прерывать процесс обычно нельзя.
Зависимость, отношение предшествования: процесс B имеет предшественника A, если B нельзя начать раньше окончания A.
Граф предшествования, ориентированный граф: ребро A → B означает «A предшествует B». Циклов быть не должно, иначе расписание невозможно.
Раннее время начала процесса, самый ранний момент, когда завершены все его предшественники.
Раннее время окончания, раннее начало плюс длительность.
Позднее время начала, самый поздний момент старта, который ещё не сдвигает общее окончание проекта.
Резерв времени, разница между поздним и ранним началом. Нулевой резерв означает, что процесс лежит на критическом пути.
Критический путь, самая длинная по суммарной длительности цепочка зависимых процессов от старта до финиша. Её длина равна минимально возможному времени завершения всей совокупности.
Параллельность, несколько процессов могут идти одновременно, если ни один не является предшественником другого и хватает «исполнителей», если они ограничены. В типовом задании исполнителей обычно достаточно, ограничение только в зависимостях.
Простой, промежуток, когда процесс мог бы идти, но ждёт предшественников, либо когда система ждёт между событиями.
Связь с таблицей
Таблица процессов, тот же граф: столбцы «время» и «зависимости». Если зависимость указана списком номеров, каждый номер, предшественник.
Время в таблице, длительность, а не момент старта. Момент старта вычисляют.
Общий алгоритм решения
- Построить граф предшествования и проверить, что у каждого процесса известна длительность.
- Вычислить ранние начала и окончания в топологическом порядке: сначала процессы без предшественников.
- Время окончания всей совокупности, максимум ранних окончаний.
- Если нужен критический путь, пройти назад по процессам, на которых достигается этот максимум.
- Если нужно максимальное число одновременных процессов, рассматривать ось времени и для каждого момента считать, сколько процессов имеют ранний интервал, покрывающий этот момент при старте как можно раньше. Уточнить по условию, обязаны ли процессы стартовать рано.
- Если спрашивают задержку одного процесса, посмотреть, насколько можно сдвинуть его старт, не увеличивая общее окончание.