ПОИСК ЛОКАЛЬНОГО МИНИМУМА В ЗАДАЧЕ РАЗМЕЩЕНИЯ ПРЯМОУГОЛЬНИКОВ НА ЛИНИЯХ
https://doi.org/10.26518/2071-7296-2017-1(53)-122-128
Аннотация
Рассматривается задача оптимального размещения взаимосвязанных прямоугольных объектов на параллельных линиях с запрещенными зонами. Размещение внутри запрещенных зон не допускается. Объекты связаны между собой и с зонами. Метрика прямоугольная, критерий – минимизация суммарной стоимости связей объектов между собой и с зонами. Такие задачи необходимо решать, например, при проектировании расположения элементов сложных систем. Построена модель частично-целочисленного линейного программирования поиска локального оптимума задачи. Проведен вычислительный эксперимент с использованием предложенной модели и пакета IBM ILOG CPLEX.
Ключевые слова
Об авторе
Н. С. Веремчук
Институт математики им. С. Л. Соболева СО РАН
Россия
Россия
аспирант, Институт математики им. С.Л. Соболева СО РАН
644043, г. Омск, ул. Певцова, 13
Список литературы
1. Farahani R.Z., Hekmatfar M. Facility location: Concepts, models, algorithms and case studies. Heidelberg: Physica-Verlag, 2009. 549 p.
2. Klamroth K. Single-Facility Location Problems with Barriers. Springer Series in Operations Research, 2002. 216 p.
3. Zabudsky G., Veremchuk N., About Local Optimum of the Weber Problem on Line with Forbidden Gaps. Proc. DOOR 2016, Vladivostok, Russia, September 19-23, 2016. CEUR-WS. 2016, vol. 1623, pp. 115-124. CEURWS.org, online: http://ceur-ws.org/Vol-1623/ paperco17.pdf
4. Забудский, Г. Г. Алгоритм приближенного решения задачи Вебера на линии с запрещёнными зонами / Г. Г. Забудский, Н. С. Веремчук // Дискрет. анализ и исслед. операций. – 2016. – Т. 23, № 1. – С. 82-96, [G.G. Zabudskii, N.S. Veremchuk, An Algorithm for Finding an Approximate Solution to the Weber Problem on a Line with Forbidden Gaps. J. Appl. Ind. Math., 2016, 10(1), pp. 136-144].
5. Забудский, Г. Г. Алгоритмы компактного размещения технологического оборудования на параллельных линиях / Г. Г. Забудский, И. В. Амзин // Сиб. журн. индустр. матем. – 2013. –16:3 (55). – С. 86–94.
6. E.A. Mukhacheva, V.A. Zalgaller, Linear programming cutting problems. Intern. J. of Software Engineering and Knowledge Engineering, 1993, vol. 3, no. 4, pp. 463-476.
7. Мухачева, Э. А. Метод динамического перебора в задаче двумерной упаковки / Э. А. Мухачева, А. Ф. Валеева // Информационные технологии. – 2000. – № 5. – С. 30-37.
8. Руднев, А. С. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу / А. С. Руднев // Дискрет. анализ и исслед. операций. – 2009. – Т. 16, № 4. – С. 61-86.
9. Математическая модель оптимизации гибких модулей технологического оборудования / Г.Г. Забудский, С. А. Лёгких // Прикл. математика и информ. технологии : сб. науч. и метод. трудов. – Омск, 2005. – С. 20–28.
10. Wai-Kai Chen. The VLSI Handbook, CRC Press, 2000. 1975 p.
11. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NPCompleteness. Freeman, San Francisco, 1979; Mir, Moscow, 1982. 338 p.
Рецензия
Для цитирования:
Веремчук Н.С. ПОИСК ЛОКАЛЬНОГО МИНИМУМА В ЗАДАЧЕ РАЗМЕЩЕНИЯ ПРЯМОУГОЛЬНИКОВ НА ЛИНИЯХ. Научный рецензируемый журнал "Вестник СибАДИ". 2017;(1(53)):122-128. https://doi.org/10.26518/2071-7296-2017-1(53)-122-128
For citation:
Veremchuk N.S. SEARCH OF LOCAL MINIMUM IN LOCATION PROBLEM OF RECTANGLES ON LINES. The Russian Automobile and Highway Industry Journal. 2017;(1(53)):122-128. (In Russ.) https://doi.org/10.26518/2071-7296-2017-1(53)-122-128
Просмотров:
811
Послать статью по эл. почте 