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

Решение.
Открываем исходный файл ODS. Полная таблица содержит 25 процессов; иллюстративная таблица в тексте задания показывает только формат данных. Для ответа используем именно файл. Все времена ниже указаны в миллисекундах.
Обозначим длительность процесса i через d(i), самое раннее время начала — S(i), завершения — F(i). Время отсчитываем от нуля: независимые процессы начинаются в момент 0 и работают уже на первой миллисекунде.
Процесс может начаться, когда завершатся все его непосредственные предшественники. Поэтому S(i) равно максимуму их времён F. Для независимого процесса S(i) = 0. После начала процесс выполняется непрерывно, так что F(i) = S(i) + d(i).
Сначала рассчитываем независимые процессы, затем те, у которых известны времена завершения всех предшественников. Номер процесса не задаёт порядок вычисления. Параллельные ветви не складываем между собой: в формуле начала нужен максимум.
В таблице ниже процессы расположены в порядке расчёта. Знак «—» означает отсутствие зависимостей. В столбцах S и F показаны численные подстановки.

Проверка расписания: каждая длительность равна F(i) − S(i), а начало не меньше завершения любого предшественника. Все готовые процессы можно запускать одновременно: ограничения на число исполнителей в условии нет.
Докажем, что получены самые ранние времена. Независимый процесс нельзя начать раньше нуля. Если самые ранние завершения его предшественников уже найдены, зависимый процесс не может начаться раньше их максимума. Запуск в этот момент допустим. Продолжая рассуждение по порядку зависимостей, получаем самые ранние начала и завершения всех процессов.
Расположим завершения по возрастанию. Каждая пара имеет вид «время; ID процесса»:
(6; 3); (6; 8); (6; 13); (7; 17); (7; 23); (8; 21); (9; 20); (12; 12); (13; 14); (13; 19); (15; 2); (15; 25); (18; 4); (18; 7); (19; 16); (19; 22); (20; 9); (21; 11); (23; 1); (24; 10); (25; 24); (26; 15); (28; 5); (29; 6); (29; 18).
Нужно дождаться завершения 16 процессов. Время 16-го завершения в этом списке — 19.
Строго раньше момента 19 завершились 14 процессов: 2, 3, 4, 7, 8, 12, 13, 14, 17, 19, 20, 21, 23, 25.
Ровно в момент 19 завершаются ещё 2: 16, 22. Итого к этому моменту завершено 16 процессов.
До момента 19 завершившихся меньше 16, а к нему их уже не меньше 16. Следовательно, самое раннее требуемое время равно 19 мс. Одинаковые времена завершения учитываются одновременно; каждый процесс считается один раз.
Ответ: 19.