Задание 22: Вычислительные процессы

Общая информация

• Тема: параллельное и последовательное выполнение процессов, минимальное время завершения всей совокупности работ.
• Формат данных: таблица (файл .ods / .xlsx) с колонками: ID процесса, время выполнения (мс), ID процессов-предшественников (0 - если независимый).
• Ответ: минимальное время завершения всех процессов при оптимальном расписании.
• Балл: 1. Время: 8 мин.

Правила

• Процессы не приостанавливаются - начавшийся процесс выполняется до конца.
• Независимые процессы (нет предшественников) могут выполняться параллельно.
• Если процесс B зависит от процесса A, то B не может начаться раньше, чем завершится A.
• Один процесс может зависеть от нескольких - тогда он стартует после завершения всех своих предшественников.

Задания: N22. Параллельные процессы

Идея решения

1. Построить граф зависимостей: ребро A → B означает «A должен завершиться до старта B».
2. Для каждого процесса вычислить время начала = максимум по всем временам завершения предшественников.
3. Время завершения процесса = время начала + его длительность.
4. Ответ = максимум времён завершения среди всех процессов.

Этот метод называется нахождением критического пути (метод CPM).

Алгоритм по шагам. ЧЕРЕЗ ВПР

Задание:

Решение:

1. Для дальнейшего удобства переименуем заголовки в "ID" "Время" "ID влияющих"
   

2. Распределяем ID влияющих на несколько столбцов (1 ID = 1 столбец) с помощью инструмента "Текст по столбцам..." во вкладке Данные
   

3. Выделить цветом столько же столбцов, сколько и id влияющих, назвать "Время влияющих". Назвать "Начало" и "Конец"
   

4. В ячейку Начало 1-го процесса прописываем формулу =МАКС(время влияющих)+1
   

5. В ячейку Конец 1-го процесса прописываем формулу = Ячейка"Начало" + Ячейка"Время" - 1
   

6. Растягиваем ячейки "Начало" и "Конец" на весь столбец

Проверка: в столбце Начало все значения должны быть 1, в столбце Конец такие же, как и в столбце Время
7. В ячейке "Время влияющих" прописываем формулу ВПР, которая будет выглядеть как
=ВПР(ячейка с ID влияющего процесса; все столбцы таблицы + F4 для $(закрепление значений); номер столбца "Конец"; 0)
ВАЖНО!:

• первым значением выбираем ячейку нужного процесса из ID влияющих
  
• ставить после каждого значения ";" и пробел,
  
• вторым значением - выделять таблицу через выделение столбцов (тянуть по буквам наверху стобцов),
  
• фиксировать таблицу через F4 чтобы выл вид $A$J, где A и J это первый и последний столбцы таблицы,
  
• третим значением в впр писать номер последнего столбца цифрой, например, номер столбца J это 10,
  
• четвертым значением писать 0 (отвечает за поиск только полного совпадения)
  
  Результат должен быть такой как на скрине ниже, ошибка из-за ссылки на несуществующий индекс ID 0

9. Добавляем 0 в столбец ID, ошибка пропала

10. Копируем формулу на все остальные ячейки из Время влияющих

11. Результат

12. Делаем замену всех пустых пространств в столбцах ID влияющих на 0
    

13. Выводим максимальное время через формулу МАКС по столбцу Конец
    

14. Результат: 51

Алгоритм по шагам. ГРАФИЧЕСКОЕ РЕШЕНИЕ

Задание:

Решение:

1. Для дальнейшего удобства переименуем заголовки в ID Время ID влияющих и расставим время (начало с 1, не как в изображении)
   
   

2. Закрашиваем столько клеток, сколько указано в стобце В. Если в задание требуется посчитать, добавляем счетчик (1 в закрашенную ячейку)
   

3. Так как влияющих процессов нет, первые два процесса будут параллельными
   

4. На 3 процесс влияют процессы 1 и 2, поэтому они будут последовательными (3 начнется тогда когда закончится 1 и 2)
   

5. Последовательно заполняем остальные процессы

6. Ответом будет последняя число, под которым закрашена клетка

Типичные ошибки

Материалы будут дополняться.