8.4. Оптимизация сетевого графика по ресурсам
Задача оптимального распределения ресурсов является одной из важнейших задач планирования. Для простоты изложения рассмотрим случай, когда используется один вид ресурсов.
Пусть проект задан сетевым графиком . Имеющееся количество ресурса равно R. Каждая работа проекта характеризуется продолжительностью выполнения tij и интенсивностью потребления ресурса rij . Под интенсивностью потребления будем понимать требуемое количество ресурса для выполнения работы в единицу времени. Рассмотрим случай, когда интенсивности постоянные. Под оптимальным распределением ресурсов понимается такое размещение работ во времени,
при котором в любой момент времени было бы достаточно ресурса для выполнения работ, а время выполнения всего комплекса работ было бы минимальным. Работы не допускают перерыва в выполнении.
На практике получили широкое применение эвристические методы распределения ресурсов. Отметим, что приведенный ниже алгоритм не всегда позволяет найти оптимальное решение задачи, однако часто дает хорошее приближение к нему.
Алгоритм оптимизации комплекса работ по распределению ресурсов
Предварительный шаг. Составить линейный график выполнения проекта. Определить по нему критическое время tкр и критический путь.
Первый шаг. 1. Спроецировать на ось времени начало и конец каждой работы и обозначить проекцию, совпадающую с началом координат, через 0, а следующую за ней – через 1.
2. Определить полные резервы времени работ Rп(i,j), расположенных над промежутком (0,1). Пронумеровать эти работы в порядке возрастания их полных резервов. Работы с одинаковыми полными резервами времени нумеруют в порядке убывания интенсивностей.
3. Просуммировать последовательно интенсивности работ, расположенных над промежутком (0,1) в порядке возрастания присвоенных им номеров, сравнивая полученные суммы с заданной величиной ресурса R. Все работы, сумма интенсивностей которых не превосходит R, оставить в первоначальном положении. Если после прибавления интенсивности какой-нибудь работы окажется, что суммарное потребление ресурсов больше R, то эту работу сдвинуть вправо на величину рассматриваемого промежутка, перейти к добавлению интенсивности следующей работы и так продолжать до тех пор, пока не будут просмотрены все работы, расположенные над промежутком (0, 1).
Результатом выполнения этого действия является новый линейный график, момент 1 которого считается началом оставшейся части комплекса работ. Работы , расположенные над промежутком (1, кр), изобразить так, чтобы их начала совпадали с новыми ранними сроками свершения событий.
Общий шаг. Пусть выполнено k шагов алгоритма и получен линейный график, момент k которого является началом оставшейся части комплекса работ.
1. Спроецировать на ось времени начало и конец каждой работы, расположенной над промежутком (k, кр), и обозначить проекцию, ближайшую к k, через k+1. Таким образом, будет выделен новый промежуток (k , k+1 ).
2. Определить полные резервы работ Rп(i,j), расположенных над промежутком (k ,k+1), и пронумеровать их. Сначала нумеруются работы , начатые левее момента k, согласно возрастанию разностей между полными резервами этих работ и длительностями от начала до момента k+1 (длительности работ обозначим через lij). Работы с одинаковыми разностями нумеруются в порядке убывания интенсивностей. Все остальные работы нумеруются в порядке возрастания их полных резервов, а с одинаковыми резервами – в порядке убывания интенсивностей.
3. Эти действия выполняются так же, как и действие 3 первого шага.
Однако следует иметь в виду, что если сдвигу подлежит работа , начатая левее k, то сдвигается вся работа, т.е. начало этой работы устанавливается в момент k+1.
4. Проверить, все ли работы комплекса просмотрены. Если все, то решение закончено, если нет, то необходимо вернуться к первому действию общего повторяющегося шага.
Пример
8.4.1. Предприятие
осваивает производство нового изделия.
С этой целью создана группа из
специалистов и составлен сетевой график
выполнения работ (рис 8.4.1). Известны
продолжительность tij
(в днях) каждой работы
(первое
число, указанное на ребре) и интенсивность
потребления ресурса rij
(количество специалистов, необходимое
для выполнения работы
в единицу времени
число в скобках, указанное на ребре).
Рис. 8.4.1
Требуется:
построить линейный график и диаграмму использования ресурса, найти критический путь и критическое время tкр;
найти полные
резервы времени для некритических работ
;
установить сроки начала и окончания работ так, чтобы в любой момент реализации проекта потребность в специалистах не превосходила , а время осуществления проекта было минимальным.
Решение.
Строим график Ганта, указывая над каждым отрезком значение rij.
(i,j)
(4,5)
4
(3,5)
5
8
(2,5)
9
(2,4)
(2,3)
3
(1,3)
7
5
(1,2)
t
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
12
5
20
22
17
9
4
Рис. 8.4.2
Очевидно, что
Критический путь выделен жирной линией
и определяется работами:(1,2), (2,4), (4,5).
Для построения
шкалы потребления ресурса спроецируем
на ось Ot
начальные и конечные точки всех работ.
Получим промежутки (0,2), (2,4), (4,6), (6,7),
(7,9), (9,12), (12,14). В этих промежутках суммируем
интенсивности rij
работ, расположенных над ними. Так,
например, на промежутке (4,6) суммарная
интенсивность составляет
;
на промежутке (6,7):
.
По линейному
графику определяем полные резервы
некритических работ (для критических
работ
).
Работу (3,5) можно отсрочить или увеличить
ее продолжительность на 2 дня (согласно
времени окончания выполнения проекта),
т.е.
.
Работу (2,3) можно было бы отсрочить
(сдвинуть вправо) на 8 дней, но после ее
завершения начинается работа (3,5), а ее
можно отсрочить только на 2 дня, поэтому
и
.
Аналогично,
,
.
Из шкалы потребления
ресурса видно, что в промежутках (4,6),
(6,7), (7,9) число требуемых специалистов
превышает их наличие. Необходимо
отстрочить начало некоторых работ таким
образом, чтобы на каждом промежутке
.
Для определения работ, подлежащих сдвигу, используем алгоритм оптимизации комплекса работ по распределению ресурсов.
Предыдущее решение задачи соответствует выполнению предварительного и первого шагов алгоритма. На данном этапе предстоит действовать по общему шагу алгоритма. Выполним упорядочивание работ на промежутке (4,6):
;
;
№ 2;
;
;
№ 1;
;
№ 3,
так как
.
,
,
следовательно сдвигаем работу (2,5) вправо на длину промежутка (4,6), равную 2 дням.
Так как на
следующем промежутке (6,7)
,
а работа (2,5) уже начнется к моменту
времени
,
то избегая лишнего шага, можно сдвинуть
работу (2,5) еще на один день, тем более,
что
,
т.е., очевидно, надо сдвинуть работу
(2,5) на 3 дня.
Получим новый линейный график (рис.8.4.3).
Рис. 8.4.3
На промежутке
(7,12)
.
Упорядочиваем работы:
;
;
№ 3;
;
;
№ 1;
;
;
№ 2.
Работа (3,5) к моменту
уже началась, поэтому ей присвоили №1.
,
поэтому (4,5)
№ 2, (2,5)
№ 3.
,
.
Работу (2,5) сдвигаем вправо на 5 дней (длину промежутка (7,12)).
Получим новый линейный график (рис. 8.4.4).
Время, необходимое для выполнения всего проекта при использова-нии 15 специалистов, составит 17 дней.
(i,j)
4
(4,5)
(3,5)
5
(2,5)
8
9
(2,4)
3
(2,3)
(1,3)
7
5
t
(1,2)
17
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
12
5
12
14
9
12
8
Рис. 8.4.4
Составим таблицу новых сроков начала (tн) и окончания (tо) работ.
Таблица 8.4.1
Работа Сроки |
(1,2) |
(1,3) |
(2,3) |
(2,4) |
(2,5) |
(3,5) |
(4,5) |
tн tо |
0 4 |
0 2 |
4 6 |
4 7 |
12 17 |
6 12 |
7 14 |