Question

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Процесс B зависит от процесса A, если для выполнения B необходимы результаты A. В этом случае процессы выполняются только последовательно.

Информация представлена в виде таблицы:
- первый столбец — идентификатор процесса (ID);
- второй столбец — время выполнения в миллисекундах;
- третий столбец — ID процессов-предшественников, разделённые «;». Если процесс независимый, указано значение 0.

Типовой пример:

| ID процесса | Время выполнения (мс) | ID предшественников |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1; 2 |
| 4 | 7 | 3 |

Определите минимальное время завершения всей совокупности процессов при условии, что все независимые друг от друга процессы выполняются параллельно.

Accepted Answer

211

Answer

Идея решения: для каждого процесса вычислить время его завершения как сумму его длительности и максимального времени завершения всех его предшественников; ответ — максимальное время завершения среди всех процессов.

Алгоритм:

1. Загрузить данные из файла.
2. Для каждого процесса определить его предшественников.
3. Вычислить время завершения каждого процесса по формуле:
   $$	ext{finish}[i] = 	ext{duration}[i] + \max(	ext{finish}[j] : j \in 	ext{predecessors}[i])$$
   где для независимых процессов максимум равен 0.
4. Найти максимальное время завершения среди всех процессов.

Реализация:

```python
import pandas as pd

df = pd.read_excel('22.xlsx')

finish_time = {}

for _, row in df.iterrows():
    process_id = row['ID процесса B']
    duration = row['Время выполнения процесса B (мс)']
    predecessors_str = str(row['ID процесса(ов) A'])
    
    # Парсим предшественников
    if predecessors_str == '0' or predecessors_str == 'nan':
        predecessors = []
    else:
        predecessors = [int(p.strip()) 
                       for p in predecessors_str.split(';') 
                       if p.strip() and p.strip() != '0']
    
    # Вычисляем время завершения
    if predecessors:
        max_pred_time = max(finish_time[p] for p in predecessors)
    else:
        max_pred_time = 0
    
    finish_time[process_id] = max_pred_time + duration

# Ответ — максимальное время завершения
result = max(finish_time.values())
print(result)
```

Прогон на примере из условия:
- Процессы 1, 2, 4, 12, 18 независимы: завершаются в моменты 22, 30, 40, 34, 22 соответственно.
- Процесс 8 зависит от 1: $20 + 22 = 42$.
- Процесс 5 зависит от 4: $28 + 40 = 68$.
- Процесс 19 зависит от 4: $34 + 40 = 74$.
- Процесс 7 зависит от 5: $36 + 68 = 104$.
- Процесс 10 зависит от 7: $35 + 104 = 139$.
- Процесс 11 зависит от 9: $32 + 149 = 181$.
- Процесс 15 зависит от 9: $21 + 149 = 170$.
- Процесс 20 зависит от 12: $27 + 34 = 61$.
- Процесс 17 зависит от 13: $32 + 176 = 208$.
- Процесс 3 зависит от 14: $27 + 100 = 127$.
- Процесс 6 зависит от 1, 10, 11, 15: $30 + \max(22, 139, 181, 170) = 30 + 181 = 211$.
- Процесс 9 зависит от 1, 3, 4: $22 + \max(22, 127, 40) = 22 + 127 = 149$.
- Процесс 13 зависит от 10, 12: $37 + \max(139, 34) = 37 + 139 = 176$.
- Процесс 14 зависит от 19, 20: $26 + \max(74, 61) = 26 + 74 = 100$.
- Процесс 16 зависит от 14, 18: $28 + \max(100, 22) = 28 + 100 = 128$.

Максимальное время завершения: 211.

Задание №22Алгоритмы и исполнителиЕГЭ по информатике