sibadiНаучный рецензируемый журнал "Вестник СибАДИ"The Russian Automobile and Highway Industry Journal2071-72962658-5626The Siberian State Automobile and Highway University10.26518/2071-7296-2017-1(53)-122-128sibadi-83Research ArticleИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕINFORMATICS, COMPUTER ENGINEERING AND MANAGEMENTПОИСК ЛОКАЛЬНОГО МИНИМУМА В ЗАДАЧЕ РАЗМЕЩЕНИЯ ПРЯМОУГОЛЬНИКОВ НА ЛИНИЯХSEARCH OF LOCAL MINIMUM IN LOCATION PROBLEM OF RECTANGLES ON LINESВеремчукН. С.VeremchukN. S.

аспирант, Институт математики им. С.Л. Соболева СО РАН

644043, г. Омск, ул. Певцова, 13

Post-Graduate Student

644043, Russia, Omsk, Pevtsova St., 13

n-veremchuk@rambler.ruИнститут математики им. С. Л. Соболева СО РАНРоссияSobolev Institute of Mathematics Siberian Branch of RASRussian Federation20172408201701(53)122128Copyright © Веремчук Н.С., 20172017Веремчук Н.С.Veremchuk N.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibadi.org/jour/article/view/83

Рассматривается задача оптимального размещения взаимосвязанных прямоугольных объектов на параллельных линиях с запрещенными зонами. Размещение внутри запрещенных зон не допускается. Объекты связаны между собой и с зонами. Метрика прямоугольная, критерий – минимизация суммарной стоимости связей объектов между собой и с зонами. Такие задачи необходимо решать, например, при проектировании расположения элементов сложных систем. Построена модель частично-целочисленного линейного программирования поиска локального оптимума задачи. Проведен вычислительный эксперимент с использованием предложенной модели и пакета IBM ILOG CPLEX.

The problem of optimum location of the interconnected facilities on parallel lines with the forbidden gaps is considered. Location in the forbidden gaps isn’t allowed. The locating facilities are connected among themselves and with gaps. For measurement of distances the rectangular metrics is used. Criterion of optimization is minimization of total cost of communications of facilities among themselves and with gaps. The considered problem is model of many practical applications from various fields of science and design. The mathematical model of integer linear programming of search of a local optimum of the problem is constructed. The computing experiment with use of the offered model and an IBM ILOG CPLEX package is made.

математическая модельзадача Веберазапрещенные зоныпараллельные линиипрямоугольная метрикаmathematical modelWeber problemforbidden gapsparallel linesrectangular metricsReferencesFarahani R.Z., Hekmatfar M. Facility location: Concepts, models, algorithms and case studies. Heidelberg: Physica-Verlag, 2009. 549 p.Farahani R.Z., Hekmatfar M. Facility location: Concepts, models, algorithms and case studies. Heidelberg: Physica-Verlag, 2009. 549 p.Klamroth K. Single-Facility Location Problems with Barriers. Springer Series in Operations Research, 2002. 216 p.Klamroth K. Single-Facility Location Problems with Barriers. Springer Series in Operations Research, 2002. 216 p.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.pdfZabudsky 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. CEUR-WS.org, online: http://ceur-ws.org/Vol-1623/paperco17.pdfЗабудский, Г. Г. Алгоритм приближенного решения задачи Вебера на линии с запрещёнными зонами / Г. Г. Забудский, Н. С. Веремчук // Дискрет. анализ и исслед. операций. – 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].Zabudskii G.G., Veremchuk N.S. 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.Забудский, Г. Г. Алгоритмы компактного размещения технологического оборудования на параллельных линиях / Г. Г. Забудский, И. В. Амзин // Сиб. журн. индустр. матем. – 2013. –16:3 (55). – С. 86–94.Zabudskii G.G., Amzin I.V. Algorithms of compact location for technological equipment on parallel lines, Sib. Zh. Ind. Mat., 2013, 16(3), pp. 86-94.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.Mukhacheva E.A., Zalgaller V.A. Linear programming cutting problems. Intern. J. of Software Engineering and Knowledge Engineering, 1993, vol. 3, no. 4, pp. 463- 476.Мухачева, Э. А. Метод динамического перебора в задаче двумерной упаковки / Э. А. Мухачева, А. Ф. Валеева // Информационные технологии. – 2000. – № 5. – С. 30-37.Muhacheva E.A., Valeeva A.F. Metod dinamicheskogo perebora v zadache dvumernoj upakovki [Method of dynamic search in a problem of two-dimensional packing]. Informacionnye tehnologii [Information technologies], 2000, no. 5, pp. 30-37.Руднев, А. С. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу / А. С. Руднев // Дискрет. анализ и исслед. операций. – 2009. – Т. 16, № 4. – С. 61-86.Rudnev A.S. Probabilistic tabu search algorithm for the packing circles and rectangles into the strip. Diskret. Anal. Issled. Oper., 2009, 16(4), pp. 61–86.Математическая модель оптимизации гибких модулей технологического оборудования / Г.Г. Забудский, С. А. Лёгких // Прикл. математика и информ. технологии : сб. науч. и метод. трудов. – Омск, 2005. – С. 20–28.Zabudskii G.G., Ljogkih S.A. Matematicheskaja model’ optimizacii gibkih modulej tehnologicheskogo oborudovanija [Mathematical model of optimization of flexible modules of processing equipment]. Prikl. matematika i inform. Tehnologii [Appl. Math. Inf. Technol.]: Sb. nauch. i metod. trudov., izd. OmGTU, Omsk, 2005, pp. 20– 28.Wai-Kai Chen. The VLSI Handbook, CRC Press, 2000. 1975 p.Wai-Kai Chen. The VLSI Handbook, CRC Press, 2000. 1975 p.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.Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979; Mir, Moscow, 1982. 338 p.

The authors declare that there are no conflicts of interest present.