Решение: Минимальное время процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. Информация о процессах представлена в таблице: указаны идентификатор процесса, время его выполнения в миллисекундах и идентификаторы процессов, от которых он зависит. Если процесс независим, указано значение 0. Определите минимальное время, через которое завершится выполнение всей совокупности процессов, если все независимые друг от друга процессы могут выполняться параллельно. Используйте данные из прилагаемого файла.
Решение по шагам
4 шагаПредставим процессы в виде ориентированного графа: ребро направлено от процесса к процессу, который от него зависит.
Для независимого процесса время завершения равно его времени выполнения: $F_i = t_i$.
Для процесса с зависимостями сначала находим максимальное время завершения всех процессов-предшественников, так как они могут выполняться параллельно, а затем прибавляем время выполнения самого процесса: $F_i = \max(F_j) + t_i$.
Последовательно обработав данные из прилагаемого файла, находим время завершения всех процессов. Максимальное из полученных значений равно $223$.
Где здесь ошибаются
Складывают времена всех процессов, хотя независимые процессы могут выполняться параллельно.
Берут минимум времени завершения зависимых процессов вместо максимума.
Не учитывают время выполнения самого процесса после завершения его зависимостей.