Решение: Максимальная параллельная загрузка
В прилагаемом файле содержится таблица с информацией о совокупности $N$ вычислительных процессов. Для каждого процесса указаны его идентификатор, время выполнения в миллисекундах и идентификаторы процессов, от которых он зависит. Если процесс независимый, указано значение 0. Приостановка выполнения процессов не допускается.
Определите максимальную продолжительность отрезка времени в миллисекундах, в течение которого возможно одновременное выполнение максимального количества процессов, если все независимые друг от друга процессы могут выполняться параллельно.
Решение по шагам
4 шагаПо данным файла для каждого процесса определяем наиболее раннее время начала: оно равно нулю для независимых процессов, а для зависимого процесса — максимальному времени окончания его предшественников.
$$t_{\text{нач}}(B)=\max\limits_{A\to B}t_{\text{ок}}(A)$$Для каждого процесса отмечаем интервал его выполнения от времени начала до времени окончания. Процессы, не связанные зависимостями в данный момент, выполняются параллельно.
Подсчитываем количество одновременно выполняющихся процессов на каждом промежутке между моментами начала и окончания процессов, выбираем максимальное количество и определяем все интервалы, на которых оно достигается.
Для данных из прилагаемого файла суммарная продолжительность такого интервала составляет $7$ миллисекунд.
Где здесь ошибаются
Складывают времена выполнения всех процессов вместо анализа их параллельного выполнения.
Начинают процесс одновременно с его предшественниками, не дожидаясь получения результатов.
Учитывают только один из нескольких процессов-предшественников.