Задача: задан комплекс из 20-ти работ, схематично заданный в виде таблицы, где в узлах обозначены длительности работ. Каждую работу можно начинать выполнять только после окончания выполнения работ, находящихся слева и сверху. Первая работа – левый верхний угол, правый нижний – последняя работа.
Найти:
1) Минимальное время выполнения комплекса работ,
2) Самые ранние и самые поздние сроки выполнения каждой работы, ответ записать в виде соответствующей матрицы,
3) Полный и свободный резервы каждой работы,
4) Критический путь,
5) Количество критических работ,
6) Количество работ, у которых свободный резерв равен нулю,
7) Количество работ, у которых свободный резерв равен полному.
| 7 | — | 5 | — | 7 | — | 5 | — | 3 |
| | | | | | | | | | | ||||
| 4 | — | 5 | — | 3 | — | 3 | — | 5 |
| | | | | | | | | | | ||||
| 6 | — | 5 | — | 7 | — | 5 | — | 6 |
| | | | | | | | | | | ||||
| 6 | — | 3 | — | 5 | — | 3 | — | 4 |
Решение:
Найдем минимальное время выполнения каждой работы. Для этого построим матрицу ранних сроков по следующему правилу: для каждой клетки выбирается максимум из чисел, стоящих выше и левее и прибавляется время выполнения этой работы.
Для работы (1;1), т.е. первая строка и первый столбец, считаем начало равным нулю и длительность равна 7, т.е. начинаем заполнять матрицу:
| 0-7 | ||||
Для работы (1:2) есть только работа левее нее (т.е. предшествующая) (1;1) заканчивается в 7 и плюс длительность этой работы 5.
Для работы (2:1) есть только работа выше нее, она заканчивается в 7 и время выполнения работы 4.
Заполним матрицу:
| 0-7 | 7-12 | |||
| 7-11 | ||||
И для работы (2;2) работа выше нее заканчивается через 12 единиц времени, работа левее нее заканчивается в 11, max(11;12)=12 и еще время ее выполнения – 5 единиц. Подставим это в ячейку и заполним таблицу до конца.
| 0-7 | 7-12 | 12-19 | 19-24 | 24-27 |
| 7-11 | 12-17 | 19-21 | 24-27 | 27-32 |
| 11-17 | 17-22 | 22-29 | 29-34 | 34-40 |
| 17-23 | 23-26 | 29-34 | 34-37 | 40-44 |
Получили матрицу ранних сроков. Весь комплекс работ может быть выполнен за 44 единицы времени.
Найдем матрицу поздних сроков.
Составлять матрицу поздних сроков нужно с конца. Для того, чтобы заполнить ячейку, следует выбрать минимальное время начала работ правее и ниже выбранной. Это будет время окончания выбранной работы.
Последняя работа начинается в 40. Для работы (3;5) правее и ниже есть только работа (4;5), она начинается в 40 и длится она 6, т.е. работа (3;5) должна заканчиваться в 40. Аналогично и работа (4;4) должна закончиться в 40 и длится она 3 единицы.
| 34-40 | ||||
| 37-40 | 40-44 |
Рассмотрим работу (3;4), работа правее нее начинается в 34, а работа ниже нее начинается в 37, min(34;37)=34, т.е. в этот момент времени работа (3;4) должна закончиться, и длится она 5 единиц времени. Заполним матрицу до конца.
| 0-7 | 7-12 | 12-19 | 21-26 | 26-29 |
| 7-11 | 12-17 | 19-22 | 26-29 | 29-34 |
| 11-17 | 17-22 | 22-29 | 29-34 | 34-40 |
| 23-29 | 29-32 | 32-37 | 37-40 | 40-44 |
Получили матрицу поздних сроков.
Определим полный и свободный резервы работ.
Для того, чтобы вычислить полный резерв работы следует рассмотреть соответствующие ей ячейки матриц ранних и поздних сроков и вычесть из позднего срока окончания работы ее ранний срок окончания. Например, для работы (2;4):
| Ячейка матрицы ранних сроков |
Яч-ка матрицы поздних сроков: |
| 24-27 | 26-29 |
| Получим значение ячейки матрицы полных резервов: | |
| 29-27=2 | |
Составим матрицу полных резервов:
| 0 | 0 | 0 | 2 | 2 |
| 0 | 0 | 1 | 2 | 2 |
| 0 | 0 | 0 | 0 | 0 |
| 6 | 6 | 3 | 3 | 0 |
Составим матрицу свободных резервов из соображений, что свободный резерв, которым можно располагать при выполнении данной работы в предположении, что предыдущая и последующая работы начинаются в свои ранние сроки.
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 2 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 3 | 0 | 3 | 0 |
Получили матрицу свободных резервов. Количество работ, у которых свободный резерв равен нулю – 16 шт.
Определим критические пути. Для этого рассмотрим матрицу полных резервов и пройдем от первой работы до последней через нули, двигаясь вправо или вниз. Например :
(1;1)- (1;2)- (2;2)- (3;2)- (3;3)- (3;4)- (3;5)- (4;5). Этот критический путь не является единственным.
Также по матрице свободных резервов можно определить количество критических работ, т.е. работ, у которых полный резерв равен нулю. Здесь таких работ 11 шт.
Количество работ, у которых свободный резерв равен полному в этой задаче равен 13 шт.