Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.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°Hkо |
+ 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 |