Решение. Заметим, что время выполнения всей совокупности процессов равно времени выполнения самого длинного процесса.
Посчитаем время выполнения процессов В, не зависящих от процессов А. Для этого введем в столбец D формулы для строк, в которых процесс А равен 0. Это процессы 1, 2, 9 и 10. В ячейку D2 введем =B2, в D3 — =B3, в D10 — =B10 и в D11 — =B11.
Посчитаем время выполнения процессов, зависящих от одного процесса А. Это процессы 4, 5, 6, 8, 11, 12 и 16. В ячейку D5 введем =B5+D4, где В5 — время процесса В, а D4 — время процесса, от которого зависит процесс В. В D6 — =B6+D4, в D7 — =B7+D6, в D9 — =B9+D8, в D12 — =B12+D10, в D13 — =B13+D11 и D17 — =B17+D16.
Посчитаем время выполнения процессов, зависящих от двух процессов А. Это процессы 3, 7, 14 и 15. В ячейку D4 введем =B4+МАКС(D2;D3), где В4 — время процесса В, а МАКС(D2;D3) — максимальное время процессов, от которого зависит процесс В (выбираем максимальное, так как процессы могут идти параллельно). В D8 — =B8+МАКС(D5;D7), в D15 — =B15+МАКС(D4;D13) и в D16 — =B16+МАКС(D9;D14).
Посчитаем время выполнения процессов, зависящих от трех процессов А. Это процесс 13. В ячейку D14 введем =B14+МАКС(D8;D12;D13), где В14 — время процесса В, а МАКС(D8;D12;D13) — максимальное время процессов, от которого зависит процесс В (выбираем максимальное, так как процессы могут идти параллельно).
Найдем максимальное время выполнения самого длинно процесса, введя формулу =МАКС(D2:D17), и получим время выполнения всех процессов — 37.
Ответ: 37.
Приведём решение Евгения Джобса на языке Python.
# скопируем содержимое таблицы в файл
# и прочитаем его.
# Заменим точки с запятой на пробелы
file = open('22.txt').read().replace(';', ' ')
# преобразуем данные в список строк из чисел
nums = [[int(x) for x in s.split()]
for s in file.split('\n')]
# создадим словарь вида
# №процесса: (время выполнения, процессы)
pr = {c[0]:(c[1], c[2:]) for c in nums[:-1]}
# определим функцию, которая
# возвращает время работы процесса
# n - номер процесса
def f(n):
# если номер равен 0, то время выполнения 0
# (начало всех процессов)
if n == 0: return 0
# иначе максимальное время выполнения
# для всех предыдущиъ процессов
# плюс время выполнения процесса n
return max(f(x)
for x in pr[n][1]) + pr[n][0]
# находим максимальное значение
print(max(f(x) for x in pr))
Примечание.
Из файла следует удалить строку заголовков и разбить ячейки с перечнями процессов, от которых зависит данный процесс, на отдельные ячейки с помощью мастера «Текст по столбцам». Файл следует сохранить в формате txt.
Приведём решение Михаила Глинского на языке Python.
f=open('22.txt')
res={'0':0}
for s in f:
n,t,*ff=s.split()
res[n]=max([res[x] for x in ff])+int(t)
print(max(res.values()))
Примечание.
Из файла следует удалить строку заголовков и разбить ячейки с перечнями процессов, от которых зависит данный процесс, на отдельные ячейки с помощью мастера «Текст по столбцам». Файл следует сохранить в формате txt.
PDF-версии: 