В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы — время его выполнения в миллисекундах, в третьей строке перечислены
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1; 2 |
| 4 | 7 | 3 |
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Выполните задания, используя данные из файла ниже:
Отсортируем данные в таблице так, чтобы все независимые процессы оказались в начале таблицы. Также в таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.
| A | B | C | D |
|---|---|---|---|
| ID | Время выполнения | ID | Время окончания процесса |
| 1 | 22 | 0 | 22 |
| 2 | 30 | 0 | 30 |
| 4 | 40 | 0 | 40 |
| 12 | 34 | 0 | 34 |
| 18 | 22 | 0 | 22 |
| 8 | 20 | 1 | |
| 5 | 28 | 4 | |
| 19 | 34 | 4 | |
| 7 | 36 | 5 | |
| 10 | 35 | 7 | |
| 11 | 32 | 9 | |
| 15 | 21 | 9 | |
| 20 | 27 | 12 | |
| 17 | 32 | 13 | |
| 3 | 27 | 14 | |
| 6 | 30 | 1;10;11;15 | |
| 9 | 22 | 1;3;4 | |
| 13 | 37 | 10;12 | |
| 16 | 28 | 14;18 | |
| 14 | 26 | 19;20 |
Далее рассчитаем время выполнения оставшихся процессов:
f(8) = 20 + f(1) = 20 + 22 = 42;
f(5) = 28 + f(4) = 28 + 40 = 68;
f(19) = 34 + f(4) = 34 + 40 = 74;
f(7) = 36 + f(5) = 36 + 68 = 104;
f(10) = 35 + f(7) = 35 + 104 = 139;
f(11) = 32 + f(9) = 32 + 149 = 181;
f(15) = 21 + f(9) = 21 + 149 = 170;
f(20) = 27 + f(12) = 27 + 34 = 61;
f(17) = 32 + f(13) = 32 + 176 = 208;
f(3) = 27 + f(14) = 27 + 100 = 127;
f(6) = 30 + max(f(1), f(10), f(11), f(15)) = 30 + 181 = 211;
f(9) = 22 + max(f(1),f(3), f(4)) = 22 + 127 = 149;
f(13) = 37 + max(f(10), f(12)) = 37 + 139 = 176;
f(14) = 26 + max(f(19), f(20)) = 26 + 74 = 100;
f(16) = 28 + max(f(14), f(18)) = 28 + 100 = 128.
| A | B | C | D |
|---|---|---|---|
| ID | Время выполнения | ID | Время окончания процесса |
| 1 | 22 | 0 | 22 |
| 2 | 30 | 0 | 30 |
| 4 | 40 | 0 | 40 |
| 12 | 34 | 0 | 34 |
| 18 | 22 | 0 | 22 |
| 8 | 20 | 1 | 42 |
| 5 | 28 | 4 | 68 |
| 19 | 34 | 4 | 74 |
| 7 | 36 | 5 | 104 |
| 10 | 35 | 7 | 139 |
| 11 | 32 | 9 | 181 |
| 15 | 21 | 9 | 170 |
| 20 | 27 | 12 | 61 |
| 17 | 32 | 13 | 208 |
| 3 | 27 | 14 | 127 |
| 6 | 30 | 1;10;11;15 | 211 |
| 9 | 22 | 1;3;4 | 149 |
| 13 | 37 | 10;12 | 176 |
| 14 | 26 | 19;20 | 100 |
| 16 | 28 | 14;18 | 128 |
| МАКС | 211 |
Ответ: 211.