Решение: Минимальное время процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы могут выполняться только последовательно. В первой строке таблицы указан идентификатор процесса, во второй — время его выполнения в миллисекундах, в третьей — через разделитель «;» идентификаторы процессов, от которых зависит данный процесс. Если процесс независим, указано значение 0. Определите минимальное время, через которое завершится выполнение всей совокупности процессов, если все независимые друг от друга процессы могут выполняться параллельно. Используйте данные из прилагаемого файла.
Решение по шагам
3 шагаПроцессы, не зависящие друг от друга, могут выполняться одновременно, поэтому складывать времена всех процессов нельзя.
Для каждого процесса вычисляется самое раннее время его завершения: если зависимостей нет, оно равно времени выполнения процесса; иначе к максимальному времени завершения зависимых процессов прибавляется время выполнения текущего процесса.
$$T(B)=\max\limits_{A\in D(B)}T(A)+t(B)$$После обработки всех записей файла выбирается максимальное время завершения. Для данных из прилагаемого файла оно равно 175 миллисекундам.
Где здесь ошибаются
Складывают времена всех процессов, хотя независимые процессы выполняются параллельно.
Берут минимальное, а не максимальное время среди цепочек зависимостей.
Не учитывают, что процесс может начаться только после завершения всех процессов, от которых он зависит.