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

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

ОГЛАВЛЕНИЕ

Следующая >>

1 шаг. Начинаем операцию 6, имеющую максимальную степень
критичности. Однако, через ? = 1 степени критичности операций 3 и 6
сравниваются, поэтому распределяем ресурс по операциям 3 и 6:
2 4
u3 = ; u6 = .
3 3
Имеем:
2 4 1
x31 = , x61 = 2 + = 3 .
3 3 3

34
2 шаг. Выполняем все проекты с максимальной скоростью. Имеем:
x 12 = 6, x 22 = 9, x 32 = 3, x 42 = 3, x 52 = 9, x 62 = 6 .
˜
N 3 = 11, то все проекты выполняются с
3 шаг. Поскольку
максимальной скоростью wi = ai, кроме проекта 5, для которого u5 = 2.
Полностью завершаются проекты 1, 2 и 5. Поэтому образуется избыток
ресурса в объеме 8 ед., который переносим в четвертый период, увеличив
˜
N4 до N 4 = 8 .
4 шаг. В четвертом периоде также избыток ресурсов, поскольку не
выполнены только проекты 3, 4 и 6. Время завершения комплекса равно
3
1 1
Tзав = ? Tk + 1 = 9
3 3
k =1

и определяется моментами окончания 3-го и 6-го проектов.




35
4. МИНИМИЗАЦИЯ ПРОДОЛЖИТЕЛЬНОСТИ
МУЛЬТИПРОЕКТА. Общий случай


В предыдущих разделах мы рассмотрели задачу минимизации
продолжительности мультипроекта для случая вогнутых зависимостей
скорости проекта от количества ресурсов. Рассмотрим теперь общий
случай.
Пусть fi(ui) - произвольные, ограниченные, непрерывные справа
функции, такие что fi(0) = 0. Определим множество Y - пар (u, w) -
следующим образом:
Yi = {( u i , w i ) > 0: w i ? f i ( u i )} . (4.1)

Заметим, что если fi(ui) - вогнутая функция, то Yi - выпуклое множество. В
общем случае множество Yi не является выпуклым. Построим выпуклую
˜
оболочку этого множества, то есть выпуклое множество Yi такое, что
любая его точка представима в виде выпуклой линейной комбинации
точек множества Yi. Граница fi ( u i ) этого множества, очевидно, является
˜

вогнутой функцией. Рассмотрим задачу минимизации продолжительности
мультипроекта, в котором скорости проектов определяются
зависимостями { fi ( u i ) }. Поскольку это вогнутые функции, то применяя
˜

методы, описанные в разделах 2 и 3, можно определить оптимальное
распределение ресурсов {ui0} и минимальную продолжительность Tm
мультипроекта.
Теорема 2. Минимальная продолжительность мультипроекта равна
Tm.
Доказательство. Ранее было показано, что в случае вогнутых
зависимостей {fi(ui)} в каждом интервале постоянства уровня ресурсов, все


36
проекты выполняются с постоянной скоростью. Обозначим w0 -
ik

скорость, u 0 - количество ресурсов на i-ом проекте в k-ом интервале.
ik

Поскольку точка { u 0 , w 0 } ? Yi, то найдутся точки { u 1 , w 1 }, { u 2 ,
ik ik ik ik ik


и
w2 }
ik

0 ? ? ? 1, u 1 ? u 2 , такие что
ik ik


u 0 = ?u1 + (1 ? ? )u ik
2
ik ik


w 0 = ?w 1 + (1 ? ? )w ik .
2
ik ik

Построим следующее распределение ресурса на проекте i в
интервале k:
?u 1 , ? k ?1 ? t < ? k ?1 + ?Tk
?
u ik ( t ) = ? ik . (4.2)
?u ik , ? k ?1 + ?Tk ? t < ? k
2
?
Содержательно это означает, что часть ?Tk интервала k проект
выполняется с количеством ресурса u 1 , меньшим оптимального, а часть
ik

(1-?)Tk - с б’ольшим оптимального. При этом, не израсходованный в
интервале [?k-1, ?k-1+?Tk) ресурс переносится в интервал [?k-1+?Tk, ?k), так
что общий объем используемого ресурса не меняется. Действительно,
u1 ? ?Tk + u ik ? (1 ? ? )Tk = u ik ? Tk .
2 0
ik

Таким образом, распределение ресурса ui k(t) является допустимым.
Покажем, что при новом распределении ресурсов в интервале k
будет выполнен тот же самый объем работ по проекту i. Действительно:
w 1 ? ?Tk + w ik ? (1 ? ? )Tk = w ik ? Tk .
2 0
ik


Выполняя описанное преобразование всякий раз, когда точка ( u 0 , w 0 ) не
ik ik

принадлежит множеству Yi, мы получили допустимое распределение
ресурсов с тем же сроком завершения мультипроекта. Поскольку Tm



37
является оценкой снизу продолжительности мультипроекта, то Tm -
минимальная продолжительность мультипроекта. Теорема доказана.
Пример 4.1. Пусть зависимости скорости проекта от количества
ресурсов являются выпуклыми функциями при ui ? ai и равны fi(ai) при ui ?
ai (рис. 4.1).


w
a1



f ( u)
˜




ai u
Рис. 4.1.
В этом случае зависимость fi ( u i ) всегда будет иметь вид:
˜

?u i , u i ? a i wa
fi ( u i ) = ?
˜
, при объеме w i = i i .
˜
?a i , u i ? a i f i (a i )

Мы получили задачу распределения ресурсов для случая линейной
зависимости скорости от количества ресурсов, рассмотренную в разделе 1.
Таким образом, в этом случае всегда существует план реализации
˜
мультипроекта, в котором каждый проект выполняется за время ?i = W i /ai
при уровне ресурсов на нем ui = ai. Продолжительность мультипроекта в
случае, если уровень ресурсов постоянен и равен N определяется
выражением:
?W ?
Tm = max ? э ; max ? i ? ,
?N ?
i




38
n
˜
где Wэ = ? Wi . При этом, всегда существует план, в котором все проекты
i =1

выполняются без перерывов. Чтобы получить такой план, достаточно
определить моменты начала проектов следующим образом:
t iH = Tm ? ? i , i = 1, n .
Если теперь сдвигать проекты максимально влево в очередности убывания
степеней критичности {?i}, то получим левосдвинутый оптимальный план
реализации мультипроекта.
Пример 3.1. Данные о проектах приведены в таблице:
Таблица 3.1.
1 2 3 4 5
i
12 15 18 12 9
Wi
2 3 4 3 6
ai
?i 6 5 4,5 4 1,5




12


9




1,5 4,5 5 6 t
Рис. 4.2. 5
5


Пусть N = 11. Тогда

39
Wэ 66
Tm = = = 6.
N 11


Мы можем начать проекты 1, 2 и 3 сразу, в момент t = 0. Определим самый
ранний момент начала проекта 4. Для этого построим интегральный
график наличия свободного ресурса при условии, что проекты 1, 2 и 3
начинаются в момент t0, а проект 5 в момент t = 4,5 ( рис. 4.2). Этот ресурс
можно использовать для проекта 4.
Закрашенный треугольник это график использования ресурса на
проекте 4. Легко видеть, что сдвиг влево этого треугольника невозможен.
Аналогично пятый проект также не может быть начат раньше момента
t5н = 4,5.




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


До сих пор мы рассматривали задачу минимизации
продолжительности мультипроекта, то есть завершения всех проектов за
минимальное время. Однако, не менее важна другая задача. Дело в том,
что каждый проект после его завершения дает фирме определенный доход.
Задержка в сроках реализации проектов ведет к уменьшению дохода
(Упущенной выгоде). Пусть i-ый проект дает после завершения доход ci в
единицу времени. Тогда упущенная выгода при завершении i-го проекта в
момент ti составит citi, а суммарная упущенная выгода равна
n
C = ? ci t i . (5.1)
i =1

Рассмотрим задачу распределения ресурсов по проектам таким
образом, чтобы минимизировать (5.1), то есть упущенную выгоду.
Пример 5.1. Пусть мультипроект состоит из двух проектов, объемы
которых W1 и W2, а скорости - w 1 = u 1 и w 2 = u 2 . Если первый проект

завершается в момент t1, то u1 = (W1 t 1 ) , u 2 = N ? ( W1 t 1 ) . За время t1
2
2



будет выполнен объем работ
2
?W ?

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

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

ОГЛАВЛЕНИЕ

Следующая >>