Location of regional facilities

In this paper we consider the single-facility and multifacility problems of the minisum type of locating facilities on the plane. Both demand locations and the facilities to be located are assumed to have circular shapes, and demand and service is assumed to have a uniform probability density inside each shape. The expected distance between two facilities is calculated. Euclidean and squared-Euclidean distances are discussed.     

An iterative algorithm for the multifacility minimax location problem with euclidean distances

An iterative solution method is presented for solving the multifacility location problem with Euclidean distances under the minimax criterion. The iterative procedure is based on the transformation of the multifacility minimax problem into a sequence of squared Euclidean minisum problems which have analytical solutions. Computational experience with the new method is also presented.     

A note on equity across groups in facility location

An equity model between groups of demand points is proposed. The set of demand points is divided into two or more groups. For example, rich and poor neighborhoods and urban and rural neighborhoods. We wish to provide equal service to the different groups by minimizing the deviation from equality among groups. The distance to the closest facility is a measure of the quality of service. Once the facilities are located, each demand point has a service distance. The objective function, to be minimized, is the sum of squares of differences between all pairs of service distances between demand points in different groups. The problem is analyzed and solution techniques are proposed for the location of a single facility in the plane. Computational experiments for problems with up to 10,000 demand points and rectilinear, Euclidean, or general ?_p distances illustrate the efficiency of the proposed algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

New heuristic methods for the capacitated multi‐facility Weber problem

In this paper we consider the capacitated multi‐facility Weber problem with the Euclidean, squared Euclidean, and ?_p‐distances. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the distance between them. We first present a mixed integer linear programming approximation of the problem. We then propose new heuristic solution methods based on this approximation. Computational results on benchmark instances indicate that the new methods are both accurate and efficient. © 2006 Wiley Periodicals, Inc. Naval Research Logistics 2006     

Minimax and maximin facility location problems on a sphere

The problem dealt with in this article is as follows. There are n “demand points” on a sphere. Each demand point has a weight which is a positive constant. A facility must be located so that the maximum of the weighted distances (distances are the shortest arcs on the surface of the sphere) is minimized; this is called the minimax problem. Alternatively, in the maximin problem, the minimum weighted distance is maximized. A setup cost associated with each demand point may be added for generality. It is shown that any maximin problem can be reparametrized into a minimax problem. A method for finding local minimax points is described and conditions under which these are global are derived. Finally, an efficient algorithm for finding the global minimax point is constructed.     

Location of facilities with rectangular distances among point and area destinations

This article is concerned with the optimal location of any number (n) of facilities in relation to any number (m) of destinations on the Euclidean plane. The criterion to be satisfied is the minimization of total weighted distances where the distances are rectangular. The destinations may be either single points, lines or rectangular areas. A gradient reduction solution procedure is described which has the property that the direction of descent is determined by the geometrical properties of the problem.     

Bounding methods for facilities location algorithms

Single- and multi-facility location problems are often solved with iterative computational procedures. Although these procedures have proven to converage, in practice it is desirable to be able to compute a lower bound on the objective function at each iteration. This enables the user to stop the iterative process when the objective function is within a prespecified tolerance of the optimum value. In this article we generalize a new bounding method to include multi-facility problems with l_p distances. A proof is given that for Euclidean distance problems the new bounding procedure is superior to two other known methods. Numerical results are given for the three methods.     

Sensitivity analysis of the optimal location of a facility

We perform a sensitivity analysis of the Euclidean, single-facility minisum problem, which is also known as the Weber problem. We find the sensitivity of the optimal site of the new facility to changes in the locations and weights of the demand points. We apply these results to get the optimal site if some of the parameters in the problem are changed. We also get approximate formulas for the set of all possible optimal sites if demand points are restricted to given areas, and weights must be within given ranges, which is a location problem under conditions of uncertainty.     

Evaluating methods for the reliability of a large 2‐dimensional rectangular k‐within‐consecutive‐(r,s)‐out‐of‐(m,n):F system

A 2‐dimensional rectangular k‐within‐consecutive‐(r, s)‐out‐of‐(m, n):F system consists of m × n components, and fails if and only if k or more components fail in an r × s submatrix. This system can be treated as a reliability model for TFT liquid crystal displays, wireless communication networks, etc. Although an effective method has been developed for evaluating the exact system reliability of small or medium‐sized systems, that method needs extremely high computing time and memory capacity when applied to larger systems. Therefore, developing upper and lower bounds and accurate approximations for system reliability is useful for large systems. In this paper, first, we propose new upper and lower bounds for the reliability of a 2‐dimensional rectangular k‐within‐consecutive‐(r, s)‐out‐of‐(m, n):F system. Secondly, we propose two limit theorems for that system. With these theorems we can obtain accurate approximations for system reliabilities when the system is large and component reliabilities are close to one. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

On estimating population characteristics from record-breaking observations. i. parametric results

Consider an experiment in which only record-breaking values (e.g., values smaller than all previous ones) are observed. The data available may be represented as X₁,K₁,X₂,K₂, …, where X₁,X₂, … are successive minima and K₁,K₂, … are the numbers of trials needed to obtain new records. We treat the problem of estimating the mean of an underlying exponential distribution, and we consider both fixed sample size problems and inverse sampling schemes. Under inverse sampling, we demonstrate certain global optimality properties of an estimator based on the “total time on test” statistic. Under random sampling, it is shown than an analogous estimator is consistent, but can be improved for any fixed sample size.     

Easily computed approximations for (s,S) inventory system operating characteristics

The operating characteristics of (s,S) inventory systems are often difficult to compute, making systems design and sensitivity analysis tedious and expensive undertakings. This article presents a methodology for simplified sensitivity analysis, and derives approximate expressions for operating characteristics of a simple (s,S) inventory system. The operating characteristics under consideration are the expected values of total cost per period, holding cost per period, replenishment cost per period, backlog cost per period, and backlog frequency. The approximations are obtained by using least-squares regression to fit simple functions to the operating characteristics of a large number of inventory items with diverse parameter settings. Accuracy to within a few percent of actual values is typical for most approximations. Potential uses of the approximations are illustrated for several idealized design problems, including consolidating demand from several locations, and tradeoffs for increasing service or reducing replenishment delivery lead time.     

Duality in constrained multi‐facility location models

We consider the ??_p‐norm multi‐facility minisum location problem with linear and distance constraints, and develop the Lagrangian dual formulation for this problem. The model that we consider represents the most general location model in which the dual formulation is not found in the literature. We find that, because of its linear objective function and less number of variables, the Lagrangian dual is more useful. Additionally, the dual formulation eliminates the differentiability problem in the primal formulation. We also provide the Lagrangian dual formulation of the multi‐facility minisum location problem with the ??_pb‐norm. Finally, we provide a numerical example for solving the Lagrangian dual formulation and obtaining the optimum facility locations from the solution of the dual formulation. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 410–421, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10010     

Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

Openshop scheduling under linear resources constraints

Consider n jobs (J₁, …, J_n), m working stations (M₁, …, M_m) and λ linear resources (R₁, …, R_λ). Job J_i consists of m operations (O_i1, …, O_im). Operation O_ij requires P_k(i, j) units of resource R_k to be realized in an M_j. The availability of resource R_k and the ability of the working station M_h to consume resource R_k, vary over time. An operation involving more than one resource consumes them in constant proportions equal to those in which they are required. The order in which operations are realized is immaterial. We seek an allocation of the resources such that the schedule length is minimized. In this paper, polynomial algorithms are developed for several problems, while NP-hardness is demonstrated for several others. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 51–66, 1998     

Applications of renewal theory in analysis of the free-replacement warranty

Under a free-replacement warranty of duration W, the customer is provided, for an initial cost of C, as many replacement items as needed to provide service for a period W. Payments of C are not made at fixed intervals of length W, but in random cycles of length Y = W + γ(W), where γ(W) is the (random) remaining life-time of the item in service W time units after the beginning of a cycle. The expected number of payments over the life cycle, L, of the item is given by M_Y(L), the renewal function for the random variable Y. We investigate this renewal function analytically and numerically and compare the latter with known asymptotic results. The distribution of Y, and hence the renewal function, depends on the underlying failure distribution of the items. Several choices for this distribution, including the exponential, uniform, gamma and Weibull, are considered.     

A decomposable transshipment algorithm for a multiperiod transportation problem

A dynamic version of the transportation (Hitchcock) problem occurs when there are demands at each of n sinks for T periods which can be fulfilled by shipments from m sources. A requirement in period t₂ can be satisfied by a shipment in the same period (a linear shipping cost is incurred) or by a shipment in period t₁ < t₂ (in addition to the linear shipping cost a linear inventory cost is incurred for every period in which the commodity is stored). A well known method for solving this problem is to transform it into an equivalent single period transportation problem with mT sources and nT sinks. Our approach treats the model as a transshipment problem consisting of T, m source — n sink transportation problems linked together by inventory variables. Storage requirements are proportional to T² for the single period equivalent transportation algorithm, proportional to T, for our algorithm without decomposition, and independent of T for our algorithm with decomposition. This storage saving feature enables much larger problems to be solved than were previously possible. Futhermore, we can easily incorporate upper bounds on inventories. This is not possible in the single period transportation equivalent.     

Approximations for heavily loaded G/GI/n + GI queues

Motivated by applications to service systems, we develop simple engineering approximation formulas for the steady‐state performance of heavily loaded G/GI/n+GI multiserver queues, which can have non‐Poisson and nonrenewal arrivals and non‐exponential service‐time and patience‐time distributions. The formulas are based on recently established Gaussian many‐server heavy‐traffic limits in the efficiency‐driven (ED) regime, where the traffic intensity is fixed at ρ > 1, but the approximations also apply to systems in the quality‐and‐ED regime, where ρ > 1 but ρ is close to 1. Good performance across a wide range of parameters is obtained by making heuristic refinements, the main one being truncation of the queue length and waiting time approximations to nonnegative values. Simulation experiments show that the proposed approximations are effective for large‐scale queuing systems for a significant range of the traffic intensity ρ and the abandonment rate θ, roughly for ρ > 1.02 and θ > 2.0. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 187–217, 2016     

On computing the expected discounted return in a markov chain

The discounted return associated with a finite state Markov chain X₁, X₂… is given by g(X₁)+ αg(X₂) + α²g(X₃) + …, where g(x) represents the immediate return from state x. Knowing the transition matrix of the chain, it is desired to compute the expected discounted return (present worth) given the initial state. This type of problem arises in inventory theory, dynamic programming, and elsewhere. Usually the solution is approximated by solving the system of linear equations characterizing the expected return. These equations can be solved by a variety of well-known methods. This paper describes yet another method, which is a slight modification of the classical iterative scheme. The method gives sequences of upper and lower bounds which converge mono-tonely to the solution. Hence, the method is relatively free of error control problems. Computational experiments were conducted which suggest that for problems with a large number of states, the method is quite efficient. The amount of computation required to obtain the solution increases much slower with an increase in the number of states, N, than with the conventional methods. In fact, computational time is more nearly proportional to N², than to N³.     

A search game with a protector

A classic problem in Search Theory is one in which a searcher allocates resources to the points of the integer interval [1, n] in an attempt to find an object which has been hidden in them using a known probability function. In this paper we consider a modification of this problem in which there is a protector who can also allocate resources to the points; allocating these resources makes it more difficult for the searcher to find an object. We model the situation as a two‐person non‐zero‐sum game so that we can take into account the fact that using resources can be costly. It is shown that this game has a unique Nash equilibrium when the searcher's probability of finding an object located at point i is of the form (1 − exp (−λ_ix_i)) exp (−μ_iy_i) when the searcher and protector allocate resources x_i and y_i respectively to point i. An algorithm to find this Nash equilibrium is given. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47:85–96, 2000     

Asymptotic inference about a density function at an end of its range

For each n, X₁(n),…X_n(n) are independent and identically distributed random variables, with common probability density function Where c, θ, α, and r(y) are all unknown. It is shown that we can make asymptotic inferences about c, θ, and α, when r(y) satisfies mild conditions.