Задание 22

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы  — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Типовой пример организации данных в файле:

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Выполните задания, используя данные из файла 22_1.xlsx

Решение:
Чтобы понять, как решать задачу, проиллюстрируем взаимосвязь процессов на примере диаграммы Ганта. Это не способ решения, а только иллюстрация того, как выполняются процессы.
Откроем файл 22_1.xlsx.

Мы видим, что процессы 1, 2, 9 и 10 из столбца В ни от чего не зависят и могут выполняться одновременно. Отобразим это на диаграмме:

Синим цветом выделена ось Х, цифрами обозначена длительность процесса в мс. Зеленым выделены номера процессов.
1-ый процесс ни от чего не зависит, можем запустить и длится он 4 мс.
2-ой процесс тоже ни от чего не зависит, может идти параллельно с 1-м и длится 3 мс.
3-ий процесс зависит только от 1-го и 2-го, длится 1 мс.
4-ый процесс зависит от 3-го и длится 7 мс.
5-ый процесс зависит от 3-го, может идти параллельно 4-му и длится 6 мс.
6-ый процесс зависит от 5-го и длится 3 мс.
7-ый процесс зависит от 4-го и 6-го и длится 1 мс.
8-ый процесс зависит от 7-го и длится 2 мс.
9-ый процесс независимый и длится 7 мс. Запускается сразу.
10-ый процесс независимый и длится 8 мс. Запускается сразу.
11-ый процесс зависит от 9-го и длится 6 мс.
12-ый процесс зависит от 10-го и длится 6 мс.
Нам нужно отобразить время, когда закончились все процессы.
Видим, что 17 мс прошло и все процессы закончились.
Диаграмма зависимости времени процессов друг от друга называется диаграммой Ганта. На ней удобно отслеживать время и очередность процессов.
Однако в данной задаче это не лучший способ решения.
Как решить такую задачу по-другому?
Нарисуем схему запуска всех процессов. Цифра – номер процесса, а индекс общее количество затраченного времени от момента запуска всей системы. Считаем устно, все расчеты зарисовываем и записываем внимательно:

Ответ: 17

Пример 2.
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы  — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Типовой пример организации данных в файле:

Решение:
В данной задаче есть процесс, который зависит от трёх источников.
Сделаем иллюстрацию с помощью диаграммы Ганта.

Самая поздняя секунда, когда закончатся все процессы – 24.
Нарисуем схему:

Ответ: 24

Пример 3
В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов – поставщиков данных. Независимые процессы (не имеющие поставщиков данных) можно запускать в любой момент времени. Если процесс B (зависимый процесс) получает данные от процесса A (поставщика данных), то процесс B может начать выполнение не раньше чем через 3 мс после завершения процесса A. Любые процессы, готовые к выполнению, можно запускать параллельно, при этом количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице 22_3.xlsx представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов. Определите, за какое минимальное время можно выполнить все процессы.
В ответе запишите целое число – минимальное время в мс.

Решение:
Задача аналогичная, но есть нюанс. Здесь любой следующий процесс запускается не мгновенно, а с зазором в 3 мс.
Чтобы не запутаться и не рисовать руками, можно все тоже самое сделать в Excel.
Скопируем данные в Excel. Столбец D будет отображать общее время окончание процесса.