Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2024
Просмотров: 115
Скачиваний: 0
Предположим, что это неравенство справедливо хотя бы для одного вида ресурсов.
Вычислим коэффициенты б; для всех j :
Л |
Rj{t) |
(5.25) |
8j = |
щ , j = 1, 2, . . , , М . |
Постараемся имеющиеся в наличии ресурсы каждого вида распределить по работам группы П\ пропорционально про изведению рi'Siji
C ij= b y ? r S u |
|
|
(2=1, 2, . . . , IV, |
у = 1, 2, . . . , М). |
(5.26) |
Так как количество ресурсов j, |
расходуемых на |
работе г, |
входит в комплект через S y , то возможное число комплек тов для работы i относительно каждого вида ресурсов опре
деляется как |
j |
Сц_ |
(5.27) |
Pi * |
|
Si j |
|
Ввиду того, что для выполнения работы i требуется одно временное использование нескольких видов ресурсов через совокупность элементов S^, Si2 , . . . » Sim » то возможное число комплектов, которое можно образовать из ресурсов, выделенных пропорционально бj и pj, равно
min (—i ] = |
min(Pi •%j)=Pi • |
(5.28) |
j \Sij j |
j |
|
Следовательно, для работы i наиболее дефицитными явля ются ресурсы вида I.
Заметим, что элементы Sy = 0 в формулах (5.26)— (5.28) не учитываются. Принимая во внимание, что число комплек тов — целое, окончательно получаем
П=[ргЭД, |
(5.29) |
где [я] — целая часть числа х. При этом может быть недо использована часть ресурсов (сумма дробных частей в вы ражении (5.28). Постараемся дораспределить эти ресурсы.
Найдем остаток ресурсов:
R]4t)=Rj(t) - 2 гГ Sij 0 '= 1 , 2, . . |
М). (5.30) |
ieiii |
|
Выберем такую работу к, которой можно дополнительно на значить один комплект, т. е. Arft = l. В качестве работы к возьмем ту, для которой выполняется условие
118
(Vi |
riHi | f |
Vk |
TkHk | y 4c |
/ с o i \ |
? ea„ f (“ |
s s t " + L l ) - |
w |
+ L * ■ |
(5-31) |
Здесь L*k— продолжительность максимального пути от fe-й работы до мажоранты.
Комплект работы к увеличивается на единицу, если од новременно соблюдаются неравенства
Skj<Rj4t), 7= 1, 2, . . . , М
(5.32)
гk1=rkJr&rk=:rkJrl^Pk
Если хотя бы одно из неравенств (5.32) нарушается, то вы бираем следующую работу по формуле (5.31), за исключе нием i= k.
Пусть неравенства (5.32) удовлетворяются, тогда скор ректированные значения комплектов обозначим снова через
rt и найдем второй остаток: |
|
s , 4 t ) - 2 г>■S,j=Sf(t). |
(5.33) |
ien, |
|
Относительно R 2(t) опять производим описанные дейст вия.
Величина, определяемая по формуле (5.31), означает кратчайшее время выполнения оставшейся части объема ра боты к. Чем больше эта продолжительность, тем больше дли на критического пути, так как резерв времени Д£1= 0. По этому назначением дополнительного комплекта мы стараем ся уменьшить продолжительность оставшейся части работы. Продолжительность фронта во втором случае вычисляется так:
© = |
[min{ai, |
а2, cu}]. |
|
(5.34) |
Здесь сц= At2— резерв |
времени |
группы |
П2 фронта. |
Если |
фронт состоит только из работ группы П\, то <Х4 принимает ся равной оо. Величины ai и а2 определяются, как в случае 1.
Переходим к шагу 6. |
/7Ь П2, . . . » |
на |
Случай 3. Пусть для работ групп |
||
значены максимальные комплекты р*. |
Для работ последней |
|
группы нельзя распределить комплекты, равные р*. |
Вычи |
|
слим остаток ресурсов для работ группы Я д: |
|
|
ч—1 |
2, . . . , М). |
(5.35) |
R M - 2 Л Д Я ,)= В ,1({)> ° 0 = 1 , |
||
Р=1 |
|
|
119
Остаток ресурсов -R /(0 распределяем по работам группы JJq так же, как и в случае 2 для работ группы П\.
Продолжительность фронта находим по формуле
© = [min{ab a2, a3}], |
(5.36) |
где
ai= 4 —t;
Vi
a2= m in — =£- при i e n x, П 2, . . . , П х и rt= p £.
ieF(t) ' 1Я 1
Величину a3 вычисляем следующим образом. Если бы ра ботам группы n q не были выделены ресурсы, то максималь но возможная величина 0 составляла бы At q, так как после этого отрезка времени резерв времени работ группы Пд ста новится равным нулю. Но так как, согласно (5.35), остаток -ft/1 ( 0 0 и часть объема работ группы Пд могут быть выпол нены, то продолжительность фронта можно увеличить. Обо значим через a i3 тот отрезок времени, по истечении которо го резерв времени работ группы Пд станет равным нулю:
(рjHj FjHi)tXi3 _ |
(5.37) |
||
PiHi |
~ |
||
|
|||
Отсюда |
|
|
|
Ш |
|
(5.38) |
|
|
|
||
Теперь а3 определим как |
|
|
|
a3=m in{ai3}, |
(5.39) |
||
iGIIg |
|
|
|
после чего переходим к шагу 6. |
|
Пт—Х задано |
|
Случай 4. Пусть работам групп П\, Пч, . . . , |
|||
максимально возможное число комплектов р*. Для работ группы Пт остаток ресурсов недостаточен, чтобы назначить
Pi » |
т . |
|
|
|
Остаток ресурсов |
|
|
|
ш—1 |
|
|
|
Rj(t) - 2 |
B j(n p)=RjKt) |
(5.40) |
|
Р = |
1 |
|
распределяем по работам группы Пт аналогично действиям, описанным в случае 2 .
120
Работы групп Пт+1, П т+2, . . . , 27? не начинаются в дан ный момент t, и начала их отодвигаются. Продолжитель ность фронта и укажет тот отрезок времени, на который ото двигаются начала работ указанных групп.
Продолжительность фронта вычисляем по формуле
|
в = min{(Xi, а2, а3, а4}, |
(5.41) |
где |
& i= 4—t; |
|
у. |
для iG lI lt JI2, . . . , П т- г и г*=р*. |
|
a2= m in —-jz- |
|
iQF(t) rin i
Объясним сущность величин а3 и а4. а3 показывает тот отрезок времени, по истечении которого сравняются резер вы времени работ групп Пщ—х и II т , так как работы группы П т выполняются с меньшим числом комплектов, чем р*.
Составим соотношение для работ группы П т:
Д ,)аи =(Д *“ - Д Г - 1) •рtH it
откуда
а£3 = |
Pi#i-rtHi |
ИЛИ |
|
|
A t m — A t m ~ l |
В качестве a3 примем минимальную из ai3 , т. е.
a3=min(ai3) = |
min ' A t m — A tm ~ l |
J |
|
ien m |
iGIlm |
||
|
Это выражение перепишем в виде
A t m — А *771-1
«3 =
1—min
i6X7m' Pi
Для определения 04 составим соотношение
A£m+1—a4—Д£т —a4( l —min j — 1).
i e n m l Pi J
(5.42)
(5.43)
(5.44)
121
Здесь а4— отрезок времени, по истечении которого резервы времени работ групп П т + 1 и Пт с учетом гг^ 0, срав няются. Так как часть объема работ группы П т выполня ется, то резерв времени этой группы за отрезок сц уменыпа-
ется на величину 04(1 — m in— ).
^пт Н
Из выражения (5.44) находим
Atm+1—Atm |
(5.45) |
|
а4 |
П_ |
|
min |
|
|
пт Pi |
|
|
и переходим к шагу 6. |
минимальной продолжи |
|
Шаг 6. Установление объема, |
||
тельности и новой величины максимального комплекта для оставшейся части работ. Продолжительность фронта озна чает тот отрезок времени, в течение которого каждая рабо та фронта F(t) будет осуществляться с постоянным исполь зованием комплекта, равного Если для некоторых работ группы 74=0, то это говорит о том, что начало работ отодвигается на величину продолжительности фронта 0. В результате потребления ресурсов в количестве гг >>0 комп лектов объемы работ фронта уменьшатся. Оставшуюся часть объема подсчитываем по формуле
V t'^ V t - r tH r Q , |
(5.46) |
где V/ — оставшаяся часть объема работы I;
Vi— объем работы i перед рассматриваемым фронтом; 0 — продолжительность фронта.
Если Т У = 0, то работа i завершена. В исходном графе G0(X, U) удаляем вершину i вместе с выходящими из нее ду гами.
Определяем момент начала следующего фронта (следу
ющей итерации k): |
|
|
tk— |
1» |
(5.47) |
где 0 о = О, 0S — продолжительность фронта на s-й итерации. Зная величину £*, находим уровень ресурсов Rj(tk ). С по мощью tki V i и Hi пересчитываем максимально возможное число комплектов для каждой работы.
Пусть имеется неравенство
V i '< H t. |
(5.48) |
Тогда Hi принимаем равным V /.
Найдя по формуле (5.19) уровень ресурсов в момент tk,
122