Оптимизация размещения взаимосвязанных объектов на параллельных линиях с запрещёнными зонами

Приводится обзор постановок, моделей и методов решения задачи размещения взаимосвязанных прямоугольных объектов на параллельных линиях с запрещёнными зонами. Центры объектов связаны коммуникациями между собой и с зонами. Необходимо разместить объекты вне зон таким образом, чтобы суммарная стоимость связей объектов между собой и с зонами была минимальной. Основное внимание уделяется задаче на линии. Для нескольких линий связи прокладываются через виадук. Построены модели в теоретико-графовой формулировке и формулировке частично-целочисленного программирования с булевыми переменными. Найдены свойства, позволяющие рассматривать задачу как дискретную и декомпозировать её на ряд задач меньшей размерности. Разработаны алгоритмы поиска точного и приближённого решений, выделены полиномиально разрешимые случаи. Приведены результаты численных экспериментов. Библиогр. 32.