2.2 Мінімізація числа міжвузлових сполучень

Основою даного алгоритму компоновки є використання ітераційного процесу обміну місцями елементів, що належать різноманітним вузлам з метою мінімізації числа міжвузлових сполучень.

Розглянемо ітераційний алгоритм компоновки. Необхідно виконати компоновку елементів схеми в вузли (кількість елементів N=7) з урахуванням заданих обмежень (кількість елементів в вузлі не повинно перевищувати заданого значення КЕ). Можна вважати, що в кожному вузлі міститься максимальна кількість елементів (КЕ=6 для розглядуваного прикладу). В випадку, коли в якому-або вузлі число елементів К менш КЕ, необхідно додатково ввести Ng=KE-K фіктивних елементів, не звязаних з іншими елементами схеми.

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

Приріст числа міжвузлових сполучень при обміні місцями елементів буде рівно [1]:

L (x, y)=Ex+Ey - 2rxy,

де rxy - елемент матриці R;

Ex=Lx - Fx, Ey=Ly - Fy;

Lx (Ly) і Fx (Fy) відповідно зовнішні і внутрішні сполучення елементів Dx, Dy.

При розрахунку зовнішніх сполучень необхідно враховувати сполучення тільки між розглядуваними вузлами Т1, Т2. Зовнішні звязки з D0 можна не враховувати.

Рисунок. 2.1 - Мінімізація міжвузлових сполучень (крок 1)

d(4,6)=1+4-2*3=-1(покращень немає)

d(6,1)=4-2-2*0=2

d(6,2)=4-3-2*0=1

d(6,4)=4+1-2*3=-1 (покращень немає)

d(6,5)=4-5-2*1=-3 (покращень немає)

Елементи 6 та 1 міняємо місцями

Рисунок. 2.2- Мінімізація міжвузлових сполучень (крок 2)

d(2,3)=1-1-2*0=0 (покращень немає)

d(2,7)=1-0-2*2=-3 (покращень немає)

d(1,6)=3-4-2*0=-1 (покращень немає)

d(1,2)=3-1-2*1=0 (покращень немає)

d(1,4)=3-5-2*0=-2 (покращень немає)

d(1,5)=3-3-2*2=-4 (покращень немає)

Введемо фіктивний елемент 8 у вузол Т2

Рисунок. 2.3 - Мінімізація міжвузлових сполучень (крок 3)

d(2,8)=1-0-2*0=1

Елементи 2 та 8 міняємо місцями

Рисунок. 2.4 - Остаточний варіант компоновки

Більше покращень немпє.

Рисунок. 2.5 - Комутаційна схема внутрішньовузлових сполучень вузла Т1

Рисунок. 2.6 - Комутаційна схема внутрішньовузлових сполучень вузла Т2

Рисунок. 2.7 - Комутаційна схема внутрішньовузлових сполучень вузла Т3

Рисунок. 2.8 - Схема міжвузлових сполучень