Шешімі: Минимальное время процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы: в первом столбце указан идентификатор процесса, во втором — время его выполнения в миллисекундах, в третьем — через разделитель «;» перечислены идентификаторы процессов, от которых зависит данный процесс. Если процесс независимый, указано значение 0.
Определите минимальное время, за которое завершатся 16 процессов. Каждый процесс начинается в самое раннее допустимое время. Время отсчитывается непрерывно с первой миллисекунды. Данные для выполнения задания находятся в прилагаемом файле.
Шешім по шагам
4 қадамПредставим процессы в виде ориентированного графа: ребро направлено от процесса-зависимости к процессу, который использует его результат.
Для каждого процесса вычислим раннее время завершения. Для независимого процесса оно равно его длительности, а для зависимого — сумме его длительности и максимального времени завершения всех зависимостей.
$$T_i = t_i + \max_{j \in D_i} T_j$$Обработав таблицу процессов в порядке, при котором зависимости рассматриваются раньше зависимых процессов, получаем максимальное время завершения всех 16 процессов.
Максимальное время завершения равно 19 миллисекундам.
Где здесь ошибаются
Складывают длительности всех процессов, не учитывая возможность параллельного выполнения.
Учитывают только одну зависимость, хотя процесс может зависеть от нескольких процессов.
Берут сумму времени по любой цепочке, а не длину критического пути.