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

На основании диаграммы D\строим график Г\ (рис. 5.4) потребления ресурсов в течение промежутка (О, Т), где Т — продолжительность критического пути на графе G(XX, Г/1), полученном на шаге 1. Жирной линией на графике показан наличный уровень нескладируемых ресурсов R(t), который

для нашего примера постоянен и равен R = 10 в любой мо­ мент времени t. Как видно из рисунка, потребление ресур­ сов на работах графа различно: на некоторых отрезках, например (4, 12) и (16, 17), оно превышает заданный уровень 1 0 , а в отдельные моменты времени суммарная интенсив­ ность используемых ресурсов ниже заданного уровня. Если в течение всего времени (0, Т) для работ графа G(XX, IIх) сум­ марная интенсивность 2 рг в каждый момент времени не превышает уровня -R(£), то построенный на шаге 1 граф бу­ дет искомым. В противном случае, при Ир* > Д (?) анализи­ руются последующие шаги.

Шаг 3. Определение фронта работ F(t). Фиксируем рабо­ ты, у которых совпадают значения ранних начал £рн. Эти ра­ боты образуют максимальный фронт F(t). Максимальный фронт работ отыскиваем на графе (рис. 5.2), полученном на первом шаге рассматриваемой итерации. На первой итера­ ции t = 0 .

В нашем примере в момент времени t = 0 ранние нача­ ла t? H работ i= 1, 2 и 3 совпадают и равны нулю (рис. 5.3).

Следовательно, максимальный фронт F(0) состоит из работ

1 , 2 и 3.

Шаг 4. Вычисление резерва времени работ фронта F(t). Резерв времени Att для любой l-й работы фронта F(t) в мо­ мент времени t рассчитываем по формула

92

где t/ и t / — продолжительность невыполненной к моменту

G(Xl, U1), определяемая по общеизвестному правилу поиска максимальных путей.

Вычислим резервы времени для работ фронта F(0) отно­ сительно графа G(Xl, U1) (рис. 5.2). Найдем предварительно

L0=niax{L ! -(-£/; 1Л Lt -1-£3/}=тах{33-1-0; 28-1-2;

29+4}=33.

Далее легко определяем и величины резервов времени:

A£1= L 0- ( L i + £ /) = 3 3 - 3 3 = 0 ,

A£2= L 0-(L 2 + £ 2')= 3 3 -3 0 = 3 ,

A£3= L 0—(Ь3+ £ 3/)= 3 3 —33=0.

Шаг 5. Установление интенсивности потребляемых ре­ сурсов на работах фронта F(t). Рассмотрим в момент време­ ни t максимальный фронт работ. Распределение имеющихся ресурсов R(t) основано на приоритете работ по их резервам времени. Аналогичная идея распределения ресурсов изло­ жена в работе [5]. Работы, резервы времени которых исчер­ паны, выполняются в первую очередь.

Правило распределения: работы фронта F(t) разбиваем в порядке возрастания резервов At на группы П\, П2, . ..

.. . , Па, объединив в одну группу работы с одинаковыми ре­ зервами. Если обозначить через А*1, А£2, . . . , Atq резервы времени каждой группы, то имеем

93

д ^ < д ? 2< . . . < a *<7.

При этом в первую группу попадают работы с нулевыми ре­ зервами времени А^ = 0, так как в любой фронт включена одна работа критического пути.

Суммируем максимальные интенсивности использования ресурсов pi на работах первой группы П\ и проверяем вы­ полнение неравенства

Если это неравенство удовлетворяется, то работам группы назначаем указанные интенсивности р* и вычисляем оста­ ток ресурсов

(5.9)

iQIli

Для работ группы П2проверяем неравенство

(5.10)

Если это неравенство соблюдается, то работы геПг получа­ ют максимальные интенсивности р* и снова вычисляется остаток ресурсов

(5.11)

iQJJа

Как только для какой-либо группы Пт окажется, что

там этой же группы пропорционально их максимальной ин­ тенсивности :

сов не хватает, и начало этих работ отодвигается. Величина

94

смещения начала работы вычисляется на шаге 6. В нашем примере работа i = l имеет временную оценку £i = 0 и р* = = 0 . Это говорит о том, что фактически работа г = 1 уже вы­

увеличению резервов времени Аt t. Так как At2= 3 , Aj3= 0 , то в группу П\ войдет работа i = 3, а в группу П2— работа

|ещ

Проверим неравенство (5.8):

2 р,= 5 < Д (()= 1 0 , 5 < 1 0 .

»еп,

Условие (5.8) соблюдается. Подсчитаем остаток Д!(?) по фор­ муле (5.9):

i?40 = 10— 5 = 5.

Переходим к распределению интенсивности потребления ресурсов по работам группы П2. Для работы i= 2, входящей в П2, величина рг= 3. Поскольку в группе П2 других работ нет, то суммарная интенсивность 2рг = 3 . Проверим нера-

венство (5.10):

2 р4=3< Л Ч 0= 5, т. е. 3<5. iQlIz

Выполнение условия (5.10) говорит о том, что ресурсов достаточно для производства работ группы П2. Остаток ре-

Шаг 6. Определение продолжительности фронта. Под про­ должительностью фронта будем понимать отрезок времени 0, в течение которого каждая работа фронта производится

95

с постоянной интенсивностью, установленной на шаге 5. Ра­ боты, которым ресурсов не хватило, будут начаты позже при наличии достаточного их количества. По истечении време­ ни, равного ©, произойдет перераспределение ресурсов на работах, которые, согласно диаграмме 5.3, могут выполнять­ ся в рассматриваемый момент времени.

Перераспределение ресурсов необходимо осуществлять

вкаждом из следующих четырех случаев:

1) произойдет скачок наличного уровня ресурсов R(t) согласно формуле (5.6) (отрезок времени от момента нача­ ла фронта t до момента скачка обозначим через щ);

2) закончится хотя бы одна из работ фронта (время вы­ полнения работы в пределах фронта обозначим через аг);

3)сравняются резервы времени работ групп П т —1 и П т (отрезок времени, по истечении которого это произойдет, обо­ значим через аз);

4)сравняются резервы времени работ групп Пт и П т + 1 (промежуток времени, по истечении которого это произойдет, обозначим через а4).

Таким образом, продолжительность фронта F(t), т. е. от­

резок времени 0 , в течение которого работы фронта выпол­ няются с назначенной на шаге 5 интенсивностью, можно рас­ считать по формуле

В свою очередь, каждое из а этого выражения находим сле­ дующим образом. Определим ai:

GCi=T£ t,

где Tk— время наступления скачка уровня ресурсов из вы­ ражения (5.6);

t — момент начала рассматриваемого фронта. Значение аг вычисляем по формуле

. Vi a,=m in — ,

iGF(t) ri

где Vi — объем i-й работы фронта;

rt— интенсивность, установленная на шаге 5. Величины аз и а4 находим из выражений

где A резерв времени работ группы Пт;

б — коэффициент, вычисленный по формуле (5.14).

96

Поясним подробно вывод указанных формул. Величина аз— это отрезок времени, по истечении которого резервы времени работ групп и П т сравняются. Поскольку продолжительность работы, согласно формуле (5.2), зависит от количества используемых ресурсов, то, уменьшив потреб­ ление ресурсов, тем самым увеличим продолжительность ра­ боты. Очевидно, увеличение продолжительности работы со­ кращает ее резерв времени.

Определим отрезок времени аз, по истечении которого резервы времени Atm~l и Atm будут равны. Это можно сде­ лать, используя понятие объема работ. Если резерв времени работ группы Пт больше резерва времени работ группы П т—и то это говорит о том, что работы i ^ I l m располагают (в сравнении с резервом времени работ группы Пт~г) време­ нем 0 * = А tm— AZ7”-1, в течение которого может быть про­ изведен с максимальной интенсивностью объем Vm = 0 * X Хрг • Если по какой-либо причине (простои работы или ресур­ сы расходуются не максимально) указанный объем не вы­ полнится, то запас времени 0 * (по отношению к работам группы Пт—Х) будет потерян, т. е. резерв времени Atm умень­ шится на величину 0 * и станет равным резерву времени ра­

htm— IS.tm—1 и объем недовыполненной работы при этом бу­ дет

уменьшится резерв времени Atm+1 всех работ групп Z7m+i ,

. . . , ILq в связи с тем, что эти работы не выполнялись из-за отсутствия ресурсов. За время щ для работ группы Пт , про­ изводимых с интенсивностью = рг •б, будет недовыполнен

увеличится на 04(1 — б), что равносильно уменьшению резер­ ва времени на ту же величину. Тогда резерв времени работ группы П т станет равным A tm— а4(1 — б).

Так как работы групп Пт . . . , 11q из-за недостатка ре­ сурсов на фронте F(t) не начинались, то начало выполнения работ отодвигается на <14, и тем самым резерв времени умень­ шается на эту же величину, т. е. Д?7^ 1 — сц. По истечении промежутка времени а4 резервы времени работ групп Пт и -Пm+i будут одинаковые:

A tm + 1— a4= A t m— а4(1 — 8),

откуда искомая величина 04 выразится как

дtm+ 1— Atm

Если уровень ресурсов R(t) позволяет выполнить все ра­ боты групп П\, П.2 , . . . » Ilq рассматриваемого фронта F(t) с максимальной интенсивностью р£, то отпадает необходи­ мость вычисления величин аз и а4. Поэтому в формуле (5.15) они не учитываются (принимаются равными оо).

Для нашего примера найдем продолжительность фрон­ та Е(0). Величины аз и а4 равны оо, так как для работ 2 и 3 фронта выделены максимальные интенсивности рг-.

Вычислим aj. Ввиду того, что функция R(t) определена

© = min{ai, a2, аз, a4}= m in {o o , 2, 00, 00} = 2.

Величина © = 2 показывает, что начиная с момента t = 0 в

98