<<
>>

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

Рассмотрим мультипроект из n независимых проектов. Каждый проект в агрегированном виде описывается как операция двумя характеристиками - объем проекта Wi и зависимость скорости реализации проекта Wi(t) = fi(ui(t)) от количества ресурсов Ui(t) в момент t.
Объем проекта, скорость и момент его завершения Ti связаны соотношением:

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.

Пусть fi(ui) = ui/(ui + a), i = 1-n. Уравнение (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.

Пусть wi = —^—, i = 1, n, T1 = 10, N1 = 25, N2 = 60, w1 =

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

Имеем ui= ji(wi) = wi1/a, hi(wi)=

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

n1a

X

-i=1

a

х/a

1

a iq

Nq

= Ta, q = 1,k

a

Назовем величину Xq = Ц x-q* 1 эквивалентным объемом работ в q-ом

i=1

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

X2q А

Рис. 2.1

0

Движение по этой траектории происходит со скоростью Nqa, а расстояние между двумя точками д^1 и ,xq2 равно:

iiX1q -

Г

x

iq

(<,x2q ) =

Как известно, кратчайшей траекторией, соединяющей любые две точки, является прямая, поэтому оптимальному распределению ресурсов соответствует прямая, соединяющая точку 0 с точкой xq.

Рассмотрим теперь фазовое пространство состояний всего комплекса операций. Аналогично случаю одного интервала, любому процессу выполнения операций соответствует кривая, соединяющая точку 0 с

точкой W, движение по которой происходит со скоростью Nqa, q = 1, k.

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

необходимо сначала найти минимальное k, такое, что

k

X Na- Tq < W3

q=1 k+1

У Na - T >W

/ * q q _ э •

q=1

Величина минимального времени реализации проекта определяется выражением:

k W -У Na - Tq

т .

=У т +— q"\'

mm / , q

N a

q=1 N k+1

Так как xiq = yqW., то x^ = yqWэ. Величина gq (это доля эквивалентного

объема, выполняемая в q-ом интервале) определяется выражением:

k

W,-УNa -Tq

k э L-i q q

T . =yT +—^

min Lu q XTa

q=1 N k+1

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

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

W„ =л/32 + 42 + 102 = 5л[5

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

= 2 - во втором, w^ = 3 - в третьем. Проверим возможность реализации проекта в третьем квартале.

w^-T, + w^T2 + w^T3 = Ь3 + 2-3 + 3-3 = 18 > W^ поэтому реализация проекта в третьем квартале возможна. Для более точной оценки определим

T 6 + Wэ - 9 6 + 5л/5 - 9 6 5

Tmin = 6 + = 6 + 1 »

3 3 6

Таким образом, мультипроект будет завершен в конце июля.

<< | >>
Источник: Бурков В.Н., Квон О.Ф., Цитович Л.А.. МОДЕЛИ И МЕТОДЫ МУЛЬТИПРОЕКТНОГО УПРАВЛЕНИЯ -М., 1997 (Препринт / Институт проблем управления). - 62 с.. 1997

Еще по теме 2. РАСПРЕДЕЛЕНИЕ РЕСУРСОВ ПО НЕЗАВИСИМЫМ ОПЕРАЦИЯМ:

- Инновационный менеджмент - Информационный менеджмент - Коммуникационный менеджмент - Кризисный менеджмент - Менеджмент предприятий - Основы менеджмента -
- Авторское право - Аграрное право - Адвокатура - Административное право - Административный процесс - Антимонопольно-конкурентное право - Арбитражный (хозяйственный) процесс - Аудит - Банковская система - Банковское право - Бизнес - Бухгалтерский учет - Вещное право - Государственное право и управление - Гражданское право и процесс - Денежное обращение, финансы и кредит - Деньги - Дипломатическое и консульское право - Договорное право - Жилищное право - Земельное право - Избирательное право - Инвестиционное право - Информационное право - Исполнительное производство - История - История государства и права - История политических и правовых учений - Конкурсное право - Конституционное право - Корпоративное право - Криминалистика - Криминология - Маркетинг - Медицинское право - Международное право - Менеджмент - Муниципальное право - Налоговое право - Наследственное право - Нотариат - Обязательственное право - Оперативно-розыскная деятельность - Права человека - Право зарубежных стран - Право социального обеспечения - Правоведение - Правоохранительная деятельность - Предпринимательское право - Семейное право - Страховое право - Судопроизводство - Таможенное право - Теория государства и права - Трудовое право - Уголовно-исполнительное право - Уголовное право - Уголовный процесс - Философия - Финансовое право - Хозяйственное право - Хозяйственный процесс - Экологическое право - Экономика - Ювенальное право - Юридическая деятельность - Юридическая техника - Юридические лица -