Параллельные процессы: резерв времени процесса
Условие
В таблице приведены сведения о процессах, которые могут выполняться параллельно (данные даны прямо в условии, в мини-версии вместо файла). Для каждого процесса B указаны его идентификатор (ID), время выполнения в миллисекундах и идентификаторы процессов A, от которых он зависит. Процесс B может начаться только после завершения всех процессов A, от которых он зависит; если процесс ни от чего не зависит, в последнем столбце записан 0. Независимые процессы могут выполняться одновременно, количество одновременно выполняемых процессов не ограничено. Временем на переключение между процессами можно пренебречь.
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(-ов) A |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 2 | 0 |
| 3 | 7 | 1 |
| 4 | 3 | 2 |
| 5 | 2 | 4 |
| 6 | 5 | 1; 4 |
| 7 | 3 | 3; 5 |
| 8 | 4 | 6 |
| 9 | 2 | 7; 8 |
Определите, на какое наибольшее количество миллисекунд можно задержать начало процесса 5 (относительно самого раннего возможного момента его начала), чтобы минимальное время завершения всех процессов не увеличилось. Остальные процессы начинаются в самый ранний возможный момент.