Том 23, номер 1, 2016 г., Стр. 82-96

УДК 519.854
Забудский Г. Г., Веремчук Н. С.
Алгоритм приближённого решения задачи Вебера на линии с запрещёнными зонами

Аннотация:
Рассматривается задача оптимального размещения взаимосвязанных объектов на линии с запрещёнными зонами. Необходимо минимизировать суммарную стоимость связей объектов с зонами и между собой. Найдены свойства задачи, позволяющие исходную непрерывную задачу свести к дискретной. Разработан алгоритм поиска приближённого решения. Приведены результаты вычислительного эксперимента.
Табл. 1, библиогр. 15.

Ключевые слова: задача размещения, взаимосвязанные объекты, приближённое решение.

DOI: 10.17377/daio.2016.23.489

Забудский Геннадий Григорьевич ¹
Веремчук Наталья Сергеевна ¹
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: zabudsky@ofim.oscsbras.ru, n-veremchuk@rambler.ru

Статья поступила 29 апреля 2015 г.
Исправленный вариант — 10 августа 2015 г.

Литература

[1] Гончаров Е. Н., Кочетов Ю. А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискрет. анализ и исслед. операций. Сер. 2. 2002. Т. 9, № 2. С. 13–30.

[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[3] Ерзин А. И., Чо Д. Д. Задача одновременного размещения и маршрутизации при проектировании интегральных схем // Автоматика и телемеханика. 2003. № 12. С. 177–190.

[4] Забудский Г. Г., Амзин И. В. Алгоритмы компактного размещения технологического оборудования на параллельных линиях // Сиб. журн. индустр. математики. 2013. Т. 16, № 3. С. 86–94.

[5] Забудский Г. Г., Веремчук Н. С. Алгоритмы поиска приближённого решения задачи Вебера на линии с запрещёнными зонами //Мат. XV Всерос. конф. «Математическое программирование и приложения» (Екатеринбург, 2–6 марта, 2015 г.). Екатеринбург: ИММ Уро РАН, 2015. С. 133.

[6] Мухачёва Э. А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки // Мат. междунар. конф. «Дискретный анализ и исследование операций». Новосибирск: Изд-во Ин-та математики, 2002. С. 80–87.

[7] Панюков А. В. Задача размещения прямоугольных объектов с минимальной стоимостью связывающей сети // Дискрет. анализ и исслед. операций. Сер. 2. 2001. Т. 8, № 1. С. 70–87.

[8] Руднев А. С. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 4. С. 61–86.

[9] Стоян Ю. Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наукова думка, 1986. 268 с.

[10] Трубин В. А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой // Кибернетика. 1978. № 6. С. 67–70.

[11] Cheng L., Wong M. D. F. Floorplan design for multi-million gate FPGAs // Proc. 2004 IEEE/ACM Int. Conf. Comput.-Aided Des. (San Jose, CA, USA, Nov. 7–11, 2004). Washington, DC: IEEE Comput. Soc., 2004. P. 292–299.

[12] Cong J., Jagannathan A., Reinman G., Romesis M. Microarchitecture evaluation with physical planning // Proc. 40th Annu. Des. Autom. Conf. (Anaheim, USA, June 2–6, 2003). New York: ACM, 2003. P. 32–35.

[13] Kahng A. B. Classical floorplanning harmful? // Proc. 2000 Int. Symp. Phys. Des. (San Diego, USA, Apr. 9–12, 2000). New York: ACM, 2000. P. 207–213.

[14] Simmons D. M. One-dimensional space allocation: an ordering algorithm // Oper. Res. 1969. Vol. 17, No. 5. P. 812–826.

[15] Suresh G., Sahu S. Multiobjective facility layout using simulated annealing // Int. J. Prod. Econ. 1993. Vol. 32, No. 2. P. 239–254.