Наши Партнеры:

 


Главная > Самоучители > Разное > Задача о сетевом графике.

Задача о сетевом графике.

Задача: задан комплекс из 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 шт.