Алгоритмы компоновки, использующие методы целочисленного программирования

Для упрощения будем считать, что схема представлена взвешенным графом коммутационной схемы G = (E, U), где E - множество вершин, соответствующих элементам схемы, U - множество ребер соответствующих цепей, и матрицей соединений R=||rij||nЧn, n строки и столбцы которой соответствуют элементам схемы, а rij равен весу, приписанному соединению элементов еi и ej.

Пусть каждому элементу eiE приписан некоторый вес pi>0 (i=1, 2, …, п). Например, pi может быть связан с размерами элемента, мощностью, рассеиваемой элементом, и т.п. Далее, пусть заданы ограничения на формирование узлов: максимальная вместимость узла k в максимальное число выводов на узле v.

Требуется осуществить при этих условиях компоновку элементов из E в узлы Tl (l=1, 2,…, г) таким образом, чтобы количество межузловых соединений было минимальным.

Введем матрицу переменных X=||xil||nЧг, в которой xil=1, если eiTl, xil=0 в противном случае. Поскольку элемент ei может находиться лишь в одном узле,

(2.1)

Ограничение на вместимость узла Tl приводит к следующим неравенствам:

(2.2)

Число внешних соединений узла Tl может быть записано в виде

(2.3)

Действительно, хil=(1 - хil) = 1 тогда и только тогда, когда eiTl, а ejTl (

ejTs, sl).

Получим теперь выражение для критерия оптимизации. На основании (2.3) количество межузловых соединений:

(2.4)

где r0 - внешние соединения схемы.

Таким образом, задача состоит в минимизации функции (2.4) при ограничениях (2.1), (2.2) и дополнительных ограничениях:

(2.5)

Отметим, что при pi=l (i=l, 2,…, n) ограничение (2.2) равносильно ограничению на число элементов в узле.

Описанная задача оптимизации представляет собой задачу нелинейного целочисленного программирования, для которой отсутствуют эффективные методы решения.

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

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

Разбиение Т1 Т2,…, Tг называется допустимым, если каждый узел Ts (s=1, 2, …, г) является допустимым. Набор ограничений называется регулярным, если из допустимости узла следует допустимость любого подмножества элементов этого узла. Очевидно, что ограничение на число элементов в узле является регулярным, а на число внешних соединений узла - нет.

Рассмотрим схему рисунке 3. Пусть ограничение по числу выводов v=3, тогда узел Т={е1, е2, е3, е4, е5} является допустимым, однако Т'={е1 е2, е4, е5} является недопустимым узлом, поскольку имеет четыре внешних соединения.

Рисунок 3 - Нерегулярное ограничение

Пусть схема соединений задана графом G = (E, V, W). Рассмотрим некоторое разбиение Кг ={T1, Т2,…, Tг} схемы на допустимые узлы.

Эквивалентная задача минимизации функции:

(2.5)

в которой ms=|Js| равно числу цепей, связанных с элементами узла Ts.

Рассмотрим теперь семейство P={Ts} непустых подмножеств множества удовлетворяющее следующему условию:

(2.6)

Тs - допустимый узел. Отметим, что условие (2.6) разрешает повторные вхождения элементов в некоторые узлы: в общем случае Ts∩Tl ≠Ш при s≠l.

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

Читайте также

Разработка конструкции и технологического процесса изготовления диффузионного резистора
Разработать конструкцию и выбрать технологический процесс изготовления диффузионного резистора в составе ИМС. Программа выпуска - 50000 шт. в год. Выпуск ежемесячный. Параметры ...

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

Проектирование двухвходовой КМОП-схемы дешифратора 2 в 4
КМОП (комплементарная логика на транзисторах металл-оксид-полупроводник; англ. CMOS, Complementary-symmetry/metal-oxide semiconductor) - технология построения электронных схем. В те ...