Решение: Параллельное выполнение процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$; в этом случае процессы $A$ и $B$ выполняются только последовательно.
В файле представлена таблица: идентификатор процесса, время его выполнения в миллисекундах и идентификаторы процессов, от которых он зависит. Независимые процессы могут выполняться параллельно. Определите максимальную продолжительность отрезка времени, в течение которого возможно одновременное выполнение максимального количества процессов, если время окончания работы всех процессов минимально. Используйте данные из прилагаемого файла.
Решение по шагам
4 шагаПо таблице из файла строим граф зависимостей процессов. Каждый процесс можно начать сразу после завершения всех процессов, от которых он зависит.
Рассчитываем расписание с минимальным временем окончания всех процессов: время начала процесса определяется максимальным временем окончания его предшественников.
Разбиваем полученное расписание на интервалы между моментами запуска и завершения процессов и для каждого интервала считаем число одновременно выполняющихся процессов.
Выбираем максимальное количество одновременно работающих процессов и определяем суммарную продолжительность всех соответствующих участков времени. Для данных файла она составляет $13$ мс.
Где здесь ошибаются
Запускают процесс до завершения всех процессов, от которых он зависит.
Считают только один самый длинный интервал, не объединяя участки с одинаковым максимальным числом одновременно выполняющихся процессов.
Не учитывают, что приостановка выполнения процесса запрещена.