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

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

ОГЛАВЛЕНИЕ

Следующая >>

t1 u2 = t1 N ? ? 1?
? t1 ?

второго проекта, а в целом второй проект будет завершен в момент
2
?W ?
W2 ? t 1 N ? ? 1 ?
? t1 ?
t 2 = t1 + = t 1 + ? 2 ? t 1 ? ?1 ,
2 2

N
? 1 = W1 ? 2 = W2
где - минимальные продолжительности
N, N
проектов. Упущенная выгода составит


41
c 1 t 1 + c 2 t 2 = (c 1 + c 2 ) t 1 + c 2 ? 2 ? c 2 t 1 ? ? 1 .
2 2
(5.2)

Найдем t1, минимизирующее (5.2)
1+ ? c1
t1 = ? 1 , где ? = .
?(2 + ?) c2

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

[ ] ?
c1
c 2 ? 2 ? ?(2 + ?) + 1 , ? = , ?= 1 . (5.3)
?2
c2
Если первым заканчивается второй проект, то оптимальный момент его
завершения
1+ ?
t2 = ?2 ,
1 + 2?
а упущенная выгода:

[ ]
c2 ? 2 1 + 2? + ?? . (5.4)

Сравнивая (5.3) и (5.4) определяем
2? + 1 ? 1
?? = . (5.5)
?(2 + ?) ? ?

Окончательно получаем, что при ? < ?? в оптимальном решении сначала
завершится первый проект, а затем второй, а в случае ? > ?? наоборот,
сначала завершится второй проект, а затем первый. Если проекты
равноценны с точки зрения упущенной выгоды (?=1), то ?? = 1, и первым
завершится проект с меньшим объемом работ. Если проекты одинаковы по
объему (? = 1), то первым завершается более важный проект (то есть с
большей величиной ci).
Пример 5.2. Мультипроект состоит из двух проектов, объемы
которых W1 и W2, а скорости линейно зависят от количества ресурсов:
?u , u i ? a i
wi = ? i .
?a i , u i ? a i

42
Примем, что a1 + a2 > N, a1 ? N, a2 ? N, так что одновременно проекты
нельзя выполнить с максимальными скоростями. Пусть первым
завершается первый проект за минимальное время ?1 = W1/a1. За время ?1
будет выполнен объем работ (N - a1)?1 второго проекта. Оставшийся
объем работ W2 - (N - a1)?1 будет выполнен за время
W2 ? ( N ? a 1 )? 1
.
a2
Упущенная выгода составит
W ? ( N ? a 1 )? 1 ?
? ? ?? ?
c1 ? 1 + c 2 ? ? 1 + 2 = c 2 ? ?? 1 + ? 2 + 1 ? ,
? (5.6)
? а2 ?
? ?
a2

где ?1 = W1/a1, ?2 = W2/a2, ? = a1 + a2 - N, ? = c1/c2.
Если первым завершается второй проект, то упущенная выгода
составит
? ??
c 2 ? ?? 1 + ? 2 + ? ? 2 ? . (5.7)
? a1 ?

Сравнивая (5.6) и (5.7) получаем следующее решающее правило. Если
c1 c
> 2,
W1 W2
то первым завершается первый проект, в противном случае - второй.
Заметим, что если a1 = a2 = N, то проекты выполняются последовательно за
минимальные времена
?i = Wi/N. В этом случае получаем известную в теории расписаний задачу
определения оптимальной очередности выполнения операций на одном
рабочем месте. Решающее правило в этом случае естественно совпадает с
известным решающим правилом - упорядочение по убыванию отношения
ci/?i.
Обобщим рассмотренную в примере 5.2. линейную модель на случай
мультипроекта из n проектов. Пусть для любых двух проектов i, j имеет

43
место ai+aj >N. В этом случае одновременно с максимальной скоростью
может выполняться только один проект. Таким образом задача
заключается в выборе очередности проектов, которые будут выполняться с
максимальной скоростью. В примере 5.2. мы показали, что оптимальное
упорядочение для случая двух проектов - это упорядочение по убыванию
величин qi = ci/Wi. В данном случае упорядочивание проектов по
убыванию qi является эвристическим решающим правилом, во многих
случаях (как показывают численные примеры) дающем оптимальное
решение. Однако не всегда, что иллюстрирует следующий пример.
Пример 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.
1 2 3
i
100 15 20
ci
25 5 10
Wi
4 3 2
qi
5 5 1
ai
?i 5 1 10


а упущенная выгода
Ф = 100?5 + 15?6 + 20?10 = 790,

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




45
6. МЕТОДЫ АГРЕГИРОВАНИЯ
КОМПЛЕКСА ОПЕРАЦИЙ


Рассмотрим методы описания комплекса операций в виде одной
агрегированной операции. Для агрегированной операции необходимо
определить ее объем Wэ, который называется эквивалентным объемом
комплекса, и зависимость скорости агрегированной операции от
количества ресурсов на комплексе:
Wэ(t) = Fэ(N(t)) (6.1)

Определение. Агрегирование называется идеальным, если для любой
функции N(t) существует оптимальное распределение ресурсов {ui(t)} по
операциям комплекса, такое что
n

? u i (t ) ? N (t ) ,
i =1

а минимальная продолжительность комплекса удовлетворяет условию:
Tmin

? Fэ ( N( t))dt = Wэ .
0

Классическим примером идеального агрегирования является случай
степенных зависимостей скоростей операций от количества ресурсов:
f i ( u i ) = u ? , ? ? 1, i = 1, n . (6.2)
i

Действительно, в этом случае доказано что существует
([3]),
эквивалентный объем комплекса Wэ и зависимость
Fэ(N) = N?,
такие, что для любого уровня ресурсов N(t) имеет место
Tmin

? F[ N( t )]dt = Wэ .
0




46
При этом, существует оптимальное распределение ресурсов {ui0(t)}, такое
что
n
u 0 ( t) = N( t) ,
?i
i =1

а время выполнения комплекса равно Tmin.
Пусть N(t) = N при любом t. В этом случае распределение ресурсов
{ui0(t)} имеет следующие интересные свойства:
1. Каждая операция выполняется без перерывов постоянным
количеством ресурсов, то есть

[ ]
u 0 ( t) = u i , t ? t H , t 0 ,
i i i


где tiH, ti0 - моменты начала и окончания i-ой операции.
2. Ресурсы {ui} образуют поток по сетевому графику.
Существует интересная геометрическая интерпретация этого
результата.
Поставим в соответствие комплексу операций некоторую область m-
мерного фазового пространства. Эта область строится следующим
образом. Сначала находим минимальное множество путей, покрывающих
сетевой график, то есть таких, что кажая операция комплекса принадлежит
хотя бы одному пути. Для построения такого множества путей
необходимо определить минимальный поток в сети при условии, что
поток в каждой дуге (исключая фиктивные дуги, соответствующие
зависимостям)не меньше 1, применяя известные алгоритмы.
Пример 6.1. Пусть сеть имеет вид рис. 6.1 (зависимости показаны
пунктирными дугами)
Минимальный поток в данном случае, очевидно, равен
3.Соответствующие пути, покрывающие сеть:
µ1 = (0, 1, 3), µ2 = (0, 2, 3), µ3 = (0, 3).



47
1




3
0 2



Рис. 6.1.

Минимальное число r путей, покрывающее сеть, называется размерностью
комплекса операций. Поставим в соответствие каждому пути
координатную ось r-мерного фазового пространства. Построим в этом
пространстве область возможных состояний комплекса. Способ
построения показан на примере 6.1. На первой координатной оси
откладываем два отрезка, длины которых равны w01 и w12, то есть объемам
соответствующих операций, на второй координатной оси откладываем,
соответственно, отрезки длины w02 и w23, а на третьей - w03 (рис 6.2).
Теперь необходимо изобразить зависимость (1, 2), отражающую тот факт,
что операцию (2, 3) нельзя начинать, пока не закончена операция (0, 1).
Это значит, что запрещено находиться в параллелограмме, верхняя и
нижняя грани которого на рис. 6.2 закрашены. Область допустимых
состояний комплекса представляет собой параллелограмм 0ABC0’A’B’C’,
у которого вырезан параллелограмм DEFBD’E’F’B’. Точка 0 соответствует
начальному состоянию комплекса, точка С’ - конечному (все операции
выполнены). Любая монотонная траектория начало
(соединяющая
координат с точкой С’), проходящая в допустимой области, соответствует
некоторому процессу выполнения операций комплекса.




48
F’
B’ C’
X2

D’

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

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

ОГЛАВЛЕНИЕ

Следующая >>