Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2016, 10:1, 136-144
Volume 23, No 1, 2016, P. 82-96
UDC 519.854
G. G. Zabudsky and N. S. Veremchuk
An algorithm for approximate solution to the Weber problem on a line with forbidden gaps
Abstract:
The location problem of interconnected facilities on a line with forbidden gaps is considered. The properties of the problem which allow the initial continuous problem to be reduced to the discrete problem are found. The approximate algorithm for solving the problem is developed and the results of computational experiments are presented.
Tab. 1, bibliogr. 15.
Keywords: location problem, interconnected facilities, approximate decision.
DOI: 10.17377/daio.2016.23.489
Gennady G. Zabudsky 1
Natalia S. Veremchuk 1
1. Omsk department of S. L. Sobolev Institute of Mathematics, SB RAS,
13 Pevtsov St., 644099 Omsk, Russia
e-mail: zabudsky@ofim.oscsbras.ru, n-veremchuk@rambler.ru
Received 29 April 2015
Revised 10 August 2015
References
[1] E. N. Goncharov and Yu. A. Kochetov, Probabilistic search with exclusions for discrete unconstrained optimization, Diskretn. Anal. Issled. Oper., Ser. 2, 9, No. 2, 13–30, 2002.[2] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982.
[3] A. I. Erzin and J. D. Cho, Concurrent placement and routing in the design of integrated circuits, Avtom. Telemekh., No. 12, 177–190, 2003. Translated in Autom. Remote Control, 64, No. 12, 1988–1999, 2003.
[4] G. G. Zabudskii and I. V. Amzin, Algorithms of compact location for technological equipment on parallel lines, Sib. Zh. Ind. Mat., 16, No. 3, 86–94, 2013.
[5] G. G. Zabudskii and N. S. Veremchuk, Algorithms of approximate solution of the Weber problem on a line with forbidden gaps, in Materialy XV Vserossiiskoi konferentsii ”Matematicheskoe programmirovanie i prilozheniya” (Proc. XV All-Russian Conf. “Mathematical Programming and Applications”), Ekaterinburg, Russia, Mar. 2–6, 2015, p. 133, IMM UrO RAN, Ekaterinburg, 2015.
[6] E. A. Mukhacheva, The review and prospects of development of combinatorial methods for solution of cutting and packing problems, in Materialy rossiiskoi konferentsii “Diskretnaya optimizatsiya i issledovanie operatsii” (Proc. Russian Conf. “Discrete Optimization and Operation Research”), Novosibirsk, Russia, June 24–28, 2002, pp. 80–87, Izd. Inst. Mat., Novosibirsk, 2002.
[7] A. V. Panyukov, The problem of locating rectangular plants with minimal cost for the connecting network, Diskretn. Anal. Issled. Oper., Ser. 2, 8, No. 1, 70–87, 2001.
[8] A. S. Rudnev, Probabilistic tabu search algorithm for the packing circles and rectangles into the strip, Diskretn. Anal. Issled. Oper., 16, No. 4, 61–86, 2009.
[9] Yu. G. Stoyan and S. V. Yakovlev, Matematicheskie modeli i optimizatsionnye metody geometricheskogo proektirovaniya (Mathematical Models and Optimization Methods in Geometric Design), Naukova Dumka, Kiev, 1986.
[10] V. A. Trubin, Effective algorithm for the Weber problem with a rectangular metric, Kibern., No. 6, 67–70, 1978. Translated in Cybern., 14, No. 6, 874–878, 1978.
[11] L. Cheng and M. D. F. Wong, Floorplan design for multi-million gate FPGAs, in Proc. 2004 IEEE/ACM Int. Conf. Comput.-Aided Des., San Jose, CA, USA, Nov. 7–11, 2004, pp. 292–299, IEEE Comput. Soc., Washington, DC, USA, 2004.
[12] J. Cong, A. Jagannathan, G. Reinman, and M. Romesis, Microarchitecture evaluation with physical planning, in Proc. 40th Annual Des. Autom. Conf., Anaheim, USA, June 2–6, 2003, pp. 32–35, ACM, New York, 2003.
[13] A. B. Kahng, Classical floorplanning harmful?, in Proc. 2000 Int. Symp. Phys. Des., San Diego, USA, Apr. 9–12, 2000, pp. 207–213, ACM, New York, 2000.
[14] D. M. Simmons, One-dimensional space allocation: An ordering algorithm, Oper. Res., 17, No. 5, 812–826, 1969.
[15] G. Suresh and S. Sahu, Multiobjective facility layout using simulated annealing, Int. J. Prod. Econ., 32, No. 2, 239–254, 1993.
