Acceleration of the HAP approach for the multifacility location problem

This article considers the problem of locating multiple new facilities to minimize the cost function consisting of the sum of weighted distances among new facilities and between new and existing facilities. The hyperboloid approximate procedure (HAP) is probably the most widely used approach for solving this problem. In this article, an optimality condition for this problem is derived and a method to accelerate the convergence rate of the HAP for the case of Euclidean distances is presented. From the numerical results presented in this article, it can be concluded that the performance of the new algorithm is superior to the performance of the original HAP.     

Properties of a multifacility location problem involving euclidian distances

This paper considers a problem of locating new facilities in the plane with respect to existing facilities, the locations of which are known. The problem consists of finding locations of new facilities which will minimize a total cost function which consists of a sum of costs directly proportional to the Euclidian distances among the new facilities, and costs directly proportional to the Euclidian distances between new and existing facilities. It is established that the total cost function has a minimum; necessary conditions for a mimumum are obtained; necessary and sufficient conditions are obtained for the function to be strictly convex (it is always convex); when the problem is “well structured,” it is established that for a minimum cost solution the locations of the new facilities will lie in the convex hull of the locations of the existing facilities. Also, a dual to the problem is obtained and interpreted; necessary and sufficient conditions for optimum solutions to the problem, and to its dual, are developed, as well as complementary slackness conditions. Many of the properties to be presented are motivated by, based on, and extend the results of Kuhn's study of the location problem known as the General Fermat Problem.     

A linear programming solution to the generalized rectangular distance weber problem

The Weber Problem generalized to the location of several new points with respect to existing points is formulated as a linear programming problem under the assumption that distances are rectangular. The dual problem is then formulated and subsequently reduced to a problem with substantially fewer variables and constraints than required by an existent alternative linear programming formulation. Flows may exist between new as well as between new and existing points. Linear constraints can be imposed to restrict the location of new points. Pairwise constraints limiting distances between new points and between new and existing points can also be accommodated.     

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.     

Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem

Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well‐known NP‐hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optimality of the sequence within the framework of probabilistic analysis. Our main result is that, when the processing times are randomly and independently drawn from the same uniform distribution, the sequence is asymptotically optimal in the sense that its relative error converges to zero in probability as n increases. Other theoretical results are also derived, including: (i) When the processing times follow a symmetric structure, the problem has 2^{⌊(n−1)/2⌋} optimal sequences, which include our proposed sequence and other heuristic sequences suggested in the literature; and (ii) when these 2^{⌊(n−1)/2⌋} sequences are used as approximate solutions for a general problem, our proposed sequence yields the best approximation (in an average sense) while another sequence, which is commonly believed to be a good approximation in the literature, is interestingly the worst. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 373–398, 1999     

On the equivalence between the Node-ARC and ARC-Chain formulations for the multi-commodity maximal flow problem

The purpose of this article is to formulate the multi-commodity maximal flow problem into a node-arc form and to show that when decomposition is applied to this form the resulting master and subproblems become precisely those described by Ford & Fulkerson [3] using the arc-chain formulation. A generalization to the problem is then considered which can potentially speed its convergence.     

Probabilistic models of decreasing failure rate processes

The “infant mortality” effect observed in the statistical treatment of reliability consists of a decreasing with age of the conditional probability of equipment failure (failure rate). One widely applicable explanatory hypothesis is that of population heterogeneity. This is developed here as a basis for several specific models of decreasing failure rate processes. Since, in the case of repairable devices, decreasing failure rate is often observed after the occurrence of failure and repair, consideration is extended to include repair in an explicit way. This union of failure and repair models is a fruitful one in view of the interaction between the two processes and gives a complete picture of the life of the device in terms of a stochastic process, usually with non-independent interfailure times. Four models, of particular significance due to their plausibility, mathematical tractability, and frugality of parameterization, are presented.     

纳米级变频器及加法器的新概率建模方法

纳米级数字电路应用时,必须考虑设备故障对纳米级设计的影响.在马尔可夫新特性随机场基础上,提出了纳米级变频器和加法器的概率逻辑模型,并用它们来建模概率行为.实验分析显示设备故障的概率分布极大依赖于系统结构及其他运行参数.     

Special cases of the flow-shop problem

The paper examines all known special cases of the mXn flow-shop problem. It provides solution procedures to three new special cases along with the optimality proofs. The theory of the new special cases is based on the critical path concept.     

On the rectangular p-center problem

The p-center problem involves finding the best locations for p facilities such that the furthest among n points is as close as possible to one of the facilities. Rectangular (sometimes called rectilinear, Manhattan, or l₁) distances are considered. An O(n) algorithm for the 1-center problem, an O(n) algorithm for the 2-center problem, and an O(n logn) algorithm for the 3-center problem are given. Generalizations to general p-center problems are also discussed.     

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.     

基于柔性基础的双层隔振系统概率灵敏度分析

对基于柔性基础的双层隔振系统的功率流传递特性进行了分析,利用有限元分析软件ANSYS计算了传递到基础的功率流,并用概率灵敏度分析方法研究了功率流对隔振系统给定参数的灵敏度,为双层隔振系统的优化设计奠定了基础.     

基于概率神经网络的编队协同防空威胁评估

为了有效地进行防空作战部署,确保重点目标不受或少受损失,以防空作战实际需要为出发点,针对目前多平台协同防空作战中目标威胁评估问题普遍存在的不足,从舰艇编队的整体角度出发,运用概率神经网络的方法,建立了编队协同防空目标威胁评估问题的数学模型,给指挥员提供了正确决策。通过实例验证,证明了该模型的有效性和正确性。     

基于概率神经网络的高校科研能力评价

科研能力是评价高校综合实力的重要指标,高校的科研能力水平将会在一定程度上影响到高校所在地方甚至国家的科研水平.因此,不断提升学校科研能力水平,成为高校自我提高和发展、增强综合实力的重要措施之一.如何对高校科研能力进行科学地评价,成为一个亟待解决的问题.本文将高等院校科研能力评价体系作为研究对象,通过相关文献的查阅,从众多研究中,选取影响高校科研能力的11个典型指标,构建了基于PNN的高校科研能力评价模型及算法.并通过仿真实验验证模型及评价方法的可行性和有效性,为高校科研能力有效评价提供参考依据.     

基于概率模型的弹道导弹突防措施分析

从作战效率的角度,建立多层防御系统的概率模型,分析单层防御系统性能变化对整体的影响;建立目标毁伤概率模型,分析单个目标命中概率对单层防御系统性能的影响;建立单层防御系统的贝努利实验模型,分析识别能力和毁伤能力对系统效能的影响.通过这些简单的概率模型,反向分析探讨了针对分层防御系统的弹道导弹突防问题.     

Regional security and the levels of analysis problem

This study explores the issues involved in creating a regional security regime in the Middle East using insights from the levels of analysis framework of international relations theory. In doing so, Spiegel focuses on the means which can be implemented in the region in order to improve the prospects for establishing such a regime.     

A generalization of the weighted set covering problem

We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect b‐matching problem. In general, we may use a polynomial‐time greedy heuristic similar to the one for the classical weighted set covering problem studied by D.S. Johnson [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256–278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383–390], and V. Chvatal [A greedy heuristic for the set‐covering problem, Math Oper Res 4(3) (1979), 233–235] to get an approximate solution for the problem. We find a worst‐case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Limiting behavior of the stochastic sequential assignment problem

The stochastic sequential assignment problem (SSAP) considers how to allocate available distinct workers to sequentially arriving tasks with stochastic parameters such that the expected total reward obtained from the sequential assignments is maximized. Implementing the optimal assignment policy for the SSAP involves calculating a new set of breakpoints upon the arrival of each task (i.e., for every time period), which is impractical for large‐scale problems. This article studies two problems that are concerned with obtaining stationary policies, which achieve the optimal expected reward per task as the number of tasks approaches infinity. The first problem considers independent and identically distributed (IID) tasks with a known distribution function, whereas in the second problem tasks are derived from r different unobservable distributions governed by an ergodic Markov chain. The convergence rate of the expected reward per task to the optimal value is also obtained for both problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Extreme solutions of the two machine flow-shop problem

The paper provides a new theoretical framework to identify extreme solutions of the two machine flow-shop problem. Some remarkable properties of these solutions have been developed. As a result the problem of generating minimal solutions can be decomposed into a number of smaller subproblems.