Question

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

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

| ID процесса | Время выполнения (мс) | ID предшественников |
|---|---|---|
| 1 | 24 | 0 |
| 2 | 20 | 0 |
| 3 | 19 | 10 |
| 4 | 22 | 0 |
| 5 | 25 | 2 |
| 6 | 23 | 4;5;7;8 |
| 7 | 18 | 5 |
| 8 | 22 | 1;5 |
| 9 | 21 | 3;4 |
| 10 | 19 | 7 |
| 11 | 22 | 15 |
| 12 | 24 | 9 |
| 13 | 25 | 10;12 |
| 14 | 20 | 11;15 |
| 15 | 24 | 0 |
| 16 | 25 | 13 |
| 17 | 22 | 14;16 |

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

Accepted Answer

218

Answer

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

Алгоритм:
1. Для независимых процессов (предшественники = 0) время завершения равно их длительности.
2. Для зависимых процессов время завершения = длительность процесса + максимум времён завершения всех предшественников.
3. Ответ — максимальное время завершения среди всех процессов.

Расчёты:

Независимые процессы:
- Процесс 1: 24
- Процесс 2: 20
- Процесс 4: 22
- Процесс 15: 24

Зависимые процессы (в порядке возрастания ID):
- Процесс 5: 25 + 20 = 45
- Процесс 7: 18 + 45 = 63
- Процесс 8: 22 + max(24, 45) = 67
- Процесс 3: 19 + 63 = 82
- Процесс 10: 19 + 63 = 82
- Процесс 9: 21 + max(82, 22) = 103
- Процесс 6: 23 + max(22, 45, 63, 67) = 90
- Процесс 11: 22 + 24 = 46
- Процесс 12: 24 + 103 = 127
- Процесс 13: 25 + max(82, 127) = 152
- Процесс 14: 20 + max(46, 24) = 66
- Процесс 16: 25 + 152 = 177
- Процесс 17: 22 + max(66, 177) = 199

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

```python
import pandas as pd

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

finish_time = {}

for _, row in df.iterrows():
    proc_id = row['ID процесса']
    duration = row['Время выполнения процесса']
    preds_str = str(row['ID предшественников'])
    
    if preds_str == '0' or preds_str == 'nan':
        preds = []
    else:
        preds = [int(p.strip()) 
                 for p in preds_str.split(';') 
                 if p.strip() and p.strip() != '0']
    
    if preds:
        start_time = max(finish_time[p] for p in preds)
    else:
        start_time = 0
    
    finish_time[proc_id] = start_time + duration

print(max(finish_time.values()))
```

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=214640)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=214642)

ID процесса	Время выполнения (мс)	ID предшественников
1	24	0
2	20	0
3	19	10
4	22	0
5	25	2
6	23	4;5;7;8
7	18	5
8	22	1;5
9	21	3;4
10	19	7
11	22	15
12	24	9
13	25	10;12
14	20	11;15
15	24	0
16	25	13
17	22	14;16

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