Рис. 7. Схема соединений с учетом разъема

3. Размещение элементов на коммутационных платах

Постановка задачи размещения.

Дано:

E = {e1, e2, e3, e4, e5, e6, e7} – множество элементов схемы устройства.

P = {p1, p2, p3, p4, p5, p6, p7} – множество установочных позиций на коммутационной плате для размещения элементов.

Задача размещения состоит в определение соответствия между элементами устройства и установочными позициями печатной платы. Разъем (элемент е7) может находиться только в одной конкретной позиции (позиция p7), все остальные элементы однотипны, а позиции равноправны, следовательно мы имеем 6! Вариантов размещений элементов на плате. Такая задача называется задачей дискретного размещения. Для того чтобы упростить задачу размещения и не перебирать все 6! вариантов решений используются различные комбинационные методы. В данной курсовой работе используется метод ветвей и границ.

Метод ветвей и границ.

Ход решения.

Соответствие блоков полученных в разделе 1 элементам.

1. Определение последовательности элементов.

Последовательность элементов строится исходя из оптимизированной компоновки (рис 4.), по ней определятся количество между элементами. Элемент, наиболее связанный с разъемом: е2.

Дальнейшая последовательность элементов (каждый элемент наиболее связан с предыдущими): е1, е3, е5, е6, е4.

2. Составление матрицы D и матрицы S.

Матрицы составляются исходя из оптимизированной компоновки (рис 7.).

3. Расчет верхней границы – функции качества размещения.

Функция качества размещения рассчитывается следующим образом:

1. Разъем (е7) помещается в позицию (р7). Все остальные элементы остаются неразмещенными.

2. Наиболее связанный с разъемом элемент (е2) последовательно помещается в каждую возможную позицию (p1…p6), рассчитывается нижняя оценка данного размещения. Выбирается позиция, нижняя оценка размещения которого минимальна.

Нижняя оценка рассчитывается следующим образом:

F = Fн + Fнр + Fр, где:

1.                  Fн – оценка длины связи между не размещенными элементами

2.                  Fнр – оценка длины связи между не размещенными и размещенными элементами

3.                  Fр – значение длины связи между размещенными элементами

Для расчета нижних оценок используется программа placeing.

Минимальная нижняя оценка при размещение в позицию p6 = 4560. Элемент закрепляется в позиции p6.

3. Аналогично пункту 2 выбираются элемент наиболее связанный с размещенными элементами и разъемом. Перебираются возможные варианты размещение элемента и выбирается такое размещение, нижняя оценка которого минимальна. Элемент закрепляется в данной позиции.

4. Пункт 3 выполняется до тех пор, пока не будут размещены все элементы. Полученное размещение:

Страницы: 1, 2, 3