Решение: Параллельное выполнение процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$; в этом случае процессы $A$ и $B$ выполняются последовательно.
Информация о процессах представлена в файле в виде таблицы: идентификатор процесса, время его выполнения в миллисекундах и список идентификаторов процессов, от которых он зависит. Для независимого процесса указано значение 0.
Определите минимальное время в миллисекундах, за которое завершатся 17 процессов. Каждый процесс начинается в самое раннее допустимое время. Минимальное время отсчитывается непрерывно с первой миллисекунды.
Решение по шагам
3 шагаПредставим процессы в виде ориентированного графа: дуга направлена от процесса-предшественника к зависящему от него процессу.
Для независимого процесса время завершения равно его длительности. Для остальных процессов время начала определяется максимальным временем завершения всех непосредственных предшественников.
Последовательно вычисляя времена завершения процессов по данным из приложенного файла, получаем время завершения 17 процессов, равное 12 миллисекундам.
$$T_{17}=12$$Где здесь ошибаются
Складывают времена всех процессов, хотя независимые процессы могут выполняться параллельно.
Учитывают только одного предшественника вместо самого поздно завершающегося.
Начинают отсчёт времени с нулевой миллисекунды, хотя по условию отсчёт ведётся с первой миллисекунды.