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

П\, то величины аз и 04 в формуле (5.1*5) принимаются рав­ ными ОО.

2. Пусть работы фронта составляют только две группы— П\ и П2. Тогда возможны случаи:

а) если по работам первой группы в шаге 5 распределя­ ются максимальные интенсивности использования ресурсов, а работам второй группы назначаются г* = р£ -6> -0, то 04=

=с о ;

б) если по работам первой группы в шаге 5 распределя­ ются r t = p f -6Х ) , а для работ второй группы не остается ресурсов, то аз= оо.

3.Если уровень ресурсов B(t) позволяет производить ра­ боты всех групп рассматриваемого фронта с максимальной интенсивностью, то 03= 04= 00.

4.Пусть некоторая i не допускает перерыва в ходе вы­ полнения. Это означает, что если она начата на k-й итерации

ине завершена в течение одного фронта, то обязательно нужно продолжать ее на fe-f-1, &+2. .. и т. д. итерациях. При этом на последующих итерациях данная работа подключа­ ется в группу /7ь и резерв времени At ее условно полагается равным нулю.

5.Если на шаге 5 k-и итерации все работы производи­ лись с максимальной интенсивностью г = р и ни одна работа фронта не была закончена, то после пересчета объема и про­ должительности оставшейся части работ формирования но­ вого исходного графа Gk+1 (X , U) не происходит. Следующая

(& + 1 )-я итерация начинается сразу же с шага 2. При этом в качестве текущего сетевого графа G{XkJrl, Uk+1), получа­

емого на шаге 1, принимаем граф G(Xk, Uk), работы которо­ го имеют пересчитанные временные оценки, и ранние нача­

этом случае на шаге 5 необходимо дополнительно проверять условие

Ъ = [ Pi‘ sJ>Pio»

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

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

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

112

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

Все шаги алгоритма остаются без изменения, только нужно учитывать, что

P io = P i= n .

8. Рассмотренный алгоритм можно положить в основу при решении задачи, когда величина г* интенсивности ре­ сурсов принимает любое постоянное значение из некоторого интервала:

Pimin^Cri'^-P/raax •

Задача усложняется тем, что необходимо определить еще для каждой работы постоянную величину rt = const из ин­ тервала (pimin, Pimax).

Указанная постановка реализуется следующими этапа­

ми.

На первом этапе при условии

PiO= PimiD'^^i'^Pimax;=Pi

используем наш алгоритм полностью без изменения. В ре­ зультате находим величины , постоянные на фронте F (tk), с продолжительностью 0 k .

На втором этапе вычисляем среднее значение интенсив­ ности :

^rik-Qk

На третьем этапе с учетом рг0 — Pi — rio относительно исходного графа с полными контурами снова применяем наш алгоритм.

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

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

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

Решение задачи при использовании нескольких видов ресурсов можно осуществить по методу, изложенному выше, но необходимо учитывать ряд особенностей.

Постановка задачи. Пусть дана функция изменения во времени каждого вида нескладируемых ресурсов Rj (t), ; = 1, 2, . . . , М. Считаем, что функция Rj (t) ступенчатая (дискрет­

из Rj (t) терпит разрыв первого рода, т. е. изменяется зна­ чение одной функции на конечную величину. Запишем это в таком виде:

Rjk*

где 7 = 1 , 2, . . . , M и Rjk — const в k-ш отрезке времени. Как уже отмечалось, для выполнения любой работы по­

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

пользовании одного комплекта в единицу времени выполня­ ется объем, равный Ht. Очевидно, что H ^ V i . Предполо­ жим, что существует прямо пропорциональная зависимость между произведенным объемом работы, количеством ком­ плектов и величиной Ht. Так как величина Hi определена заранее и фиксирована, то объем осуществленной работы в единицу времени зависит от числа применяемых комплек­ тов. Обозначим число комплектов на i-й работе через гг. Ис­ ходя из характера работы i можно установить максимальное число комплектов С; без учета запаса ресурсов.

Может оказаться, что из-за ограниченности ресурсов нель­ зя направить на данную работу все Сг комплектов. Поэто­ му на каждой работе i при заданном уровне ресурсов Rj (t) можно максимально использовать только р* комплектов. Значение pi найдено при условии, что весь запас ресурсов Rj (t) будет направлен только на работу i.

Таким образом, rt ^ P i ^ C f . Если изменяется Rj(t) в мо-

114

мент времени t, то необходимо определить новое значение pi. В дальнейшем под максимальным числом комплектов будем подразумевать рг, установленное с учетом уровня ре­

Итак, для каждой работы предполагаем известными: комплект используемых ресурсов (совокупность чисел Stj, i = 1, 2, . . . , N, j = 1, 2, . . . , M), объем Vit величину Hit мак­ симальное количество комплектов р£, а также вычисленное по формуле (5.20) значение ti0. Представим названные па­ раметры в виде таблицы 5.9. Считаем также найденными функции Rj(t).

Исходная сетевая модель дана в виде сетевого графа с полными контурами.

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

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

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

115

формуле (5.1), задан в единицах измерения нескладируемых ресурсов, то, введя параметр Hit можно ресурсы Rj(t) и объ­

емы работ выражать в разных единицах измерения. Напри­ мер, некоторые ресурсы могут измеряться в штуках, а объем работы — в кубических метрах или тоннах. Так как нескладируемые ресурсы в общем случае должны быть це­ лочисленными, то элементы комплекта Sij — целыми. Оче­

видно, что в каждом столбце j таблицы 5.9 существует хотя бы один элемент S ^ X ).

Опишем подробно шаги алгоритма.

Шаг 1. Построение текущего сетевого графа. Проанали­ зируем исходный граф Go(X, U). В качестве временных оце­ нок работ примем величины ti0 — минимальную продолжи­ тельность выполнения работы г, найденную по формуле (5.20). При этом считаем, что в начальный момент t = 0 для каждой работы вычислены рг исходя из уровня ресурсов

R j ( t = 0).

Приняв временные оценки работ t i0, синтезируем сете­ вой граф с минимальным значением длины критического пу­ ти. Для этого применяем алгоритм В — алгоритм синтеза оптимального сетевого графа в исходном графе с полными контурами (§ 3, глава III). В результате имеем граф G(XX, С/1).

В следующих итерациях на шаге 1 получаем граф G(Xk, Uk )

шага полностью совпадают с действиями шага 2, описанны­ ми в третьем параграфе главы V. Только график Гi измене­ ния суммарной интенсивности потребления ресурсов от вре­ мени t строим для каждого вида нескладируемых ресурсов. При этом величину каждого используемого вида ресурсов

времени отрезка (0, Т), где Т — длина критического пути се­ тевого графа G(XX, С/1), то получаем искомое решение нашей задачи. В противном случае переходим к шагу 3.

Шаг 3. Определение фронта работ F(t).

Шаг 4. Вычисление резерва времени работ фронта F(t). Действия этих шагов полностью совпадают с действиями шагов 3 и 4, изложенными в третьем параграфе главы V.

116

Шаг 5. Вычисление значений комплектов г* используемых ресурсов и нахождение продолжительности фронта. Все работы фронта разбиваем на группы П\, 772, . . . , J7g, объединив в одну группу работы с одинаковыми резервами времени. Если обозначить через Ait1, At2, . . . , Atq резервы времени каждой группы, то должно соблюдаться условие At1<СAt2 At9. При этом в первую группу попадают ра­ боты с нулевыми резервами времени, т. е. At!= 0. Заметим, что во фронте обязательно имеется группа работ с нулевыми резервами времени, так как в эту группу входят работы, ле­ жащие на критическом пути.

В зависимости от уровня ресурсов Rj (t) в рассматривае­ мый момент t может быть несколько случаев распределе­ ния комплектов использования ресурсов и вычисления про­ должительности фронта.

Случай 1. Пусть уровень ресурсов таков, что для всех ра­ бот фронта можно назначить максимальное число комплек­ тов pf. Если обозначить через Rj(IIp) потребное количество ресурсов j-ro вида для работ группы Пр, то для случая 1 можно записать следующие соотношения:

[x ] — целая часть числа x. Здесь t — момент анализа работ фронта F(t), xk— конец отрезка времени, определяемого по формуле (5.19), куда входит момент f.

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

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

117