<< Предыдущая

стр. 9
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

? 6? ? 3?

54
Как легко видеть, ресурсы образуют поток в сети величины N = 41.
Следовательно, эквивалентный объем комплекса равен
Wэ = T N = 10 41 ? 64 .
Опишем еще один метод оценки эквивалентного объема комплекса.
В основе его лежит следующая теорема:
Теорема 3. Эквивалентный объем комплекса является выпуклой
однородной функцией объемов операций W .
Доказательство. В [3] доказано, что при N(t) = N Tmin ( W ) является

выпуклой функцией своих аргументов. Так как Tmin ( W) = Wэ ( W) N ? , то

Tmin ( W )
из условия выпуклости получаем для

W = ?W 1 + (1 ? ? ) W 2 , 0 ? ? < 1 ,

( ) () ()
Wэ ?W 1 + (1 ? ? ) W 2 ? ?Wэ W1 + (1 ? ? ) Wэ W 2 .

Для доказательства однородности Wэ ( W ) увеличим объем всех операций

в q раз и одновременно увеличим продолжительности всех операций в q
раз. При этом количество ресурсов, выполняющих каждую операцию, не
изменится, а минимальная продолжительность комплекса увеличится в q
раз. Так как Wэ = Tmin ? N ? , то эквивалентный объем также увеличится в q
раз.
Теорема позволяет получать оценки сверху эквивалентного объема
комплекса, представляя его как выпуклую линейную комбинацию
комплексов, эквивалентные объемы которых известны.
Пример 6.4. Рассмотрим комплекс операций, приведенный на
рисунке 6.4. Точное значение эквивалентного объема комплекса равно Wэ
= 3 41 ? 19,2 .
Рассмотрим два комплекса операций, показанных на рисунке
6.5 а, б.

55
1



3
0



2


Рис. 6.4.




1
(16)
(5)

3
0

(8) (10)
2


Рис. 6.5.а



1
(5)

(6) 3
0

(8) (5)
2


Рис. 6.5.б




56
Нетрудно убедиться, что полусумма объемов операций этих
комплексов дает комплекс 6.4. Для комплекса 6.5.а имеем

Wэ1 = 212 + 132 ? 24 ,7 ,
а для комплекса на рисунке 6.5.б:

Wэ2 = 112 + 8 2 + 5 ? 18,6.
Таким образом для исходного комплекса

( )
11
Wэ ? Wэ + Wэ2 = 21,6 .
2
Отклонение от точной оценки составляет 2,4 или примерно 12,5%.
Точность оценки можно улучшить, подбирая различные наборы W1,
W2 и ? такие, что
W = ?W1 + (1 - ?)W2.
Так, например, если ? взять близким к 1, то получаем:
Wэ1?18, Wэ2 ?3/(1-?), Wэ ? 18 + 3 = 21,
что дает ошибку примерно 9%, то есть в два раза меньше.




57
Линейный случай



Рассмотрим линейную зависимость скоростей операций от
количества ресурсов:
?u , u i ? a i
f i (u i ) = ? i .
?a i , u i ? a i
Обозначим ?i = wi/ui - минимальную продолжительность i-ой операции.
Построим интегральный график использования ресурсов на комплексе
операций, полагая, что все операции начинаются в поздние моменты
времени. Для определения поздних моментов начала операций применим
известный алгоритм расчета сетей. Полагаем момент свершения
последнего события tm = T. Если определены поздние моменты начала
всех событий Qi, непосредственно следующих за i-ым, то поздний момент
свершения i-го события определяется по формуле

( )
t n = min t n ? ? ij .
i j
j?Q i

Зная поздние моменты свершения всех событий, легко определить
поздний момент начала всех операций:
t n = t n ? ? ij .
ij j




(5) [8]
[3] 1 3
(2)
(3)
[10]
[0]
(1) 5
0

(2) (1)
(3)
2 4 [9]
[6]


Рис. 6.6.

58
Пример 6.5. Рассмотрим сеть рис.6.6. Длительности операций
указаны в скобках у соответствующих дуг. Длина критического пути
T = 10. Поздние моменты свершения событий указаны в скобках у
соответствующих вершин.


(2)
0 1

(6)
1 3

(4)
0 2

(3)
2 3

(2)
2 4

(1)
3 5
(1)
45 5

Рис. 6.7.а.


60 Mi(Ti)

50


40


30


20


10
Ti
10
Рис. 6.7.б.



59
На рис. 6.7.а приведен календарный график реализации комплекса,
при условии, что все операции начинаются в поздние моменты. Числа у
операций равны количеству ресурсов, занятых на операциях.
На рис. 6.7.б приведен интегральный график использования
ресурсов. График использования ресурсов и представляет собой
агрегированное описание проекта. Действительно, имея агрегированные
описания всех проектов, то есть графики использования ресурсов на них
при условии, что все операции начинаются в наиболее поздние моменты
(такие графики называются правосдвинутыми), мы можем решить задачу
оптимального распределения ресурсов по мультипроекту как по критерию
минимума времени реализации мультипроекта, так и по критерию
упущенной выгоды.
Задача минимизации времени реализации мультипроекта решается
достаточно просто. Пусть Si(t,T) - интегральный график использования
n
ресурсов i-го проекта при его завершении в момент Т, S( t , T) = ? S i ( t , T) -
i =1

интегральный график использования ресурса для мультипроекта, M(t) -
интегральный график имеющегося количества ресурса (рис. 6.8).


M(t) M(t)
S(t, T) Si(Ti)




S(t, T)




T0
T t
Рис. 7.3.
60
Для определения минимального времени окончания
T0
мультипроекта необходимо сдвигать график S(t, T) влево (см. рис. 6.8) до
тех пор, пока он не коснется графика M(t). Получив таким образом
интегральный допустимый график распределения ресурса по
мультипроекту, мы можем декомпозировать его на графики распределения
ресурса для каждого проекта. Задача минимизации упущенной выгоды не
имеет такого простого метода решения. При небольшом числе проектов
проще всего ее решать методом перебора всевозможных упорядочений
проектов. Заметим, что если приоритетность реализации проектов
выбрана, то распределение ресурсов получается сдвигом интегральных
графиков Si(t, T) максимально влево до касания с графиком M(t) в
заданной очередности. При большом числе проектов можно
воспользоваться эвристическим правилом, обоснование которого дано в
параграфе 4.




61
ЗАКЛЮЧЕНИЕ

<< Предыдущая

стр. 9
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>