Задание 22

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

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

Скачать файл

Теория

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

Решение

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

Правее каждого процесса, учитывая его зависимость или независимость выделяем заливкой и заполняем числами 1 необходимое количество ячеек. Затем в каждом столбце, начиная с D подсчитываем сумму единиц со 2 строки по 14 строку, применяем условное форматирование и анализируем.

Максимальное количество параллельных процессов равно 4, а максимальный отрезок, когда выполняются 4 параллельных процессов, равен 5.

Но будьте внимательны - процессы 101, 102 и 109 независимы. Это значит что их можно запускать когда угодно, независимо друг от друга! В данной задаче Например процесс 102 можно начать с 4 мс. В данной задаче условие, что все независимые друг от друга процессы могут выполняться параллельно и время окончания работы всех процессов минимально. Это значение 37 мс (процессы 109 - 113).  Таким образом, все процессы 101 - 108 можно сдвинуть право (выделив их и перетащить за рамку табличного курсора или Вырезать - Вставить) не более чем на одну ячейку (1 мс). Проверьте и убедитесь, что максимальное количество процессов (чисел 4) не меняется.

Ответ

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