Решение: Параллельное выполнение процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены через разделитель «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, указано значение 0.
Определите максимальную продолжительность отрезка времени в миллисекундах, в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно и время окончания работы всех процессов минимально.
Для выполнения задания используйте данные из прилагаемого файла.
Решение по шагам
4 шагаПо таблице из файла строится граф зависимостей процессов. Для каждого процесса определяется самое раннее время начала: оно равно максимальному времени окончания всех его непосредственных предшественников.
Процессы, не связанные отношением зависимости и доступные одновременно, запускаются параллельно. Это обеспечивает минимальное время окончания всех процессов.
Для каждого процесса отмечается интервал его выполнения. Затем среди всех моментов и границ интервалов определяется отрезок, на котором одновременно выполняется максимальное количество процессов.
По данным прилагаемого файла продолжительность такого отрезка составляет $9$ миллисекунд.
Где здесь ошибаются
Запускают процесс до завершения всех процессов, от которых он зависит.
Суммируют времена всех процессов вместо параллельного выполнения независимых процессов.
Ищут самый длинный интервал работы одного процесса, а не отрезок с максимальным числом одновременно выполняющихся процессов.