Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 21.10.2024

Просмотров: 114

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

вычислим скорректированные значения максимально воз­ можных чисел комплектов по формуле

где [я] — целая часть от числа х ;

Pi— скорректированное значение максимального чис­ ла комплектов.

Для последующей итерации введем обозначения р *= рЛ

Итак, действия шага 6 являются завершающими для одной итерации. На этом шаге подготавливается информа­ ция, которая служит исходной для следующей итерации.

После завершения шага 6 имеем: новые значения объе­ мов работ Vi ; уровни ресурсов Rj(tk ); пересчитанные вели­ чины Щ и р{ ; новый исходный граф, который получается в результате удаления вершин i, соответствующих закончен­ ным работам, и дуг, выходящих из них на графе, являвшем­ ся исходным на предыдущей итерации.

С помощью вычисленных величин Vi, рг, H t устанавли­ ваем кратчайшую продолжительность выполнения остав­ шихся работ по формуле (5.20), т. е.

____ Vi

§ 5. СИНТЕЗ СЕТЕВОГО ГРАФА ПРИ ПЕРЕМЕННЫХ УРОВНЯХ НЕСКОЛЬКИХ ВИДОВ НЕСКЛАДИРУЕМЫХ РЕСУРСОВ

С РАЗЛИЧНЫМИ ТИПАМИ ПОТРЕБЛЯЕМЫХ КОМПЛЕКТОВ

Рассмотрим задачу синтеза сетевого графа, которая от­ личается от аналогичной задачи, описанной в четвертом параграфе главы V. Основное отличие в формулировке — то, что одной работе поставлено в соответствие несколько возможных типов совокупности чисел Sij, т. е. комплектов. Например, для работы i= 1 запишем эти совокупности в виде

12 » *

*

* »

 

12» ’

*

•»

(5.49)

123

Обозначим через Sfj элемент одного из возможных ком­

плектов для работы i относительно j-го вида ресурсов. Ин­ декс g для каждой работы принимает свое значение:

1 = 1 , * = 1 , 2 , . . . ,7(1)

i = 2, g — 1, 2, . . . , 2(2)

i = N , g = 1 , 2 , . . . , 7(2V)

Считается, что каждому типу комплекта поставлены в соответствие величины р£ и H tg.

Алгоритм решения сформулированной задачи основы­ вается на алгоритме задачи, рассмотренной в четвертом па­ раграфе данной главы. Отличие заключается в том, что при распределении ресурсов по работам фронта происходит вы­ бор не только величины комплекта rit но и типа комплекта из перечня (5.50).

Предполагается, что относительно каждой работы мож­ но найти такой комплект, для которого произведение р максимально, т. е.

т а х р ^ .Я ^ = р £° .# А р

(5. 51)

l<g <I(i)

Соответствующие элементы комплекта обозначим через S°ij. Поэтому на каждой итерации кратчайшее время выпол­ нения работы будем вычислять по формуле

Vi

(5.52)

t.i0 Pi*- Hi о *

Шаг 1. Построение текущего сетевого графа. Приняв вре­ менные оценки работ, найденные по формуле (5.52), синте­ зируем оптимальный сетевой граф G(Xl, U1). Все действия шага 1 полностью совпадают с действиями шага 1, рассмот­ ренными в четвертом параграфе.

Шаги 2, 3 и 4 аналогичны соответственно шагам 2, 3 и 4, описанным в четвертом параграфе.

Шаг 5. Выбор типов комплектов и вычисление величин комплектов используемых ресурсов, определение продолжи­ тельности фронта.

Разбиение на группы П\, П2, . . . , Tlq производится так же, как в шаге 5, изложенном в четвертом параграфе. Рас­ смотрим снова случаи 1— 4.

Случай 1 .

 

2 Pi°-Я °у = Л ;(Я ,), К -1 ,2 , . . . , М ;

(5.53)

ienp

 

124


9

 

(5.54)

2 R j ( n p)K R j(t), 7=1, 2, . .

M .

P=1

 

 

Условие (5.54) означает, что любая работа фронта может быть выполнена комплектом рг°, при этом в единицу време­ ни производится Hi0 объема работы L

Продолжительность фронта находим по формуле

0 = min{ai; a2},

(5.55)

где a i= t* — t;

a2= m in

Vi

Pi0-H i0

iGF(t)

Переходим к шагу 6.

Случай 2. Пусть для работ группы Z7i выполняется нера­ венство

 

Д ;№ ) =

2

Pi0S0i;>-Bj(t).

 

(5.56)

 

 

 

iQIl\

 

 

 

Предварительно выделим для каждой

работы

группы

П\ комплекты

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(5.57)

где [я] — целая часть от числа х.

формулы (5.25)— (5.29)

Для определения г*° применяем

относительно рг° и S°ij. Вычисляем остаток ресурсов:

 

 

2

n°*S0ij,

7=1,

2..............М .

(5.58)

 

i6 Н1

 

 

 

 

 

 

Находим работу k, для которой

 

 

 

шах

V j-n W j° .

т*

V k-rk°H

+ L h*.

(5.59)

iQlli

?i°Hf>

^

1

 

P°fe

 

 

Постараемся распаковать

комплекты

rk° для работы k

и назначить для нее новые величины комплектов, исполь­ зуя остаток ресурсов и заданные типы комплектов. Для это­ го проверяем неравенство

шах \Hkg

min

Rj'+rko-S°kj >г*°.Я *°. (5.60)

l < g < I ( k ) {

j

S%

Пусть неравенство (5.60) выполняется для g(k)-ro типа

125


комплектов относительно работы k. Тогда работе k назнача­ ем g(k)-й тип комплекта, величина которого равна

rg(k)~

 

■й/г+г*°* S°kj

\

 

min

W’

)

(5.61)

k

 

}

 

С учетом новой величины r|(ft) для работы k находим но­

вый остаток ресурсов Rj2 и снова рассматриваем формулу (5.59). Затем проверяем неравенство (5.60). Если оно не со­ блюдается, то в левой части выражения (5.59) отыскиваем вторую максимальную величину.

Если для всех работ группы П\ неравенство (5.60) не удовлетворяется, то перераспределение типов и величин ком­ плектов заканчивается и переходим к шагу 6.

Продолжительность фронта равна

0 = [min {си, <х2, а3}],

где (Xi= ta t;

Vi

02=min

ieF(f) riS'Hi8

a3 = At2— резерв времени работ группы Z72.

Если фронт состоит только из работ группы 27ь то а3= = оо. Переходим к шагу 6.

Случай 3. Пусть для работ групп П ь П2, . . . , Ilq—i на­ значены максимальные комплекты рД для которых выпол­ няются условия (5.51).

Остаток ресурсов

д—1

(7 = 1 .2 , . . . , М )

р=1

распределяем по работам последней группы П д так же, как и в случае 2 для группы П\.

Продолжительность фронта

 

 

 

 

0 =

[min{си, а2, а3}],

 

где а1= т Аг—

 

 

 

 

 

02= m in

Vt

g при

iGlT^ П 2 , . . . , Z7g_i и

рД

g

ieF(t)

ri

'n i

 

 

 

Значение a3 выводим из выражений

(H°^l°-rt8.Ht8)ai3= д ^ ,

р

126


ai8

?1ощо_г.ё.щд ' *

(5 .6 2 )

a3=m in(ai3). iei73

Переходим к шагу 6.

Случай 4. Пусть по работам групп П\, Пч, . . . » П т—\рас­ пределены комплекты р°. Для работ группы Пт остаток ре­ сурсов недостаточен, чтобы назначить р*°. Работы групп П т-ы » П т+2, . . . , П g не выполняются, и начала их отодвига­ ются.

Остаток ресурсов

R fi) - 2 R j W ^ R j 1

Р= 1

по работам группы 27т“ распределяем, как и в случае 2. Про­ должительность фронта вычисляем по формуле

0 = [min{ai, a2, a3, a4}],

где a i= T k — t;

«2= m in

, Ylj g при гб n v П 2, • • •, П т - 1 и

pt°.

iGF(t)

r i

 

Относительно аз составим соотношение для работ груп­ пы Пт:

откуда

tem— Мт~г

Тогда

 

a3= m in {ai3}.

(5.63)

ienm

Величину a4 определяем из соотношения

Mm+1— a4 = tem— a4 ^1—min \ ienm

откуда

127

СГ.л=

Atm + 1 — At т

(5.64)

min

Tie 'Hie

 

 

 

?i9.Hi0

 

Переходим к шагу 6.

Шаг 6. Нахождение объема, новой величины максималь­

ного комплекта, H tg и

минимальной продолжительности

оставшейся части работ.

 

Оставшуюся часть объема работ фронта

подсчитываем

по формуле

 

V ^ V t - r ^ H f - e ,

(5.65)

где гIs— значение комплекта, вычисленное на шаге 5. Вычислим сумму продолжительностей фронтов:

?A= 0 o-r0i4 - . . . — —1,

(5.66)

где ©0 = 0, ©s — продолжительность фронта s-й итерации. Обозначим оставшуюся часть объема снова через Vi.

Пусть выполняется неравенство

Vi<iHig при g = g lf g2, • • •, Sk>

(5.67)

тогда значения H f для (5.67) принимаются равными V г.

Зная tk, по формуле (5.19) находим

уровень

ресурсов

на основе чего определяем новое

значение макси­

мального комплекта каждого типа g :

 

 

Rj(tk)

 

(5.68)

min ~S¥iT

 

где [x ] — целая часть от числа х ;

р.^— скорректированное значение максимального ком­ плекта типа g для работы L

Таким образом, подготовлена исходная информация для следующей итерации. Остальные действия шага 6 полностью совпадают с действиями шага 6, описанными в четвертом параграфе.


Г л а в а VI

АВТОМАТИЗАЦИЯ ПРОЦЕССА СИНТЕЗА ОПТИМАЛЬНОГО СЕТЕВОГО ГРАФА

Ранее мы рассматривали вопросы синтеза сетевого гра­ фа, в частности алгоритм построения оптимального сетево­ го графа с минимальным значением критического пути, ме­ тоды распределения складируемых и нескладируемых ре­ сурсов на графе переменной топологии.

Алгоритм решения задачи не исчерпывает полностью проблемы отыскания наилучшего варианта решения. Сле­ дует всегда помнить об объеме проводимых вычислений. Он может оказаться таким большим, что затрачиваемое на вычисления время сделает полученную информацию прак­ тически бесполезной из-за ее «старения». Поэтому для ра­ дикального решения проблемы оптимизации кроме алго­ ритма отыскания оптимального варианта требуются еще и средства, реализующие этот алгоритм. В качестве таких средств успешно применяются ЭВМ. Их использование це­ лесообразно при решении задач больших размеров. Ниже излагаются алгоритмы реализации на ЭВМ «Минск-22» всех задач, поставленных в третьей, четвертой и пятой главах.

§ 1. АВТОМАТИЗАЦИЯ ПРОЦЕССА ПОДГОТОВКИ ИСХОДНОЙ ИНФОРМАЦИИ

Для реализации любой задачи на ЭВМ прежде всего сле­ дует выбрать способ задания (кодировку) исходной инфор­ мации, используемой в процессе решения. Как указывалось ранее, исходная сетевая модель представлена графом с пол­ ными контурами.

Условимся изображать граф на языке «работа — связь». При таком способе задания вершины графа i будем считать работами, а дуги иц графа — допустимыми связями между заданными работами i и у. Обозначим через продолжи­ тельность г-й работы (вершины графа). Тогда связь (дуга и )

9 -9 1

129