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

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

ОГЛАВЛЕНИЕ

Следующая >>

1 1
+ =7
1 ? w1 1 ? w 2
1 1
+ = 14
? (1 ? w 1 ) ? (1 ? w 2 ) (2.7)

Сразу получаем, что ? = ?.
Решая два последних уравнения относительно w1 и w2 получаем:
40 ? T 52 ? T
w1 = ; w2 = .
20 + T 20 + T
Наконец, подставляя эти решения в уравнение (2.7), получаем квадратное
уравнение относительно T:
2T2 - 63T + 460 = 0,
корни которого - T = 20 и T = 11,5. Второй корень не подходит, поскольку
w2 не может быть больше 1. Окончательно получаем, что обе операции
будут завершены за время
Tmin = T1 + T = 30 ,
причем скорости операций
w11 = 0,5 ; w21 = 0,8 ;
w12 = ?(1 + w11) = 0,75 ; w22 = ?(1 + w21) = 0,9 .
Соответственно, оптимальное распределение ресурсов имеет вид:
5w 11 5w 21
= =5 ; = = 20 ;
u 11 u 21
1 ? w 11 1 ? w 21



22
5w 12 5w 22
u 12 = = 15 ; u 22 = = 45 .
1 ? w 12 1 ? w 22

Предположим теперь, что функция ?(??h) является мультипликативной, то
есть
?( ? ? h) = ? 1 ( ? ) ? ? 2 ( h) .

В этом случае из инвариантности по направлению векторов hq следует
инвариантность по направлению векторов скоростей wq. Это позволяет
упростить систему уравнений (2.5), (2.6), записав ее в переменных {wi},
{?q} и T:

? ? i [? q ? w i ] = N q ,
n
q = 1, k (2.8)
i =1

k

? ? q w i ? Tq = Wi , i = 1, n . (2.9)
q =1

Рассмотрим два важных частных случая, когда зависимости
скоростей от количества ресурсов описываются степенными или
линейными функциями.


Степенные зависимости скоростей от количества ресурсов

Пусть fi(ui) = ui?, i = 1, n , 0<?<1. Имеем ui= ?i(wi) = wi1/?, hi(wi)=

?i’(wi) = 1/? wi1-?/?, i = 1, n . В этом случае вектор h коллинеарен вектору w
и поэтому инвариантность вектора скоростей по направлению очевидна.
Заметим, что {xiq}, Nq и Tq связаны соотношением:
?
? n 1? ?
? ? x iq ?
? i =1 ?
q = 1, k .
= Tq ,
N?
q




23
?
n
? x 1? ?
Назовем величину X q = ? ? iq ? эквивалентным объемом работ в q-ом
? ?
i =1

интервале, Nq? - эквивалентной скоростью выполнения этих работ. Если
изобразить фазовое пространство состояний в q-ом интервале (рис. 2.1),
то любому процессу выполнения работ в q-ом интервале соответствует
некоторая траектория, соединяющая начало координат с точкой Xq = {xiq},
соответствующей окончанию всех работ в q-ом интервале.
x2q




x1q
0

Рис. 2.1

Движение по этой траектории происходит со скоростью Nq?, а расстояние
между двумя точками xq1 и xq2 равно:
?
? ??
( )
1
? x 1 , x 2 = ?? x1 ? x iq
2
?.
q q iq
?i ?
Как известно, кратчайшей траекторией, соединяющей любые две точки,
является прямая, поэтому оптимальному распределению ресурсов
соответствует прямая, соединяющая точку 0 с точкой xq.
Рассмотрим теперь фазовое пространство состояний всего комплекса
операций. Аналогично случаю одного интервала, любому процессу
выполнения операций соответствует кривая, соединяющая точку 0 с

24
точкой W, движение по которой происходит со скоростью Nq?, q = 1, k .
Поэтому оптимальному распределению ресурса соответствует прямая,
соединяющая точку 0 с точкой W. Длина этой прямой называется
эквивалентным объемом мультипроекта Wэ. Это и есть свойство
инвариантности вектора скоростей по направлению для рассматриваемого
случая. Чтобы определить минимальное время завершения всех операций,
необходимо сначала найти минимальное k, такое, что
k

? N ? ? Tq < Wэ
q
q =1

k +1

? N q ? Tq ? Wэ .
?

q =1

Величина минимального времени реализации проекта определяется
выражением:
k
Wэ ? ? N ? ? Tq
q
k
Tmin = ? Tq +
q =1
.
N ?+1
q =1 k

Так как xiq = ?qWi, то xqэ = ?qWэ. Величина ?q (это доля эквивалентного
объема, выполняемая в q-ом интервале) определяется выражением:
k
Wэ ? ? N ? ? Tq
q
k
Tmin = ? Tq +
q =1
.
N ?+1
q =1 k

Пример 1.2. Мультипроект состоит из трех проектов, объемы
которых - W1 = 3, W2 = 4, W3 = 10. Зависимости скоростей
соответствующих операций от количества ресурсов имеют вид
f i ( u i ) = u i , i = 1, 2, 3. Поквартальное финансирование планируется в

следующих объемах - N1 = 1 (T1 = 3 мес.), N2 = 4 (T2 = 3 мес.), N3 = 9
(T3 = 3 мес.), N4 = 1 (T4 = 3 мес.). Удастся ли завершить все проекты в
третьем квартале? Определим эквивалентный объем мультипроекта:

25
Wэ = 32 + 4 2 + 10 2 = 5 5 .

Эквивалентная скорость w э = N q и равна wэ1 = 1 в первом квартале, wэ2

= 2 - во втором, wэ3 = 3 - в третьем. Проверим возможность реализации
проекта в третьем квартале.
wэ1?T1 + wэ2?T2 + wэ3?T3 = 1?3 + 2?3 + 3?3 = 18 > Wэ,
поэтому реализация проекта в третьем квартале возможна. Для более
точной оценки определим
Wэ ? 9 5 5?9 5
Tmin = 6 + =6+ ?6 .
3 3 6
Таким образом, мультипроект будет завершен в конце июля.


Линейные зависимости скоростей от количества ресурсов

Случай линейных зависимостей скоростей операций от количества
ресурсов широко распространен, поскольку пропорциональность объема
выполненных работ количеству ресурсов довольно часто имеет место с
достаточной для практики точностью. Пусть

?u , если u i ? a i
w i = f i (u i ) = ? i .
?a i , если u i ? a i

Обозначим, как и ранее, xiq - объем работ i-го проекта, выполняемых
в q-ом интервале. Рассмотрим задачу о возможности реализации проекта в
первых k интервалах. Эта задача сводится к проверке существования
решений следующей системы линейных неравенств:

? x iq ? N q Tq , q = 1, k
i


? x iq ? Wi , i = 1, n
q


x iq ? a i ? Tq , i = 1, n , q = 1, k .

26
Необходимым условием существования решения этой системы является,
очевидно, следующее:

? N q Tq ? ? Wi = W .
q i


Покажем, что если wi = ?ai, i = 1, n , то это условие является достаточным.
Nq
x iq = a i ? Tq i = 1, n , q = 1, k .
Действительно, возьмем решение ,
A
Покажем, что это решение является допустимым. Имеем:

? x iq = N q Tq
i


ai Wi
? x iq ? N q Tq = W ? N q Tq ? Wi ,
=
A
q q q



? N q Tq ? W .
так как
q


Доказанное свойство позволяет предложить эффективный алгоритм
решения задачи. Сначала упорядочим все операции по убыванию
?i = Wi /ai. Все операции с одинаковыми ?i объединим в одну
величин
операцию с объемом, равным сумме объемов, и с величиной a, равной
сумме соответствующих ai. Пусть после такого преобразования осталось m
операций с различными значениями ?i, пронумерованными по убыванию
?i, то есть ?1 > ?2 > ... > ?m.

1 шаг. Рассматриваем первый интервал и распределяем ресурс в
объеме N1T1 так, чтобы максимально выровнять числа {?i}. Для этого
определяем l такое, что
l ?1

? a i < N1
i=1




27
l

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

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

ОГЛАВЛЕНИЕ

Следующая >>