A simple and deterministic competitive algorithm for online facility location

This paper presents a deterministic and efficient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also applies to a variety of models, i.e., models where the facilities can be placed anywhere in the region, or only at customer sites, or only at fixed locations. The paper shows that the algorithm is O (log n)-competitive under these various models, where n is the total number of customers. It also shows that the algorithm is O (1)-competitive with high probability and for any arrival order when customers are uniformly distributed or when they follow a distribution satisfying a smoothness property. Experimental results for a variety of scenarios indicate that the algorithm behaves extremely well in practice.     

A branch-and-cluster coordination scheme for selecting prison facility sites under uncertainty

A multi-period stochastic model and an algorithmic approach to location of prison facilities under uncertainty are presented and applied to the Chilean prison system. The problem consists of finding locations and sizes of a preset number of new jails and determining where and when to increase the capacity of both new and existing facilities over a time horizon, while minimizing the expected costs of the prison system. Constraints include maximum inmate transfer distances, upper and lower bounds for facility capacities, and scheduling of facility openings and expansion, among others. The uncertainty lies in the future demand for capacity, because of the long time horizon under study and because of the changes in criminal laws, which could strongly modify the historical tendencies of penal population growth. Uncertainty comes from the effects of penal reform in the capacity demand. It is represented in the model through probabilistic scenarios, and the large-scale model is solved via a heuristic mixture of branch-and-fix coordination and branch-and-bound schemes to satisfy the constraints in all scenarios, the so-called branch-and-cluster coordination scheme. We discuss computational experience and compare the results obtained for the minimum expected cost and average scenario strategies. Our results demonstrate that the minimum expected cost solution leads to better solutions than does the average scenario approach. Additionally, the results show that the stochastic algorithmic approach that we propose outperforms the plain use of a state-of-the-art optimization engine, at least for the three versions of the real-life case that have been tested by us.     

Facility layout problems: A survey

Layout problems are found in several types of manufacturing systems. Typically, layout problems are related to the location of facilities (e.g., machines, departments) in a plant. They are known to greatly impact the system performance. Most of these problems are NP hard. Numerous research works related to facility layout have been published. A few literature reviews exist, but they are not recent or are restricted to certain specific aspects of these problems. The literature analysis given here is recent and not restricted to specific considerations about layout design.

We suggest a general framework to analyze the literature and present existing works using such criteria as: the manufacturing system features, static/dynamic considerations, continual/discrete representation, problem formulation, and resolution approach. Several research directions are pointed out and discussed in our conclusion.     

Facility location and scale decision problem with customer preference

This paper addresses the facility location problem that aims to optimize the location and scale of a new facility in consideration of customer restrictions, including customer preference and the minimum number of customers required to open the facility. In a classic covering problem, the customer is assumed to be covered if he/she is located within the critical distance zone around the facility and is otherwise not covered. This problem is caused by customer facility selection, which differs from the classic covering problem in which services are determined only by proximity. This paper proposes a mixed integer programming formulation based on customer restrictions and also develops a heuristic solution procedure using Lagrangian relaxation. The suggested solution procedure is shown to yield acceptable results in a reasonable computation time.     

多服务中心设置问题局部搜索算法的分析与实验

讨论了多服务中心设置问题的局部搜索近似算法及其在实际计算中表现出的新性质。首先对局部搜索算法求解多服务中心设置问题的实际近似性能比给出了一个针对性分析结果,然后编程实验对局部搜索求解算法的求解时间和求解质量进行了探讨。     

Approaches to uncertainties in facility layout problems: Perspectives at the beginning of the 21<Superscript>st</Superscript> Century

Production uncertainty is one of the most challenging aspects in manufacturing environments in the 21st century. The next generation of intelligent manufacturing is dynamically depending on the production requirements, and success in designing agile facilities is closely related to what extent these requirements are satisfied. This paper presents the most recent advancements in designing robust and flexible facilities under uncertainty. The focus is on exploring the way uncertainty is incorporated in facility design, namely dynamic and stochastic facility layout problems. Recent approaches are explored and categorized in detail, and previous approaches are briefly reviewed in the related categories. Furthermore, research avenues warranting exploration in the emerging field of facility design are also discussed.     

基于遗传模拟退火算法的多层设施选址方法

逆向物流网络是逆向物流系统高效运作的基础和前提,而设施的选址定位是逆向物流网络设计的核心问题.为此,提出一个多层设施选址模型,旨在构建由回收点、回收中心和生产点相结合的最佳逆向物流回收网络.根据模型特点,提出基于遗传模拟退火算法的求解方法,个体采用二进制十进制混合编码;提出基于Metropolis准则的特定遗传进化操作;设计顾客对回收点、回收点对回收中心的两个子分配算法保证所有约束的满足性.最后通过仿真实验,得到满意的设施选址方案.可见,选址模型和算法是一种有效的设施选址方法,具有一定的应用前景.     

一般设施定位问题计算复杂度和近似算法研究

设施定位问题即UFL问题是NP-hard的组合优化问题,是聚类问题领域的热点问题之一,在数据挖掘和分类识别方面有着重要应用.多年来其近似算法研究一直是计算机科学工作者关注的焦点,然而现有研究结果大多关于Metric空间,一般距离空间中该问题结果始终未见.针对最大连接费用至多是最小连接费用ω＞1倍的一般距离空间中设施定位问题,简称一般设施定位问题,借助集合覆盖问题,利用问题归约方法证明其不存在近似性能比小于1.243 0.316ln(ω-1)的多项式时间近似算法,除非NPDTIME(nO(log log n));设计了一般设施定位问题的局部搜索算法,证明算法近似性能比是(1 ω)/α,ω＞1,1≤α≤2.仿真实验表明,一般设施定位问题局部搜索算法的求解质量极高;通过实验进一步研究了该算法并给出了改进方法.     

An overview of JML tools and applications

The Java Modeling Language (JML) can be used to specify the detailed design of Java classes and interfaces by adding annotations to Java source files. The aim of JML is to provide a specification language that is easy to use for Java programmers and that is supported by a wide range of tools for specification typechecking, runtime debugging, static analysis, and verification.This paper gives an overview of the main ideas behind JML, details about JML’s wide range of tools, and a glimpse into existing applications of JML.     

一个综合交换机模型

在给出ISDN的基本概念和开发综合交换机的重要性之后，我们对现有的各种综合交换机模型进行了大致的分类，并给出了各自的优、缺点和存在的问题。在此基础上我们提出了一个希望能解决上述问题，并能够保证ISDN的各种优越性能得到充分施展和发挥的新模型。本文给出了该模型的结构，介绍了各模块的功能和各模块之间的联系。较详细地讨论了该模型对分组业务的处理情况。     

Stochastic facility location with general long-run costs and convex short-run costs

This paper addresses the problem of minimizing the expected cost of locating a number of single product facilities and allocating uncertain customer demand to these facilities. The total costs consist of two components: firstly linear transportation cost and secondly the costs of investing in a facility as well as maintaining and operating it. These facility costs are general and non-linear in shape and could express both changing economies of scale and diseconomies of scale. We formulate the problem as a two-stage stochastic programming model where both demand and short-run costs may be uncertain at the investment time. We use a solution method based on Lagrangean relaxation, and show computational results for a slaughterhouse location case from the Norwegian meat industry.     

Main Effect Fine-tuning of the Mutation Operator and the Neighbourhood Function for Uncapacitated Facility Location Problems

In both genetic algorithms (GAs) and simulated annealing (SA), solutions can be represented by gene representation. Mutation operator in GA and neighborhood function in SA are used to explore the solution space. They usually select genes for performing mutation. The rate of selection of genes can be called mutation rate. However, randomly selecting genes may not be the best way for both algorithms. This paper describes how to estimate the main effect in genes representation. The resulting estimates cannot only be used to understand the domination of gene representation, but also employed to fine-tune the mutation rate in both the mutation operator in the GA and the neighborhood function in the SA. It has been demonstrated the use of the proposed methods for solving uncapacitated facility location problems and discuss the examination of the proposed methods with some useful comparisons with both the latest developed GA and SA for solving this problem. For many well-known benchmark problems, the proposed methods yield better results in solution quality than the previously used methods.     

A bottleneck Steiner tree based multi-objective location model and intelligent optimization of emergency logistics systems

Logistics networks could be very fragile in a global environment due to unexpected emergencies such as earthquakes, tsunamis and terrorists attacks. Therefore, the research on emergency logistics systems is extremely significant. The dynamic changes, quick responses and unpredictable events are main features of the location problems in emergency logistics systems, which make them quite different from the traditional logistics networks. The previous single-objective location models and solution algorithms do not capture the new characteristics that arise from the emergency logistics systems. This paper first proposes a new node-weighted bottleneck Steiner tree based multi-objective location optimization model for the emergency logistics systems. Then, a cellular stochastic diffusion search based intelligent algorithm is introduced to solve the proposed model. Under different emergent scenarios, several examples are used to illustrate the application of the proposed model. Numerical experiments show that the proposed approach is effective and efficient for solving the location problem of emergency logistics systems.     

Convergence of Markov chain approximation on generalized HJB equation and its applications

This work is concerned with numerical methods for a class of stochastic control optimizations and stochastic differential games. Numerical procedures based on Markov chain approximation techniques are developed in a framework of generalized Hamilton-Jacobi-Bellman equations. Convergence of the algorithms is derived by means of viscosity solution methods.     

An overview of dynamic parameter identification of robots

Due to the importance to model-based control, dynamic parameter identification has attracted much attention. However, until now, there is still much work for the identification of dynamic parameters to be done. In this paper, an overview is given of the existing work on dynamic parameter identification of serial and parallel robots. The methods for estimating the dynamic parameters are summarized, and the advantages and disadvantages of each method are discussed. The model to be identified and the trajectory optimization are reviewed. Further, the methods for validating the estimated model are summarized and the application of dynamic parameter identification is mentioned. The results of this review are useful for manufacturers of robots in selecting proper identification method and also for researchers in determining further research areas.     

Minimizing ordered weighted averaging of rational functions with applications to continuous location

This paper considers the problem of minimizing the ordered weighted average (or ordered median) function of finitely many rational functions over compact semi-algebraic sets. Ordered weighted averages of rational functions are, in general, neither rational functions nor the supremum of rational functions so current results available for the minimization of rational functions cannot be applied to handle these problems. We prove that the problem can be transformed into a new problem embedded in a higher dimensional space where it admits a convenient polynomial optimization representation. This reformulation allows a hierarchy of SDP relaxations that approximates, up to any degree of accuracy, the optimal value of those problems. We apply this general framework to a broad family of continuous location problems showing that some difficult problems (convex and non-convex) that up to date could only be solved on the plane and with Euclidean distance can be reasonably solved with different _?p-norms${?}_p\mathrm{-}\mathrm{norms}$ in finite dimensional spaces. We illustrate this methodology with some extensive computational results on constrained and unconstrained location problems.     

Static strategy and dynamic adjustment: An effective method for Grid task scheduling

Task scheduling is the key technology in Grid computing. Hierarchical organization is suitable for the computational Grid because of the dynamic, heterogeneous and autonomous nature of the Grid. Although a number of Grid systems adopt this organization, few of them has dealt with task scheduling for the hierarchical architecture. In this paper, we present an effective method, fully taking into account both historical Grid trade data and dynamic variation of the Grid market to improve the task scheduling for a hierarchical Grid market. The main idea of the proposed method is a combination of an off-line static strategy using time series prediction and an on-line dynamic adjustment using reinforcement learning. The superiority of this new scheduling algorithm, in improving the inquiry efficiency for resource consumers, getting better load balancing of the whole hierarchical Grid market, and achieving higher success rate of the Grid service request, is demonstrated by simulation experiments.