5. МИНИМИЗАЦИЯ УПУЩЕННОЙ ВЫГОДЫ

n

i=1

(5.1)

Рассмотрим задачу распределения ресурсов по проектам таким образом, чтобы минимизировать (5.1), то есть упущенную выгоду.

Пример 5.1. Пусть мультипроект состоит из двух проектов, объемы

которых W1 и W2, а скорости - w1 = д/й^ и w2 = л/й^. Если первый проект

второго проекта, а в целом второй проект будет завершен в момент

завершается в момент t1, то й1 = (W^t1)2, й2 = N -(W^t1)2. За время t1 будет выполнен объем работ

2 1 ,

Vn

где t1 = W^VN, 12 = W2/VN - минимальные продолжительности проектов. Упущенная выгода составит

Cltl + C2^2 =(C1 + C2 )tl + C212 - CWt2 -t2 • (5-2)

Найдем tb минимизирующее (5.2)

t 1 + P P Ci

ti = i , 4ti, где P = -k

/P(2 + P) C2

При этой величине t1 упущенная выгода равна

C2 ^ 2

^л/Р(2 + P) +1, P = —, g = — • (5.3)

C2 ^ 2

Если первым заканчивается второй проект, то оптимальный момент его завершения

t2 = п zrpr 12,

1+ P

а упущенная выгода:

C2 ^ 2

yr+2b + Yp] • (5.4) Сравнивая (5.3) и (5.4) определяем

* J2P +1 -1 , ч

g* = У-^г -. (5.5) P(2 + P)-P

Окончательно получаем, что при g < g* в оптимальном решении сначала завершится первый проект, а затем второй, а в случае g > g* наоборот, сначала завершится второй проект, а затем первый.

Пример 5.2. Мультипроект состоит из двух проектов, объемы которых W1 и W2, а скорости линейно зависят от количества ресурсов:

ui, u; < a;

w; ¦

a;, u; < a;

Примем, что a1 + a2 > N, a1 < N, a2 < N, так что одновременно проекты нельзя выполнить с максимальными скоростями. Пусть первым завершается первый проект за минимальное время t1 = W1/a1. За время t1 будет выполнен объем работ (N - a1)t1 второго проекта. Оставшийся объем работ W2 - (N - a1)t1 будет выполнен за время

W2-(N - a1 )t1

a

Упущенная выгода составит

At 1

а 2 0

pt 1 +T 2 +

(5.6)

W2 -(N - a1 )t 1\'

С1 t 1 + С2

= c2

11 +

a2

где i1 = W1/a1, i2 = W2/a2, A = a1 + a2 - N, P = c1/c2.

Если первым завершается второй проект, то упущенная выгода составит

(5.7)

c

pt 1 +t 2 +P — 12 a1 0

Сравнивая (5.6) и (5.7) получаем следующее решающее правило. Если

c

c

—^ > —, W1 W2

то первым завершается первый проект, в противном случае - второй. Заметим, что если a1 = a2 = N, то проекты выполняются последовательно за минимальные времена

ti = Wi/N. В этом случае получаем известную в теории расписаний задачу определения оптимальной очередности выполнения операций на одном рабочем месте. Решающее правило в этом случае естественно совпадает с известным решающим правилом - упорядочение по убыванию отношения Ci/ti.

Обобщим рассмотренную в примере 5.2. линейную модель на случай мультипроекта из n проектов. Пусть для любых двух проектов i, j имеет

место ai+aj >N. В этом случае одновременно с максимальной скоростью может выполняться только один проект. Таким образом задача заключается в выборе очередности проектов, которые будут выполняться с максимальной скоростью.

Пример 5.3. Мультипроект состоит из трех проектов, данные о которых приведены в таблице 5.1

Пусть количество ресурса N = 6. Упорядочим проект по убыванию qi следующим образом: 1®2®3. Первый и второй проекты завершаются в срок t1 = t2 = 5, а третий - в срок t3 = 15. Упущенная выгода Ф = 100-5 + 15-5 + 20-15 = 875. В то же время, если сначала выполнять проекты 1 и 3, а после завершения проекта 1 начать проект 2, то моменты завершения проектов

t1 =5, t2 = 6, t3 = 10,

Таблица 5.1.\r\ni 1 2 3\r\nCi 100 15 20\r\nW 25 5 10\r\nqi 4 3 2\r\n 5 5 1\r\nti 5 1 10\r\n1. а упущенная выгода

Ф = 100-5 + 15-6 + 20-10 = 790,

что меньше, чем в предыдущем случае.