Задание 22

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

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Скачать файл

Теория

Задание состоит в анализе общего времени выполнения последовательности процессов. Информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно содержится в файле. Эту информацию можно изобразить графически в виде набора параллельных и последовательных отрезков или воспользоваться заливкой в MSExcel. Пользоваться специальными программами для построения диаграммы Ганта (Microsoft Project и др.)  не обязательно, можно построить ее в Excel.

Решение

Открываем файл электронной таблицы и выделяем 30-40 столбцов, начиная со столбца D и задаем их ширину через контекстное меню в 2 символа. Далее заполняем ячейки первой строки числами 1, 2, 3 и т.д. начиная с D1.

Правее каждого процесса, учитывая его зависимость или независимость выделяем и заполняем числами 1 (Ctrl+Enter) необходимое количество ячеек (данные столбца B). Затем в каждом столбце, начиная с D в строке 15 подсчитываем сумму единиц со 2 строки по 13 строку, применяем условное форматирование для диапазона D2:AM12 (Правила выделения ячеек - Равно ставим 1) и для диапазона D15:AM15 (Равно 4). Получится подобно приведенному ниже рисунку

Максимальное количество параллельных процессов равно 4, а максимальный отрезок, когда выполняются 4 параллельных процессов, равен 4. Но будьте внимательны - процессы 1, 2 и 9, 10 независимы. Это значит что их можно запускать когда угодно, независимо друг от друга! Ограничений на общее время выполнения нет.  Таким образом, все процессы 1 - 8 можно сдвинуть вправо (выделив их и перетащив за рамку табличного курсора или Вырезать - Вставить) на произвольное количество ячеек. Проверьте и убедитесь, что максимальное количество процессов (чисел 4) не больше четырех. Аналогично выделите процессы 9-12 и сдвигайте их правее - максимальное количество процессов будет 7. Ответ 7.

Ответ

7 (Время не более 10 минут)