Preview

Научный рецензируемый журнал "Вестник СибАДИ"

Расширенный поиск

ПОИСК ЛОКАЛЬНОГО МИНИМУМА В ЗАДАЧЕ РАЗМЕЩЕНИЯ ПРЯМОУГОЛЬНИКОВ НА ЛИНИЯХ

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

Просмотров: 243


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2071-7296 (Print)
ISSN 2658-5626 (Online)