Задание EGEINFABAA67: Параллельные вычисления

Решение.

В приложенной таблице 25 процессов. Первый столбец содержит их идентификаторы, второй — длительности в миллисекундах, третий — идентификаторы всех необходимых предшественников. Ноль в третьем столбце означает отсутствие предшественников. Типовой пример из условия не заменяет данные файла.

Начальный момент обозначим 0. Пусть d(B) — длительность процесса B, S(B) — время его начала, F(B) — время окончания. Процесс занимает промежуток от S(B) включительно до F(B) не включительно. Его результат доступен уже в момент F(B); следующий процесс может начаться в этот же момент.

Для самого раннего допустимого запуска используем правила:
S(B) = 0, если предшественников нет;
S(B) = max(F(A)), где максимум берётся по всем предшественникам A;
F(B) = S(B) + d(B).
Длительности разных предшественников не складываем: они могут работать параллельно. Но ждать требуется завершения каждого, поэтому выбираем самое позднее окончание. Строки вычисляем после их предшественников, даже если в файле они расположены в другом порядке.

Эти времена достижимы одновременным запуском всех готовых процессов. Раньше запустить очередной процесс нельзя: хотя бы один необходимый результат ещё отсутствует. Последовательно применяя это рассуждение по зависимостям, получаем минимальные времена окончания каждого процесса.

Проверка зависимостей и длительностей. Полный расчёт самого раннего расписания, все времена в мс:

Нужно найти первый момент, к которому завершилось не менее 17 процессов. Упорядочим все значения F по возрастанию, сохраняя одинаковые окончания разных процессов:
2; 3; 4; 5; 6; 6; 6; 8; 8; 9; 9; 9; 11; 11; 12; 12; 12; 13; 15; 15; 16; 16; 17; 18; 21.

На позиции 17 стоит 12. Строго раньше этого момента завершается 14 процессов, а к этому моменту включительно — 17. Поэтому раньше нужного количества ещё нет, а в момент 12 мс оно уже достигнуто. Одновременные окончания считаем по отдельности.

Ответ: 12.