Многопроцессорные системы

(М. Попков) На предприятии «АвтоПро» производится сборка автомобилей, включающая множество этапов, которые могут выполняться параллельно или последовательно. Приостановка выполнения этапа не допускается. Будем говорить, что этап B зависит от этапа A, если для выполнения этапа B необходимы результаты выполнения этапа A. В этом случае этапы A и B могут выполняться только последовательно.

Информация об этапах сборки представлена в электронном виде в виде таблицы. В первом столбце таблицы указан идентификатор этапа (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID этапов, от которых зависит данный этап. Если этап независимый, то в таблице указано значение 0.

Типовой пример организации данных в файле

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества этапов, при условии, что все независимые друг от друга этапы могут выполняться параллельно, а время завершения каждого этапа минимально.