<<
>>

Распределение ресурсов коммутационного поля

Рассмотрим задачу распределения соединений по областям как задачу распределения ресурсов. Это дает возможность рас­ширить сферу применения рассматриваемого ниже алгоритма [8.9, 8.1o].

В общем случае имеется множество потребителей P = {pi| i = 1,2,...,n} и множество складов S = {sj∙ | j = = 1,2,..., m}. Пусть Ai— множество альтернатив потребителя Pi, Ai = {θifc| k = 1,2,..., v}.

Установим соответствие Γ(A, G, S) между множеством всех альтернатив всех потребителей A = Aiи множеством всех

i

складов S.

Здесь G — график соответствия (рис. 8.3).

Образом Γ(aik) альтернативы aikявляется подмножество складов Sik∈S.

Допустимым решением Ri, |Rι| = n является набор альтерна­тив, содержащий по одной альтернативе из каждого набора Ai:

Тогда любое решение Ri, определяемое некоторым набором зна­чений параметров xik, будет допустимым, если для него будет выполняться следующая группа ограничений:

Прообразом Γ-1(sj) склада Sjявляется множество альтерна­тив aikпотребителей, включающих склад Sj, и Qlj = Γ-1(sj∙) ∩ ∩ Ri — множество альтернатив из решения Ri, включающих в свой состав Sj.

Пусть Pij — множество тех потребителей, чьи альтернативы входят в состав Qij, т. е. тех потребителей, чьи альтернативы в соответствии с решением Ri включают склад Sj. Пусть φij— ресурсы, которые потребляет (или необходимы для потребления) потребитель piв складе Sj. Если значения всех φijзадаются

априори, то количество ресурсов βj, необходимое потребителям в складе Sj в соответствии с решением Ri, определяется как

i

Aльтернативы α⅛. и наборы складов Γ(α⅛.), которые выбира­ются в соответствии с этими альтернативами, задаются априори. Для этой цели введем параметры αikj, значения которых задают­ся априори:

Тогда объем ресурсов, необходимый потребителям на складе Sj при реализации решения Ri в соответствии с ограничениями (8.1), определится как

В случае априорного задания всех ^>ij∙ целью задачи яв­ляется максимальное удовлетворение потребностей в ресурсах. Существуют различные варианты оптимизируемого параметра. Определим остаток Wj ресурсов на складе Sj:

Обозначим через Vi — число складов Sj, у которых, в соответ­ствии с решением Ri, остаток Wj имеет отрицательное значение. Тогда целевую функцию можно представить как

Если ввести функцию знака sign(wj∙), то

Задача сводится к выбору такого допустимого набора аль­тернатив Ri, при котором число складов, чьих ресурсов недо­

статочно для обслуживания потребителей, минимально.

Найдем минимальное значение wminсреди всех Wj, т. е. Vj[wmin≤ Wj]. В другой постановке задача представляется в виде

Задача заключается в максимизации минимального остатка ресурсов на складах после обслуживания потребителей.

Очевидно, что оптимизация по критерию F2имеет здравый смысл, если существуют решения, для которых Wmin≥ 0.

Обозначим через tiчисло потребителей pi, чьи альтернативы в соответствии с решением Ri включают склады с отрицатель­ными значениями wj∙. Это значит, что потребители в этом складе могут быть неполностью обслужены. Следующая постановка за­дачи представляется в виде

Задача сводится к минимизации числа неполно обслуженных потребителей.

Рассмотрим постановку распределения ресурсов, заключаю­щуюся в том, что для каждого потребителя pj задается мак­симально возможное число ресурсов φijкоторое он может по­требить в складе Sj. Целью решения является максимизация потребляемых ресурсов. В результате реализации некоторого решения Riдля каждого потребителя pi∈Pij, потребляющего ресурсы склада Sj, осуществляется расчет фактических ресурсов γij, потребленных в складах.

Если объем ресурсов βj, который необходим потребителям в складе Sj, в соответствии с решением Ri, меньше запасов αj∙, т. е. βj ≤ αj, то γij = φij. Если же βj> αj∙, то где nij

число потребителей склада Sj, nij = ^ij|.

Для каждого потребителя Pi определяется максимально воз­можное число ресурсов, которое он может потребить в соответ­ствии с решением Ri:

Тогда критерий оптимизации примет вид

Для задачи распределения соединений по областям множе­ство потребителей — это множество цепей T; множество складов S — это множество границ B(или множество ребер Uмодели­рующего графа G = (X, U)). Множество альтернатив Ai— это множество вариантов реализации связывающих сетей для цепи ti[8.12]. Критерии оптимизации соответствуют критериям Fi, F2, F3. Потребности потребителей в ресурсах ^jj∙ определяются шириной цепи, задаваемой априорно.

Основной целью является полное распределение цепей по областям и исключение по возможности того, чтобы параметр wj∙ принимал отрицательное значение, так как при этом невозможна 100% детальная трассировка (критерий F11).

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

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

Рассмотрим подход к формирова­нию альтернативных вариантов связы­вающих сетей. Для каждой цепи tiна множестве вершин Xi, |Xi| = k + 1,графа G строится минимальное связывающее дерево (МСД) Di с помощью алгоритма Прима [8.12] (рис. 8.4).

Di= {rik| k = 1,2,..., n}, где rik— ребро минимального свя­зывающего дерева.

Для каждого ребра rik∈Diформируется набор Vik= {vjik∖j = 1, 2, ... } вариантов маршрутов, связывающих на графе G соответствующие вершины. Каждому маршруту vjik соответствует множество Γ(vjk) ребер графа G. Формирование возможных маршрутов осуществляется следующим образом. Для ребра rik∈Di, связывающего xn∈G и xm∈G, определяется множество вершин Xik C Xi, смежных вершинам xnи xmребра rik. Через множество вершин Xik, а также через вершины xnиxm,проводятся новые вертикальные и горизонтальные линии. Отметим, что эти линии проходят по ребрам ортогонального графа G. В узлах пересечения этих линий лежат некоторые вершины xi∈X. Эти вершины являются узловыми для фор­мирования вариантов. Будем считать, что варианты маршрутов

проходят по тем ребрам графа G,которые лежат на этих линиях (рис. 8.5).

Рис. 8.5. Ребра и вершины гра­фа G,являющиеся узловыми для формирования вариантов возмож­ных маршрутов

Назовем такой маршрут двухтерминальным соединением или d-соединением. Пример: сформируем набор вариантов d-соединений для ребра rik, связывающего вершины xmи xn. Пронумеруем узлы пересечения вертикальных и горизонтальных линий. Вершина xmлежит в узле 3, а вершина xn— в узле 1o.

Для данного ребра rikсуще­ствует 1o вариантов прохожде­ния маршрута

Такой способ обеспечивает максимальное совпадение вариантов d-соединений, реализующих ребро τik, с вариантами d-соеди­нений ребер, смежных ребру τik. Формирование d-соединений осуществляется из следующих соображений:

1) d-соединения формируются таким образом, чтобы они были минимальной длины;

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

Альтернативная реализация aiιдля цепи tiзаключается в том, что для всех ребер τik минимально-связывающего дерева Diвы­браны соответствующие варианты их реализации в виде d-соеди­нений. Введем переменную yikj:

Альтернативная реализация цепи tiзадается набором пара­метров yikj, удовлетворяющих следующей группе ограничений:

k

Отметим, что если выбранные варианты d-соединений различных ребер одного и того же минимально-связывающего дерева Di включают одно и то же uj∙, то совместно они используют в Пу- объем ресурсов, равный

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Распределение ресурсов коммутационного поля:

  1. 2.2 Фотонная модель прохождения света через кристалл с произвольным распределением рассеивающих OA.
  2. Ввод изображения оптико-электронным датчиком
  3. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
  4. 3.3 Тепловизионный контроль монокристаллов германия.
  5. ВВЕДЕНИЕ
  6. ЗАКЛЮЧЕНИЕ
  7. Динамика стоимости совокупных персональных финансовых активов
  8. Объект для испытания
  9. Методика использования МИКФ
  10. 3. Понятие государственной тайны
  11. 3.6. Электронная микроскопия
  12. Известные оптические аномалии в монокристаллах германия и парателлурита.
  13. ПРИЛОЖЕНИЯ
  14. 3.4.3 Определение удельного сопротивления монокристаллов германия.
  15. 4.1. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ
  16. Выводы
  17. Основные выводы по главе 2
  18. 3.11 Основные выводы по главе 3