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

Решение.
Используем данные приложенного файла 1_22.ods: в нём 17 процессов. Таблица из четырёх строк в условии — только пример структуры, её числа не подставляем вместо данных файла.
Обозначим длительность процесса i через d(i), самое раннее время начала — S(i), время окончания — F(i). Отсчёт времени ведём от нуля. Независимый процесс можно запустить сразу: S(i) = 0, F(i) = d(i).
Если есть зависимости, процесс ждёт окончания всех предшественников. Поэтому S(i) = max(F(j)) по всем указанным предшественникам j, а F(i) = S(i) + d(i). Берём максимум, а не сумму: предшественники могут выполняться параллельно.
Вычисляем времена в порядке зависимостей, а не обязательно по номеру строки. Например, процесс 3 зависит от 10, а процесс 11 — от 15, хотя эти строки находятся ниже в файле.
Для процесса 5: S(5) = F(2) = 20, F(5) = 20 + 25 = 45.
Для процесса 8: S(8) = max(F(1), F(5)) = max(24, 45) = 45, F(8) = 45 + 22 = 67.
Для процесса 6: S(6) = max(F(4), F(5), F(7), F(8)) = max(22, 45, 63, 67) = 67, F(6) = 67 + 23 = 90.
Полный расчёт по исходному файлу:

Последним заканчивается процесс 17. Его начало: S(17) = max(F(14), F(16)) = max(66, 196) = 196. Окончание: F(17) = 196 + 22 = 218 мс. Все остальные процессы завершаются не позже этого момента.
Докажем минимальность. В файле есть цепочка непосредственных зависимостей 2 → 5 → 7 → 10 → 3 → 9 → 12 → 13 → 16 → 17. Эти процессы обязаны выполняться последовательно. Сумма их длительностей равна 20 + 25 + 18 + 19 + 19 + 21 + 24 + 25 + 25 + 22 = 218 мс. Ни одно допустимое расписание не может закончиться раньше.
Проверка: таблица задаёт допустимое расписание, в котором каждый процесс начинается после всех своих предшественников, и достигает нижней границы 218 мс. Значит, найдено именно минимальное время всей совокупности.
Ответ: 218.