1. Алгоритмы, использующие силовые функции, в которых задача размещения сводится к задаче определения статического состояния модельной механической системы материальных точек. Элементы интерпретируются как материальные точки, между которыми действуют силы притяжения и отталкивания. Силы притяжения
между точками
(
,
) и
(
,
) пропорциональны числу связей
, силы отталкивания Ф
ij между точками
,- и
возрастают с уменьшением
. Вводятся силы отталкивания
от краев коммутационного поля и силы сопротивления среды
где
— скорость движения точки
(
,
),
— экспериментально определяемый коэффициент. Алгоритмы этой группы сложны для реализации на ЭВМ.
2.
Последовательные алгоритмы размещения предусматривают первоначальное размещение части элементов. На следующем шаге рассматривается упорядоченное множество неразмещенных элементов, множество свободных позиций и матрица длин связей [
], где
— длина соединений между элементом
и другими ранее размещенными элементами при условии размещения элемента
в позиции
. Для каждой позиции определяется суммарная длина соединений (СДС) элементов, для которых эта позиция наиболее удобна (в смысле минимальной длины соединений с размещенными элементами). Иногда подсчитывается не абсолютная длина соединений, а приращение длины соединений, т. е. вводится некоторая
целевая функция, учитывающая связи данного элемента с размещенными элементами. После размещения очередного элемента (модуля) процесс повторяется для оставшихся элементов и вакантных установочных мест до тех пор, пока не будут размещены все элементы. Алгоритмы этой группы просты в реализации и наиболее быстродействующи.
3.
Итерационные алгоритмы размещения, сводящиеся к перестановкам элементов (парные замены, соседние парные замены, частичный перебор). Предполагается наличие начального размещения, полученного с помощью алгоритмов первой или второй группы или вручную, и используются для улучшения первоначального размещения. Например, в итерационном алгоритме парных замен каждый элемент меняется с каждым и при каждой пробе просматривается, сокращается ли СДС. Все возможные пробы (их число равно
(
—1)/2, где
— число элементов) составляют одну итерацию. Выбирается та замена, которая приводит к наибольшему сокращению СДС. Время решения пропорционально
и при больших размерностях применение алгоритма нецелесообразно. Алгоритм соседних парных замен отличается от предыдущего просмотром только соседних элементов (например, при расстоянии
= 4 от первичного элемента просматривается около 2
(
+1)=40 элементов). Применяются методы упорядочения просмотра элементов при замене, групповые перестановки.
4. Алгоритмы, использующие принцип случайного размещения, предусматривают решение многокритериальной и многоэкстремальной задачи о назначении. Решение получается точным, но требует большого машинного времени, так как просматриваются различные варианты (полный перебор) закрепления элементов на посадочные места с вычислением в каждом варианте целевой функции (СДС). Сюда относятся алгоритмы случайного поиска (слепого поиска, случайного блуждания), алгоритмы назначения (линейного назначения, квадратичного назначения).
5. Алгоритмы, использующие комбинаторные методы целочисленного (дискретного) программирования, обеспечивают получение точного решения, но требуют большого машинного времени. Наиболее распространены алгоритмы
метода ветвей и границ.
