Решение: Минимальное время процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы: в первой строке таблицы указан идентификатор процесса ($ID$), во второй строке — время его выполнения в миллисекундах, в третьей строке перечислены через «;» $ID$ процессов, от которых зависит данный процесс. Если процесс является независимым, указано значение 0.
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, если все независимые друг от друга процессы могут выполняться параллельно. Для решения используйте данные из прилагаемого файла.
Решение по шагам
4 шагаПараллельное выполнение означает, что для процесса с несколькими предшественниками нужно дождаться самого позднего из них. Поэтому для каждого процесса вычисляется время его завершения.
Для независимого процесса время завершения равно его времени выполнения. Для зависимого процесса время завершения вычисляется как максимум времён завершения всех указанных процессов-предшественников плюс время выполнения текущего процесса.
$$T_B = \max(T_{A_1}, T_{A_2}, \ldots) + t_B$$После обработки всех записей файла выбираем максимальное время завершения процессов. Это время критического пути всей системы.
По данным прилагаемого файла максимальное время завершения равно 148 миллисекундам.
Где здесь ошибаются
Складывают времена всех процессов, хотя независимые процессы могут выполняться параллельно.
Берут сумму времён всех предшественников вместо максимума.
Не учитывают время выполнения последнего процесса в цепочке зависимостей.