2. РАСПРЕДЕЛЕНИЕ РЕСУРСОВ ПО НЕЗАВИСИМЫМ ОПЕРАЦИЯМ

0

(2.1)

Пусть задана величина ресурсов N(t) на реализацию мультипроекта. Задача заключается в распределении этих ресурсов по отдельным операциям так, чтобы мультипроект был реализован за минимальное время T = max T;. В случае, если N(t)=N в любой момент времени

(равномерное поступление ресурсов во времени) и fi(Ui) - вогнутые функции ui, задача распределения ресурсов детально исследована [1, 2, 3]. Показано, что оптимальное распределение ресурса имеет следующие свойства:

а) каждая операция выполняется при постоянном уровне ресурсов ui(t) = ui, i = 1^n, te [0, T], а значит с постоянной скоростью;

б) все операции заканчиваются одновременно.

Если Т - момент завершения всех операций, то Wi = Wi/T постоянная скорость i-ой операции. Если обозначить через ji(wi) - функцию, обратную функции fi(ui), то ui = ji(Wi/T) определяет количество ресурсов, требуемое для завершения операции i за время T. Минимальное время T определяется теперь из уравнения

IfiI = N. (2.2)

i=1 4 t

Пример 1.1. Пусть fi(ui) = uia, 0 < a < 1, i = 1-n. Тогда ji(wi) = wi1/a Уравнение (1.2) примет вид:

I (W) a = N.

Решая это уравнение, получим:

Г n \\a

I Wi>a i=1

T ¦ =

min

N

Величина W, = ^iW^j называется эквивалентным объемом

мультипроекта. Действительно, мультипроект можно представить в виде одной операции объема W3 с такой же зависимостью f(u) = u1/a .

Пример 1.2.

вид:

" Wia

It-W = N

В данном случае для определения Tmin применяются численные методы. Для случая двух операций решение можно получить в аналитическом виде, решая уравнение

W, W2 N

1 - + -

T - W1 T - W2 a

Пусть N(t) - кусочно-постоянная функция времени, N(t) = Nk,

te[Tk-1,Tk), k = 1, p, T0 =0. Зафиксируем некоторые k и рассмотрим задачу о возможности реализации мультипроекта за время, не большее Tk. Обозначим xiq объем i-ой операции, выполняемой в интервале q. Очевидно, что

(2.3)

Z Xiq = Wi.

q=1

Поскольку в интервале [Tq-1, Tq) ресурсы поступают равномерно, то величины {xiq} в оптимальном решении связаны соотношением:

n Г X >

Z j i

iq

= Nq , q = 1,k - 1, Tq = Tq - T,_1

i=1 V Tq 0

а для последнего интервала имеет место следующее условие:

Z ji J= Nk, T = T - Tk-1

где T - время завершения всех операций.

Для получения необходимых условий оптимальности, применим метод множителей Лагранжа. Функция Лагранжа имеют вид:

x

Xiq V Tq 0

m k [ Z j il

X

ik

Xiq - Wi

n,

Nk

+

T 0

L = T-Zli Z

-11=1

i=1 V q=1

k-1 f n

+Zmq Zji

0 q=1 V ii=1

где 1i, mq - множители Лагранжа. Дифференцируя по Xiq, получим

Мч T

X

(v \\

iq

(2.4)

j i

q V Tq 0

= ^ i, q = 1,k:

при q = k, Tq = T.

Обозначим h, вектор, с компонентами hiq = ji\'(wiq), i = 1, n. Из (2.4) следует, что

hq = g qh1, , = 2,k , h1 ={hi }, g 1 = 1

то есть вектор h является в определенном смысле инвариантным во времени (его направление не меняется от интервала к интервалу, а меняется только его длина).

Разрешая уравнение hiq = ji\'(wiq) относительно wiq, получим

Wiq =Х i (hiq ) = X i(g q • hi) j i (wik) = j i [ i( g k • hi)].

uik =

Полученное свойство оптимального решения позволяет свести задачу распределения ресурсов к решению системы нелинейных уравнений с (n +

k) неизвестными {hi}, i = 1, n, {gq}, и T:

n

Xji[Xi(gq ¦ h)] = Nq , q = 1,k (2.5)

i=1

Xxi(gq ¦ hi)¦ Tq +xi(gk ¦ hi)¦ T = Wi, i = й. (2.6)

q=1

Операции мультипроекта будем называть однотипными, если wi = f(ui), то есть если все операции имеют одинаковые зависимости скорости от ресурса.

Пример 1.1.

u + 5

20, w2 = 26. Находим:

5w;

ui = j i(wi) = - — , i = 1,n

1 - w;

5

hi(wi) = ту , i = 1,n .

(1 - wi)

Заметим, что инвариантность по направлению вектора h эквивалентна в данном случае инвариантности по направлению вектора (1- w). Поэтому

(1 - w2 ) = g^(1 - w),

где через w обозначен вектор скоростей в первом интервале, а через g - значение gq во втором интервале.

Выпишем систему уравнений:

5w1 + JwL_ = 25

1 - w1 1 - w2

51 -gl1 - w1)) + 511 -Yl1 - w2 )) = 60 g(1 - w1 ) gl1 - w2 ) 10w1 + T[1 -g(1 - w1 )] = 20 10w2 + T[1 -g(1 - w2 )] = 26. Первые два уравнения после несложных преобразований

приводятся к виду:

= 7

11

+

1 - w1 1 - w2 1 1

+

(2.7)

= 14

g( - w1) g( - w2 ) Сразу получаем, что g =

Решая два последних уравнения относительно w1 и w2 получаем:

52 - T

40 - 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 + wn) = 0,75 ; w22 = /2(1 + w21) = 0,9 . Соответственно, оптимальное распределение ресурсов имеет вид:

5w

21

= 20;

= 5 ;

u

u

11

21

1 - w21

5w11

5w12 5w22

u12 = ^^ = 15 ; u22 = ^ = 45.

1 - w12 1 - w22

Предположим теперь, что функция X(g^h) является мультипликативной, то

есть

x(g^ h) = x 1 (g)^x2 (h).

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

{gq} и T:

n

Xji[gq ¦ wi] = Nq , q = 1,k (2.8)

i=1

k

Xgqwi ¦ Tq = Wi , i = 1,n. (2.9)

q=1

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

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

Пусть fi(ui) = uia, i = 1, n, 0