Математическая постановка задачи компоновки схем конструктивно унифицированными модулями

Пусть имеется схема, состоящая из n элементов: , где e₀ – разъем.

Данную схему необходимо скомпоновать в r блоков: .

Обозначим через вес – число элементов j -го блока.

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

При решении этой задачи необходимо выработать критерий разбиения:

1) минимальное число межблочных связей;

2) минимальное число внешних выводов каждого блока;

3) любой другой критерий.

Математическая постановка задачи компоновки зависит от выбора исходной ММ схемы, оптимизирующего критерия качества и от учета тех или иных ограничений.

Математическая постановка задачи компоновки с использованием модели ВНГ

Критерий оптимизации – число межблочных связей. ВНГ будем представлять в виде матрицы C.

Введем в рассмотрение матрицу решений ξ, которая определяет вариант компоновки элементов схемы в блоки.

На элементы матрицы решений накладываются следующие ограничения:

Т.е. каждый элемент может быть расположен только в одном блоке.

Число элементов в блоке должно быть не больше заданного.

Выведем формулу для числа внешних выводов блока.

Очевидно, что выражение означает число межблочных связей, которые выходят из блока b_j от элемента e_i на элемент e_k,расположенный вне блока b_j.

Очевидно, что выражение означает число межблочных связей, выходящих из блока b_j от элемента e_i на все остальные элементы схемы, расположенные вне блока b_j, включая элемент e₀.

Для того, чтобы получить общее число выводов от блока b_j, необходимо просуммировать предыдущее выражение по i:

Теперь получим формулу для суммарного числа межблочных связей:

С учетом выражения (3.2) второй член выражения (3.5) перепишем в виде:

– число связей с внешним разъемом схемы.

Поэтому в качестве можно взять первую часть целевой функции (3.5). Т.о., необходимо найти такую матрицу решений ξ, удовлетворяющую ограничениям (3.2)–(3.4), для которой обеспечивается минимум целевой функции (3.5). Данная задача является задачей квадратичного целочисленного программирования с булевыми переменными c_ij.

В связи с тем, что модель ВНГ является грубой моделью, то и полученные формулы (3.4), (3.5) носят грубый характер.

Для примера рассмотрим схему, приведенную на рисунке 3.1.

Рис. 3.1

ВНГ для данной схемы приведен на рисунке 3.2 (примечание: вес ребра на рисунке обозначен количеством связей).

Пусть требуется разбить приведенную схему на блоки с ограничениями:

.

Из рассмотрения ВНГ нетрудно видеть, что по данной модели невозможно разбить схему не только на два, но и на четыре блока. На самом же деле это не так (см. схему). Это говорит о неточности данной модели.

Математическая постановка задачи компоновки с использованием модели ГГ

Рассмотрим ту же задачу, т.е. задачу нахождения матрицы решений ξ для данного варианта разбиения. На элементы матрицы ξ_ij накладываются те же ограничения (3.2 и 3.3), что и выше.

Отметим, что каждая цепь v_k в блоке b_j может потребовать либо один, либо ноль выводов. Для того чтобы цепь v_k потребовала один вывод необходимо и достаточно, чтобы хотя бы один элемент, инцидентный данной цепи, был бы расположен в блоке b_j, и хотя бы один элемент, инцидентный данной цепи, включая элемент e₀, был бы расположен вне блока b_j.

Математически вышесказанное записывается следующим образом.

– сумма элементов, инцидентных цепи v_k и расположенных в блоке b_j.

– сумма элементов, инцидентных цепи v_k и расположенных вне блока b_j.

Введем в обозначения функцию:

С учетом данного обозначения выражение

будет справедливо, если цепь v_k содержит хотя бы один элемент e_i в блоке b_j. Выражение

справедливо, если цепь v_k содержит хотя бы один элемент вне блока b_j.

Число внешних выводов блока b_j, которые требуют цепи v_k, определяется из выражения:

.

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

определяет количество блоков, в которых содержатся элементы, инцидентные цепи v_k. Количество межблочных связей, которые требует цепь v_k (без учета элемента e₀), определяется из выражения:

.

Количество межблочных связей, которые требует цепь v_k с учетом внешнего разъема e₀, определяется из выражения:

.

Для определения суммарного числа межблочных связей просуммируем выражение (3.13) по всем цепям v_k .

Задача (3.14) это задача нелинейного целочисленного программирования с булевыми переменными.

Теперь вернемся к нашему примеру (рис. 3.1).

Матрица инцидентности (цепей) ГГ имеет вид:

			v1	v2	v3	v4	v5	Т.о., элементы hik известны.
		e0
H	=	e1
e2
		e3
		e4

Матрица решений ξ для нашего примера имеет вид:

			b1	b2
		e1	ξ11	ξ12				Т.о., элементы ξij для нашего варианта компоновки тоже известны.
ξ	=	e2	ξ21	ξ22	=
		e3	ξ31	ξ32
		e4	ξ41	ξ42

Формула (3.13), примененная для каждой цепи v_k, показывает, что каждая из них требует только один вывод.

Формула (3.14) для нашего варианта разбиения (компоновки) дает следующее число межблочных связей:

Блочная организация схемы рисунка 3.1 при таком варианте размещения приведена на рисунке 3.3.

Общая характеристика алгоритмов компоновки конструктивных модулей

Все существующие алгоритмы компоновки конструктивных модулей можно разделить на два основных класса: точные и приближенные алгоритмы, которые, в свою очередь представлены несколькими подклассами (см. рис. 3.4).

Рис. 3.4 Классификация алгоритмов компоновки

Алгоритмы Лаурера основаны на сведении задачи компоновки к так называемой задаче покрытия, возникающей при минимизации булевых функций. Эти алгоритмы в качестве модели схемы используют гиперграф (матрицу H).

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

При современном быстродействии ЭВМ точные алгоритмы позволяют решать задачи с числом переменных не более 20-ти. В связи с этим на практике широко применяются приближенные, эвристические алгоритмы, математически слабо обоснованные, но дающие неплохие результаты. Суть последовательных алгоритмов – последовательное заполнение блоков еще не распределенными в блоки элементами. В качестве очередного элемента выбирается элемент максимально связанный с элементами, уже включенными в формируемый блок. Процесс заполнения блока элементами продолжается до тех пор, пока не нарушаются ограничения на модульную () и контактную () емкости блока. Имеются различные модификации таких алгоритмов, отличающиеся выбором критерия для кандидата на включение и способом вычисления оценки.

Суть параллельно-последовательных алгоритмов: здесь сначала выделяются некоторые группы элементов, например, сильно связанные между собой, а затем эти группы параллельно распределяются по блокам с учетом контактных и модульных ограничений.

Итерационные алгоритмы служат для улучшения некоторого начального варианта компоновки, полученного либо вручную, либо с помощью последовательных алгоритмов, и состоят в обмене (перестановках) элементов, принадлежащих разным блокам. При этом осуществляются одинарные, двойные и, в общем случае, групповые перестановки элементов.

Дата добавления: 2014-01-14