SEARCH OF LOCAL MINIMUM IN LOCATION PROBLEM OF RECTANGLES ON LINES
https://doi.org/10.26518/2071-7296-2017-1(53)-122-128
Abstract
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.
About the Author
N. S. Veremchuk
Sobolev Institute of Mathematics Siberian Branch of RAS
Russian Federation
Russian Federation
Post-Graduate Student
644043, Russia, Omsk, Pevtsova St., 13
References
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. CEUR-WS.org, online: http://ceur-ws.org/Vol-1623/paperco17.pdf
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
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 NP-Completeness. Freeman, San Francisco, 1979; Mir, Moscow, 1982. 338 p.
Review
For citations:
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
Views:
809
Email this article 