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

Решение.
Открываем приложенный файл 1_22.ods. В нём 14 процессов с номерами 101–114. Иллюстративную таблицу из условия не используем вместо файла: например, длительность 104 в файле равна 5 мс.
Нужно получить самый длинный непрерывный интервал, когда одновременно работают пять процессов. Условие допускает откладывать начало процесса; уже запущенный процесс прерывать нельзя. Поэтому одно расписание с самыми ранними стартами ещё не доказывает максимум.
Разделим процессы на три группы, между которыми нет зависимостей.
Первая группа: 101, 102, 103, 104, 105, 106, 107, 108. Сначала могут идти параллельно 101 и 102; затем выполняется 103. После него параллельны ветвь 105 и цепочка 104 → 106. Процесс 107 ждёт обе ветви, за ним следует 108. Одновременно в этой группе работают не больше двух процессов.
Вторая группа: 109, 111, 114, 113. После 109 параллельно выполняются 111 и 114, а 113 ждёт их обоих. Здесь тоже не больше двух процессов одновременно.
Третья группа: цепочка 110 → 112. Одновременно работает не больше одного процесса.
Таким образом, пять одновременно — это обязательно два из первой группы, два из второй и один из третьей.
Докажем верхнюю границу. В первой группе два процесса могут работать только в двух разделённых этапах. Пересечение 101 и 102 длится не более min(4, 3) = 3 мс. Второй этап — процесс 105 вместе с 104, а затем с 106. Он ограничен длительностью 105, равной 7 мс, и суммарной длительностью 104 и 106, равной 5 + 3 = 8 мс. Поэтому этот этап длится не больше min(7, 8) = 7 мс.
Между этими этапами обязательно выполняется 103, когда первая группа даёт только один работающий процесс. Объединить этапы в непрерывный интервал работы пяти процессов нельзя. Следовательно, искомый интервал не длиннее 7 мс.
Построим расписание, достигающее границы. Начало и окончание указаны в миллисекундах от нуля; каждый процесс занимает один непрерывный промежуток:

Процесс 103 намеренно начинается в момент 7, хотя его предшественники завершились раньше. Процесс 110 также отложен до момента 8. Эти задержки разрешены условием и позволяют совместить нужные этапы.
Рассмотрим интервал от момента 8 до момента 15:

В момент 13 закончившийся 104 сменяется процессом 106, а в момент 14 закончившийся 110 — процессом 112. Разрывов нет; ни один процесс не приостанавливается. Пять процессов работают непрерывно 15 − 8 = 7 мс.
Проверка зависимостей: 104 и 105 стартуют после окончания 103; 106 — после 104; 107 — после 105 и 106; 111 и 114 — после 109; 113 — после 111 и 114; 112 — после 110. Все длительности в таблице равны исходным. Получено допустимое расписание с интервалом 7 мс, и выше доказано, что больше невозможно.
Ответ: 7.