Задание повышенного уровня сложности (7 минут на выполнение). Необходимо построить математическую модель для решения практической задачи, используя предоставленный файл с информацией о N вычислительных процессах. Выполнение процессов нельзя прерывать. Процесс B зависит от процесса A, если для выполнения B необходимы результаты A; в этом случае они выполняются последовательно. Задача: определить максимальную продолжительность отрезка времени, в течение которого возможно одновременное выполнение максимального количества процессов, минимизируя общее время выполнения.
Моделирование с помощью диаграммы Ганта
Для решения удобно использовать диаграмму Ганта. Создадим таймлайн, отображающий время выполнения каждого процесса в миллисекундах (достаточно 44 мс, при необходимости количество можно увеличить). Каждый процесс характеризуется ID, временем выполнения и ID процессов, от которых он зависит (0 – если зависимостей нет). Пример:
- Процесс 101: 12 мс, зависимостей нет. Начало: 1 мс.
- Процесс 102: 9 мс, зависимостей нет.
- Процесс 103: 2 мс, зависит от 101 и 102. Начало: 12 мс.
- Процесс 104: 4 мс, зависит от 103.
- Процесс 105: 18 мс, зависит от 103.
- Процесс 106: 1 мс, зависит от 104.
- Процесс 107: 1 мс, зависит от 105 и 106.
- Процесс 108: 3 мс, зависит от 107.
- Процесс 109: 8 мс, зависимостей нет.
- Процесс 110: 14 мс, зависит от 109.
- Процесс 111: 6 мс, зависит от 109.
- Процесс 112: 15 мс, зависит от 110 и 111.
- Процесс 113: 11 мс, зависит от 111.
Визуализация данных на диаграмме Ганта с цветным выделением повысит наглядность.
Определение максимальной продолжительности
Для подсчета количества одновременно выполняемых процессов в каждую миллисекунду воспользуемся функцией СЧЁТ. Это позволит определить количество активных процессов в каждый момент времени. Важно минимизировать общее время выполнения всех процессов.
Анализ диаграммы Ганта (сгруппировав процессы: 101, 102 и зависимые от них; 109 и зависимые от него) показывает, что максимальное количество одновременно выполняемых процессов равно четырем. Максимальная продолжительность отрезка времени с четырьмя параллельными процессами составляет 5 мс.
Оптимизация графика выполнения процессов не позволяет получить результат, превышающий 5 мс одновременного выполнения четырех процессов. Ответ: 5.