=Paper=
{{Paper
|id=Vol-1623/paperco17
|storemode=property
|title=About Local Optimum of the Weber Problem on Line with Forbidden Gaps
|pdfUrl=https://ceur-ws.org/Vol-1623/paperco17.pdf
|volume=Vol-1623
|authors=Gennady Zabudsky, Natalia Veremchuk
|dblpUrl=https://dblp.org/rec/conf/door/ZabudskyV16
}}
==About Local Optimum of the Weber Problem on Line with Forbidden Gaps==
https://ceur-ws.org/Vol-1623/paperco17.pdf
About Local Optimum of the Weber Problem
on Line with Forbidden Gaps
Gennady Zabudsky⋆ and Natalia Veremchuk
Sobolev Institute of Mathematics Siberian Branch of RAS, Omsk, Russia
zabudsky@ofim.oscsbras.ru,n-veremchuk@rambler.ru
Abstract. The location problem of interconnected facilities on the line with
forbidden gaps is considered. The located facilities are connected among them-
selves and with gaps. Location in forbidden gaps is not allowed. It is need to
minimize the total cost of connections between facilities and between facilities
and gaps. It is known that the initial continuous problem is reduced to series
discrete subproblems of smaller dimension. In this paper the definition of the
local optimum of the problem is introduced. In order that to obtain the local op-
timum it is necessary to solve some subproblems. The variants of lower bounds
of the goal function of the subproblems are proposed. The bounds can be used
in the branch and bounds algorithm for solving the subproblems.
Keywords: forbidden gaps, local optimum, lower bounds, Weber problem
1 Introduction
The analysis and decision of location problems are intensively developing directions in
operations research [2, 4, 5, 17, 18]. Problems of such class have important applications
and arise in various fields of activity: at designing of master plans of the enterprisers,
arrangement of processing equipment in shops, definition of the locations of the service
stations, etc. The various statements of such problems are defined by size of facilities,
area in which they are located, various restrictions and types of criteria and so on.
An important subclass of the location problems of the interconnected facilities is the
Weber problem with criterion of minimum of total cost of connections [8, 12, 17, 18].
The Weber problem is an adequate model of many practical applications. For example,
in automation of design of the complex systems can be the problem of placement of
structural elements in the area with implementation of certain requirements [7, 16]. At
designing of the plan of the petrochemical enterprise the facilities are the equipment [7,
16]. The equipment can be connected among themselves by various communications,
for example, systems of the pipelines. Regularity of location often is required to ensure
the straightforward paths and convenient maintenance along so-called “red” lines [15].
⋆
This work was supported by grant 16–01–00740 from the Russian Foundation for Basic
Research.
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
116 G. Zabudsky and N. Veremchuk
The Weber problem with restrictions on facility location and/or traveling has been
considered widely in recent years [4, 6]. Depending on the type of restrictions, such
problems are divided into three categories. The category considers planar facility lo-
cation problems in which restrictions come from existence of forbidden regions (gaps).
Forbidden gaps refer to prohibition of facility placement but allowance of free travel-
ing. Moreover, some forbidden gaps may contain the equipment, for example, during
modernization of the enterprise. In the second category, restrictions are imposed by
barriers. Barriers are defined as regions where neither locating a facility on not passing
through is allowed. The last category considers restricted planar location problems with
congested regions. Congested regions are bounded areas in the plane that forbid facility
location however passing through their interior is possible at some extra traveling cost.
A broad overview on facility location problems with forbidden gaps is provided in [6].
If the facilities are commensurable to the area of location then they often are ap-
proximated by the rectangles; otherwise, we may consider them as material points.
Various approaches to the problem of optimal location of the rectangles are developed
[1, 8–10, 13, 15]. In case the rectangles are unconnected, the two–dimensional problem
of packing of the rectangles into the strip of the minimal length is considered in [9]. The
problem is formulated as a mixed integer nonlinear programming problem. For solving
this problem the probabilistic tabu search algorithm is developed. In [15] the location
problem of the rectangles on the parallel lines is considered. For constructing a set of
Pareto–optimal solutions, integer optimization and dynamic programming are applied.
In [8, 10], the algorithms of local optimization on the plane and dynamic programming
on the line without forbidden gaps are described. For the problem in which the rect-
angles can be rotated and it is possible to create routes for establishing connections,
the heuristic algorithm is proposed [1]. An important subclass of problems of optimal
location of rectangles is the VLSI chip design problems. The wide review of practical
applications and various approaches for solving such problems is provided in [13].
In this paper, we study the Weber problem on the line with forbidden gaps. The
located facilities are segments, for example, projection of the rectangles onto the line. It
is known that the initial continuous problem is reduced to series discrete subproblems of
smaller dimension. All subproblems have identical structure. The local optimum of the
problem is obtained by solving some subproblems. The variants of lower bounds of the
goal function of the subproblems are proposed. The bounds can be used in algorithms
for solving of the subproblems, for example, in the branch and bounds algorithm.
2 Problem Formulation and Basic Properties
The Weber problem on the line with forbidden gaps is formulated as follows. Consider
a straight–line segment of length LS containing some fixed rectilinear areas (forbidden
gaps). It is necessary to locate on this line facilities which are the segments, whose
centers are connected with each other and with the forbidden gaps. Location in forbid-
den gaps is not allowed. The problem is to locate facilities on the segment of length
LS outside the forbidden gaps so that they do not intersect each other and, moreover,
the total cost of connections between the facilities and between facilities and gaps is
About Local Optimum of the Weber Problem 117
minimized [17]. Without loss of generality, we can assume that the left border of the
segment of length LS is the origin.
Let Xi and Fj denote the facilities and gaps with the centers at xi and bj and
lengths of li and pj , where i ∈ I = {1, . . . , n} and j ∈ J = {1, . . . , m}; while wij ≥ 0,
uik ≥ 0 are the specific costs of connections between Xi and Fj , Xi and Xk for i,
k ∈ I, j ∈ J, and i < k. The target is to locate the facilities X1 , . . . , Xn on the segment
outside gaps F1 , . . . , Fm and so that they do not intersect with each other and the
total cost of the connections between the facilities and between facilities and gaps is
minimized.
The mathematical model under consideration is as follows:
∑
n ∑
m ∑
n−1 ∑
n
G(x) = wij |xi − bj | + uik |xi − xk | → min, (1)
i=1 j=1 i=1 k=i+1
li + pj
|xi − bj | ≥ , i ∈ I, j ∈ J, (2)
2
li + lk
|xi − xk | ≥ , i, k ∈ I, i < k, (3)
2
li li
≤ xi ≤ LS − , i ∈ I. (4)
2 2
The first component in (1) defines the total cost of connections between facilities and
gaps; the second part defines the total cost of connections between the facilities them-
selves; and (2) and (3) are the conditions of disjointness.
The feasible area B is disconnected and consists of the set of r disjoint ∪ segments
(blocks) Bk of length Lk that contain the facilities Xi , i ∈ I, B = k=1,r Bk . The
problem (1)–(4) is NP-hard; a feasible solution to the problem can be found by con-
struction of a one–dimensional packing into containers [3]. In this case, the facilities
with lengths of li , i ∈ I, are packed into containers with sizes Lk , k = 1, r. Moreover,
if there are no gaps then (1)–(4) is an optimal linear ordering problem [11] which is
NP-hard for an arbitrary set of connections between the facilities.
In [17] the algorithm for obtaining an approximate decision in two phases is of-
fered. In the first phase, we find an feasible partition of the facilities into blocks, and in
the second phase, the facilities in the blocks are interchanged for the purpose of mini-
mization of total cost of connections. A computational experiment with this algorithm
and solving of the problem using IBM ILOG CPLEX and a mixed-integer linear pro-
gramming model is considered. This work is continuation of researches of the problem
(1)–(4).
Given a feasible location, a remainder in the block Bk is a segment between two
adjacent facilities that do not have a common border or between the border of Bk
and an adjacent block. A block without facilities is called a block with remainder. Two
elements (facilities, gaps, remainders) are called glued if they have a common border.
Let JL (Bk ) and JR (Bk ) denote the set of gaps to the left and to the right of the
block Bk , let IL (A) and IR (A) denote the set of facilities to the left and to the right of
118 G. Zabudsky and N. Veremchuk
the block (gap) A correspondingly. Given an facility Xi in Bk , let Lwi and Rwi denote
the total cost of connections for Xi defined as
∑ ∑ ∑ ∑
Lwi = wij + uik , Rwi = wij + uik .
j∈JL (Bk ) k∈IL (Bk ) j∈JR (Bk ) k∈IR (Bk )
Let x = (x1 , . . . , xn ) be a feasible solution of (1)–(4) that uniquely defines the partition
of X1∪, . . . , Xn into blocks. Let Ik (x) denote the set of the facility’s numbers in Bk ,
I = k=1,r Ik (x), and let Hk (x) denote the set of remainders in Bk for x. Let nk
denote the size of set Ik (x), then |Hk (x)| ≤ nk + 1. Note that x can be represented
as x = (x1 , . . . , xr ), where xk is the coordinates of the centers of the facilities that are
located in Bk and have numbers from Ik (x).
Proposition 1. (see [17]) Given a feasible solution x of (1)–(4), we can find a feasible
solution x′ such that
|Hk (x′ )| ≤ 1, k = 1, . . . , r, G(x′ ) ≤ G(x).
Thus in each block Bk it is possible to consider no more than one remainder, length
of which we denote by ∆k .
Let LBk and RBk denote the coordinates of the left and right borders of Bk . Then,
for a fixed partition of facilities into blocks, the goal function G(x) can be presented as
∑
r
G(x) = Gk (xk ) + C, (5)
k=1
where
∑ ∑ ∑ ( ∑
Gk (xk ) = ust |xs − xt | + |xs − LBk | wsj +
s∈Ik (x) t∈Ik (x),t>s s∈Ik (x) j∈JL (Bk )
∑ ) ∑ ( ∑ ∑ )
+ usi + |xt − RBk | wtj + uti ,
i∈IL (Bk ) t∈Ik (x) j∈JR (Bk ) i∈IR (Bk )
C is some constant.
The first component of Gk (xk ) is the sum of costs of connections between the
facilities in Bk , the second is the total cost of connections between the facilities from
Bk and LBk , and the third component is the total cost of connections between the
facilities from Bk and RBk . In the case when the area of location on the segment is
bounded on the left and on the right by gaps, we have
∑ ( ∑
1 ∑ ∑
m−1
1
C = p1 wk1 + pj wkj + wkj +
2 2 j=2
k∈IR (F1 ) k∈IL (Fj ) k∈IR (Fj )
∑ ∑ ∑ ∑ ∑ ∑ )
+2 wkt + 2 wks + 2 ukt +
k∈IL (Fj ) t∈J,t>j k∈IR (Fj ) s∈J,ss s∈Ik (x)
∑
+ wtR |xt − RBk | → min, (6)
t∈Ik (x)
li + lk
|xi − xk | ≥ , i, k ∈ Ik (x), i < k, (7)
2
li li
LBk + ≤ xi ≤ RBk − , i ∈ Ik (x). (8)
2 2
It is need to find coordinates xk of the centers facilities in Bk , so that the total cost
of connections between located facilities among themselves and with FL and FR is
minimized. ∩
As Ik (x) Il (x) = ∅ for all k, l = 1, . . . , r, then to find a local optimum for some
fixed partition of the facilities into blocks, it is sufficiently to find the minimum in r
independent subproblems (6)–(8). These subproblems have identical structure.
Proposition 2. For search of the local minimum of the problem (1)–(4) it is suffi-
ciently to solve r subproblems (6)–(8).
The proof of proposition 2 follows from representation of the goal function (5).
Note that the process of search of the local minimum can be parallelized as solving
r independent subproblems (6)–(8).
The properties stated above allowed to reduce the initial continuous problem to
series of discrete subproblems of smaller dimension. For finding of the local optimum
of the problem it is need to solve r subproblems.
120 G. Zabudsky and N. Veremchuk
Solving of the problem (1)–(4) is sequential performance of two phases. In the first
phase, we find feasible partition of the facilities into blocks by means of the algorithm
[17]. In the second phase, for obtained partition the series of the subproblems of smaller
dimension are solved. Thus we fined the local optimum of the problem (1)–(4). The
local optimum with minimal value of the goal function is the exact decision of the
problem (1)–(4). For the search of approximate decision of the problem (1)–(4) the
stopping criteria of the algorithm may be running time, number of iterations, finding
of the exact decision or given estimate of accuracy. Note that the number of possible
partitions Xi , i ∈ I into the blocks B1 , . . . , Br is at most rn . The remainder in Bk
can be considered as the additional located facility Xnk +1 , for which lnk +1 = ∆k and
Lwnk +1 = Rwnk +1 = 0.
Note that if ust = 0, ∀s, t ∈ Ik (x), s < t, then in the second phase the exact decision
for the subproblem (6)–(8) is found by the polynomial algorithm [17]. In this case the
graph, whose tops are the left and the right borders of the block Bk and the facilities
in Bk , has a series–parallel type with one top on each chain between the source and
the sink. For such structure of the graph the effective algorithm is offered in [14].
Generally, if ∃s, t ∈ Ik (x) : ust > 0, then for solving the subproblem (6)–(8) for
small value nk , it is possible to use nk ! permutations of the facilities into block. In
general case it is possible to apply, for example, the branch and bounds algorithm. In
the algorithm calculation of the lower bounds of the goal function is important.
3 Lower Bounds
Let some located facilities in Bk are glued to the left border of Bk , some located facilities
are glued to the right border of Bk , and some facilities aren’t located yet. Denote
∪ by
N Fl , N Fr the sets of the located facility’s numbers in Bk , then Ik (x)\{N Fl N Fr } is
the set of the unlocated facility’s numbers. Without loss of generality, we shall consider
that the facilities in the set N Fl have numbers from 1 to s, and in the set N Fr the
facility’s numbers are from t + 1 to nk . Denote by D the set of the admissible locations
of the facilities in Bk when N Fl and N Fr are defined (partial location). Let ξ(D) be
the lower bound of function Gk (xk ) for the set D. Then ξ(D) can be presented as the
sum of three components. The first component ξ1 (D) is the total cost of connections
between the located facilities themselves and with FL and FR . The second component
ξ2 (D) is lower bound of total cost of connections the unlocated facilities with FL , FR
and with the located facilities in Bk . The third component ξ3 (D) is lower bound of
total cost of connections between the unlocated facilities themselves. Thus ξ(D) can
be presented as
ξ(D) = ξ1 (D) + ξ2 (D) + ξ3 (D).
The coordinates of the centers of the located facilities are known and ξ1 (D) can be
calculated as follows
∑ ∑ ∑
ξ1 (D) = ust |xs − xt | + |xs − LBk |·
∪ ∪ ∪
s∈{N Fl N Fr } t∈{N Fl N Fr },t>s s∈{N Fl N Fr }
( ∑ ∑ ) ∑ ( ∑ ∑ )
· wsj + usi + |xt − RBk | wtj + uti .
∪
j∈JL (Bk ) i∈IL (Bk ) t∈{N Fl N Fr } j∈JR (Bk ) i∈IR (Bk )
About Local Optimum of the Weber Problem 121
Further two variants of calculation ξ2 (D) are∪offered.
The first variant. For each i ∈ Ik (x)\{N Fl N Fr } the total cost of connections
between the located facilities themselves and with FL and FR is determined as follows
∑ ∑
SL(i) = Lwi + uik , SR(i) = Rwi + uik .
k∈N Fl k∈N Fr
Further location of the unlocated facilities in Bk is defined in two ways. In the first
way, the facilities are ordered by not increase of the relations SL(i)/li . The facilities
consistently are pasted together in that order with the most left located facility in Bk .
Let, for simplicity of designations, the glued unlocated facilities have numbers from
s + 1 to t.
In the second way, the unlocated facilities are ordered by not increase of the relations
SR(i)/li . The facilities consistently are pasted together in that order with the most
right located facility in Bk . Let the glued unlocated facilities have numbers from t to
s + 1. Then
ξ2 (D) = ξ2L (D) + ξ2R (D),
where ξ2L (D) and ξ2R (D) are the lower bounds of total cost of the connections unlo-
cated facilities with FL , FR respectively and with the located facilities in Bk .
In both cases we receive some permutation π of facilities in the block Bk . Consider
the permutation π and two distinct facilities Xi and Xj in Bk . The distance between
Xi and Xj with respect to this permutation, assumed to be taken their centers, is equal
to the half-length of Xi , plus the lengths lk of all facilities which are between Xi and
Xj in π, plus the half-length of Xj . The half-length of Xi plus the half-length of Xj is
the constant. Thus, at the calculation of the distance between the facilities Xi and Xj
it is sufficient to consider only the lengths lk of all facilities which are between Xi and
Xj in π. Then ξ2L (D) and ξ2R (D) can be calculated as follows:
t (
∑ ∑
q−1 ∑
s ∑
q−1 )
ξ2L (D) = Lwq lg + uqi lk ,
q=s+1 g=1 i=1 k=i+1
t (
∑ ∑
nk ∑
nk ∑
i−1 )
ξ2R (D) = Rwq lg + uqi lk .
q=s+1 g=q+1 i=t+1 k=q+1
The proof that ξ2L (D) and ξ2R (D) are the lower bounds of the total cost of connections
unlocated facilities with FL , FR and with the located facilities in Bk is similar to the
proof in [10]. ∪
The second variant.
∪ ∪The set Ik (x)\{N Fl N Fr } can be presented as union of non–
crossing sets NL NC NR , where by NL , NC , NR are denoted the sets of facility’s
numbers for which SL(i) > SR(i), SL(i) = SR(i), SL(i) < SR(i) respectively.
Further facilities with numbers from NL are ordered by not increase of the relations
(SL(i) − SR(i))/li . The facilities consistently are pasted together in that order with
the most left located facility in Bk . The facilities with numbers from NR are ordered
by not increase of the relations (SR(i) − SL(i))/li , and they consistently are pasted
together in that order with the most right located facility. The facilities with numbers
122 G. Zabudsky and N. Veremchuk
from NC are located between sets of the facilities with numbers from NL and from NR
in any order. ∪
Thus, for∪each i ∈ Ik (x)\{N Fl N Fr } coordinate of the center is determined. Let
Ik (x)\{N Fl N Fr } = {s + 1, . . . , t} as well as earlier. Determine the following value
Z as
t (
∑ ∑
q−1 ∑
s ∑
q−1 ∑
nk ∑
nk ∑
j−1 )
Z= Lwq lg + uqi lk + Rwq lh + uqj lv . (9)
q=s+1 g=1 i=1 k=i+1 h=q+1 j=t+1 v=q+1
Proposition 3. The value Z is the lower bound of the total cost of connections the
unlocated facilities with FL , FR and with the located facilities in Bk .
Proof. Let NL ̸= ∅ and NR = ∅ and NC = ∅. Without loss of generality, we consider
the case when N Fl = ∅ and N Fr = ∅. Otherwise it is possible to redefine the cost of
connections the unlocated facilities with FL , FR and with the located facilities. Then
the set of the unlocated facility’s numbers is Ik (x) and Lwi > Rwi for each i ∈ Ik (x).
Let (Lw1 − Rw1 )/l1 > . . . > (Lwnk − Rwnk )/lnk , then the facilities are located in
order X1 , . . . , Xnk according to the second variant of the calculation ξ2 (D). Denote
by Π ∗ = (1, . . . , nk ) the permutation of numbers facilities corresponding to order
X1 , . . . , Xnk and denote by Z(Π ∗ ) the value Z for Π ∗ . On the formula (9) we receive
Z(Π ∗ ) = Lw2 l1 + . . . + Lwt (l1 + . . . + lt−1 ) + Lwt+1 (l1 + . . . + lt ) +
+ . . . + Lwnk (l1 + . . . + lnk −1 ) + Rw1 (l2 + . . . + lnk ) + . . . +
+Rwt (lt+1 + . . . + lnk ) + Rwt+1 (lt+2 + . . . + lnk ) + . . . + Rwnk −1 lnk .
To prove that Z(Π ∗ ) is the lower bound for Z(Π), where Π is any permutation of
numbers facilities from Ik (x). Assume, that Z(Π ∗ ) is not minimum. Then there is other
permutation Π, such that Z(Π ∗ ) > Z(Π). Any permutation can be received by series of
transposition of adjacent numbers, then it is sufficiently to consider the proof for change
the position of two adjacent facilities. Denote by Π = (1, . . . t − 1, t + 1, t, t + 2, . . . , nk ),
then on the formula (9) we receive
Z(Π) = Lw2 l1 + . . . + Lwt+1 (l1 + . . . + lt−1 ) + Lwt (l1 + . . . + lt−1 + lt+1 ) +
+ . . . + Lwnk (l1 + . . . + lnk −1 ) + Rw1 (l2 + . . . + lnk ) + . . . +
+Rwt+1 (lt + lt+2 + . . . + lnk ) + Rwt (lt+2 + . . . + lnk ) + . . . + Rwnk −1 lnk .
By assumption Z(Π ∗ ) − Z(Π) > 0, then
Z(Π ∗ ) − Z(Π) = Lw2 l1 + . . . + Lwt (l1 + . . . + lt−1 ) + Lwt+1 (l1 + . . . + lt ) +
+ . . . + Lwnk (l1 + . . . + lnk −1 ) + Rw1 (l2 + . . . + lnk ) + . . . +
+Rwt (lt+1 + . . . + lnk ) + Rwt+1 (lt+2 + . . . + lnk ) + . . . + Rwnk −1 lnk −
−Lw2 l1 − . . . − Lwt+1 (l1 + . . . + lt−1 ) − Lwt (l1 + . . . + lt−1 + lt+1 ) − . . . −
−Lwnk (l1 + . . . + lnk −1 ) − Rw1 (l2 + . . . + lnk ) − . . . −
About Local Optimum of the Weber Problem 123
−Rwt+1 (lt + lt+2 + . . . + lnk ) − Rwt (lt+2 + . . . + lnk ) − . . . − Rwnk −1 lnk =
= (Lwt+1 − Rwt+1 )lt − (Lwt − Rwt )lt+1 > 0.
Hence
Lwt+1 − Rwt+1 Lwt − Rwt
> .
lt+1 lt
It is the contradiction with inequalities (Lw1 − Rw1 )/l1 > . . . > (Lwt − Rwt )/lt >
(Lwt+1 − Rwt+1 )/lt+1 > . . . > (Lwnk − Rwnk )/lnk .
The proof for the subset NR ̸= ∅ is similarly. Note that facilities with numbers from
NC can be located in arbitrary order.
Proposition is proved.
Therefore, in the capacity of ξ2 (D) it is possible to use the value Z.
Following way may ∪ be use for the calculation of ξ3 (D). Let for the facilities Xs , Xt , Xq ,
s, t, q ∈ Ik (x)\{N Fl N Fr } take place inequalities ust > 0, usq > 0, utq > 0. Consid-
ering any three of the interconnected facilities, value of ξ3 (D) can be calculated, for
example, as follows
∑
ξ3 (D) = min{ust lq ; usq lt ; utq ls }.
∪
s,t,q∈Ik (x)\{N Fl N Fr }
4 Conclusion
The NP–hard location problem of interconnected facilities on the line with forbidden
gaps is considered. It is need to minimize the total cost of connections between the
facilities and between the facilities and gaps. It is known that the initial continuous
problem is reduced to series discrete subproblems of smaller dimension. For finding of
the local optimum of the problem it is need to solve some subproblems. Two variants
of lower bounds of the goal function of the subproblems are proposed. The bounds can
be used in the branch and bounds algorithm for solving the subproblems.
References
1. Erzin, A., I., Cho, J., D.: Concurrent Placement and Routing in the Design of Integrated
Circuits. Avtomat. i Telemekh. No. 12, 177–190 (2003) [Automat. Remote Control 64(12),
1988–1999 (2003)]
2. Farahani, R., Z., Hekmatfar, M.: Facility location: Concepts, models, algorithms and case
studies. Heidelberg: Physica-Verlag, (2009)
3. Garey, M., R., Johnson ,D., S.: Computers and Intractability: A Guide to the Theory of
NP–Completeness. (Freeman, San Francisco, 1979; Mir, Moscow, 1982)
4. Klamroth, K.: Single-Facility Location Problems with Barriers. Springer Series in Oper-
ations Research, (2002)
5. Kochetov, Yu., A., Panin, A., A., Plyasunov, A., V.: Comparison of metaheuristics for
the bilevel facility location and mill pricing problem. Diskret. Anal. Issled. Oper. 22(3),
36-54 (2015) DOI: 10.17377/daio.2015.22.465
6. Nickel, S., Puerto, J.: Location theory. A unified approach. Berlin: Springer, (2005)
124 G. Zabudsky and N. Veremchuk
7. Legkih, S., A., Nagornay, Z., E., Zabudsky, G., G.: Automation of design of plans of
production sites and shops of the sewing enterprises (in Russian). Nat. Tech. Scien. No. 4,
pp. 261–266 (2005)
8. Panyukov, A., V.: The problem of locating rectangular plants with minimal cost for the
connecting network. Diskret. Anal. Issled. Oper. Ser. 2, 8(1), 70–87 (2001)
9. Rudnev, A., S.: Probabilistic tabu search algorithm for the packing circles and rectangles
into the strip. Diskret. Anal. Issled. Oper. 16(4), 61–86 (2009)
10. Simmons, D., M.: One-dimensional space allocation: an ordering algorithm. Oper. Res.
17(5), 812–826 (1969)
11. Suresh, G., Sahu, S.: Multiobjective Facility Layout Using Simulated Annealing. Int. J.
Prod. Econom. 32(2), 239–254 (1993)
12. Trubin, V., A.: Effective algorithm for Weber problem with a rectangular metrics. Kiber-
net. No. 6, 67–70 (1978) [Cybernetics 14(6), 874–878 (1978)]
13. Wai–Kai, Chen: The VLSI Handbook. CRC Press. (2000)
14. Zabudsky, G., G.: On the problem of the linear ordering of vertices of parallel-sequential
graphs. Diskret. Anal. Issled. Oper. 7(1), 61-64 (2000)
15. Zabudskii, G., G., Amzin, I., V.: Algorithms of compact location for technological equip-
ment on parallel lines (in Russian). Sib. Zh. Ind. Mat. 16(3), 86–94 (2013)
16. Zabudsky, G., G., Legkih, S., A.: Mathematical model of optimization of flexible modules
of processing equipment (in Russian). Appl. Math. Inf. Technol. Omsk: Publishing House
of OMGTU, pp.20–28 (2005)
17. Zabudskii, G., G., Veremchuk, N., S.: An Algorithm for Finding an Approxi-
mate Solution to the Weber Problem on a Line with Forbidden Gaps. Diskret.
Anal. Issled. Oper. 23(1), 82-96 (2016) [J. Appl. Ind. Math. 10(1), 136–144 (2016)
DOI: 10.1134/S1990478916010154]
18. Zabudsky, G., G., Veremchuk, N., S.: Solving Weber problem on plane with minimax
criterion and forbidden gaps (in Russian). IIGU Ser. Matematika, Vol. 9, pp. 10–25 (2014)