A new fuzzy weighted average (FWA) method based on left and right scores: An application for determining a suitable location for a gas oil station

The selection of a facility location from alternative locations is a multiple criteria decision making (MCDM) problem including both quantitative and qualitative criteria. In many real-life cases, determining the exact values for MCDM problems, and especially for facility location selection problems, is difficult or impossible, so the values of alternatives with respect to the criteria or/and the values of criteria weights are considered as fuzzy values (fuzzy numbers) such that the conventional crisp approaches for solving facility location selection problems and other MCDM problems tend to be less effective for dealing with the imprecise or vagueness nature of the linguistic assessments. In such conditions, fuzzy MCDM methods are applied for facility location selection problem and other fuzzy MCDM problems. In this paper, we propose a new fuzzy weighted average (FWA) method based on left and right scores for fuzzy MCDM problems. Moreover, we apply the proposed method to a real application. As a result, we found that the proposed method is practical for facility location selection problems. Besides, it seems that the proposed FWA method is very accurate, flexible, simple, and easy to use when compared to other versions of the FWA method.     

一种求解Job-Shop调度问题的新型蚁群算法

Job-Shop调度问题是一类具有很高理论研究和工程应用价值的问题。针对使用蚁群算法求解Job-Shop调度问题时较难设置合适参数的问题,提出一种动态设置参数的新型蚁群求解算法。分析了蚁群算法中参数对求解结果的影响,给出了算法求解Job-Shop调度问题的关键技术和实现过程。最后对五个基本测试问题进行了仿真实验,并与遗传算法、模拟退火算法、基本蚁群算法进行了比较。结果表明,该算法能得到较优的结果,具有一定的应用价值。     

Capacity constrained maximizing bichromatic reverse nearest neighbor search

When planning a new development (facility/service site), location decisions are always the major issue. In this paper we introduce a novel query capacity constraint MaxBRNN, which can solve the facility location selection problem efficiently.The MaxBRNN (maximizing BRNN) query is based on bichromatic reverse nearest neighbor (BRNN) query which uses the number of reverse nearest customers to model the influence of a facility location. The MaxBRNN query has been appreciated extensively in spatial database studies because of its great potential in real life applications, such as, markets decision, sensor network clustering and the design of GSM (global system for mobile communication). The existing researches mostly suppose that the service facility's capacity is unlimited. However, in real cases, facilities are inevitably constrained by designed capacities. For example, if the government wants to select a new place to set up an emergency center to share the existing centers’ patients, they need to know the current emergency centers’ capacity so that they can estimate the new center's scale. Thus, the capacity constrained MaxBRNN query is significantly important in planning a new development. As far as we know, the capacity constrained MaxBRNN query has not been studied yet, so, we formulate this problem, propose a basic solution and develop some efficient algorithms for the query.Our major contributions are as follows: (1) we propose a novel query capacity constraint MaxBRNN which can solve the facility location selection problem effectively and efficiently; (2) we develop a basic algorithm CCMB and two improved algorithms which can find out the optimal region in terms of building a new facility, maximize its impact and deal with the complicated reassignment when adding new facilities into the dataset; (3) we prove the algorithms’ effectiveness and efficiency by extensive experiments using both real and synthetic data sets.     

.物流配送中心动态选址模型及算法研究*

针对传统物流配送中心动态选址模型没有充分考虑配送中心的可能状态和库存持有成本的问题,建立了一种新的模型。首先,利用两步骤近似法构建了在有库存和运输双重能力约束下,每一个周期配送中心的库存成本计算方法;然后,分别给出了配送中心在整个规划期内的打开、运营、关闭和再次打开的成本表达式;最后,分别用遗传算法、克隆选择算法、粒子群算法求解所建立的模型,并从算法的寻优能力、稳定性、运算速度和收敛性方面比较了三种算法的性能。算例测试结果表明,所建立的模型是有效的;从总体上看,遗传算法的适应性要强于克隆选择算法和粒子群算     

A formulation of the integrated facility layout,product selection and process planning problem

A mathematical formulation for integrated production system planning is proposed. The economic decision model integrates product selection, capacity planning, process planning, and facility layout. The network structure of the material flow constraints facilitates the solution.     

韦伯型多点设施优化选址的组合算法研究

韦伯型设施选址问题是组合优化领域中的一类重要问题,其核心内容是如何在离散的需求空间域内,寻找到最优决策关注点,即设施点。对于单点设施最优规划问题,由于不存在设置点之间的作用,仅考虑设施点与需求点之间的引力作用问题即可。对于多点设施的最优规划问题,不仅存在着设施点与需求点之间的引力作用问题,而且从资源优化配置的角度,还存在着设施点之间的斥力问题。因此,需要从系统整体优化的角度进行选择规划。目前解决韦伯型设施多点的优化选址问题,一般是通过寻找局部最优解的逐次递阶法来确定最优设施点。但由于该方法没有考虑到设施点间的斥力问题,容易导致设施点间的粘连。针对此问题,提出了一种PGSA-GA组合算法,通过建立模拟植物生长算法得到全局最优解的单点坐标,将其与需求点结合构建遗传算法优化的多目标规划多点设施选址模型求出Pareto最优解,并依此推广到多次选址方案。     

Single-plant sourcing decisions with a multidimensional knapsack model

This paper addresses sourcing decisions and how those decisions can affect the management of a company’s assets. The study begins with a single-plant insourcing problem in which the facility chooses, from a list of parts, which parts to bring in-house. This model is extended to include an outsourcing element where, in addition to the decision of which parts to insource, parts currently in-house are considered for outsourcing. The selection is based on maximizing the value of the selected parts while remaining within the plant’s capacity. This is defined as the sourcing problem and modeled as a multidimensional knapsack problem (MKP). Characteristics of the sourcing problem are identified and compared to standard MKP test problems, then utilized to provide guidelines for generating industry-motivated data sets. Experiences with modeling and solving the sourcing problem for a sheet metal fabrication facility are reported.     

Design and implementation of a relational data base for automated process planning

The function of process planning in a manufacturing facility is to identify the processes and the machines required to convert a design into its final form. Majority of the process plans are still made manually. The degree of the process plan detail varies with the shop environment. A feature-based process planning system which interacts with the SDRC I-DEAS solid modeling software is presented. The system operates under the UNIX environment. A relational database model which incorporates manufacturing details including the operation selection, machine selection, tool selection, fixture selection, etc. was developed and implemented. This relational database was structured using Microsoft SQL SERVER for the PC multi-user environment. This database is part of an ongoing research project on automated process planning and scheduling and primarily focuses on prismatic parts. The developed routines generate the Overall Removable Volume (ORV) graphically by comparing the desirable design to the blank work piece. The routines then decompose the ORV into various General Manufacturing Features (GMF) based on concave edges. The recognition routine captures geometrical and topological information and identifies the shape of each GMF. An expert system (using CLIPS expert system shell) analyzes the GMFs and determines appropriate operation(s) for the designed part. The developed expert system is capable of recommending the suitable machines, tools, fixtures, etc.     

A Branch and Bound Algorithm for An Uncapacitated Facility Location Problem with a Side Constraint

In this paper, a branch and bound algorithm for solving an uncapacitated facility location problem (UFLP) with an aggregate capacity constraint is presented. The problem arises as a subproblem when Lagrangean relaxation of the capacity constraints is used to solve capacitated facility location problems. The algorithm is an extension of a procedure used by Christofides and Beasley (A tree search algorithm for the p-median problem. European Journal of Operational Research , Vol. 10, 1982, pp. 196–204) to solve p -median problems and is based on Lagrangean relaxation in combination with subgradient optimization for lower bounding, simple Lagrangean heuristics to produce feasible solutions, and penalties to reduce the problem size. For node selection, a jump-backtracking rule is proposed, and alternative rules for choosing the branching variable are discussed. Computational experience is reported.     

A tabu search procedure for coordinating production,inventory and distribution routing problems

This paper addresses the problem of optimally coordinating a production‐distribution system over a multi‐period finite horizon, where a facility production produces several items that are distributed to a set of customers by a fleet of homogeneous vehicles. The demand for each item at each customer is known over the horizon. The production planning determines how much to produce of each item in every period, while the distribution planning defines when customers should be visited, the amount of each item that should be delivered to customers and the vehicle routes. The objective is to minimize the sum of production and inventory costs at the facility, inventory costs at the customers and distribution costs. We also consider a related problem of inventory routing, where a supplier receives or produces known quantities of items in each period and has to solve the distribution problem. We propose a tabu search procedure for solving such problems, and this approach is compared with vendor managed policies proposed in the literature, in which the facility knows the inventory levels of the customers and determines the replenishment policies.     

Efficient primal-dual heuristic for a dynamic location problem

In this paper the dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal-dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal-dual heuristic based on the work of Erlenkotter [A dual-based procedure for uncapacitated facility location. Operations Research 1978;26:992–1009] and Van Roy and Erlenkotter [A dual-based procedure for dynamic facility location. Management Science 1982;28:1091–105] was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated as in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.     

Hierarchical multi-agent planning for flexible assembly of large-scale lunar facilities

Several national space agencies and commercial aerospace companies plan to set up lunar bases with large-scale facilities that rely on multiple lunar robots’ assembly. Mission planning is necessary to achieve efficient multi-robot cooperation. This paper aims at autonomous multi-robot planning for the flexible assembly of the large-scale lunar facility, considering the harsh lunar environment, mission time optimization, and joint actions. The lunar robots and modules are scattered around the mission area without fixed assembly lines. Thus, the traditional assembly planning methods ignoring the optimal selection of modules are unable to handle this problem. We propose a hierarchical multi-agent planning method based on two-stage two-sided matching (HMAP-TTM) to solve this critical problem. First, the distributed planning framework with multi-replica public agents is introduced, ensuring robot plan knowledge consistency through public agents’ communication. Second, the hierarchical task graph (HTG) divides the mission into task layers based on task dependency knowledge. Third, we develop a novel two-stage two-sided matching algorithm. Time-optimal plans emerge from the matching games among public and private agents in each layer of HTG. Agents make decisions in the game based on action knowledge updated during planning. Finally, an assembly mission is presented to prove the method’s effectiveness. The simulation results show that the HMAP-TTM can generate plans with shorter mission time and require smaller communication costs than the baseline methods.     

The min-dist location selection and facility replacement queries

We propose and study a new type of location optimization problem, the min-dist location selection problem: given a set of clients and a set of existing facilities, we select a location from a given set of potential locations for establishing a new facility, so that the average distance between a client and her nearest facility is minimized. The problem has a wide range of applications in urban development simulation, massively multiplayer online games, and decision support systems. We also investigate a variant of the problem, where we consider replacing (instead of adding) a facility while achieving the same optimization goal. We call this variant the min-dist facility replacement problem. We explore two common approaches to location optimization problems and present methods based on those approaches for solving the min-dist location selection problem. However, those methods either need to maintain an extra index or fall short in efficiency. To address their drawbacks, we propose a novel method (named MND), which has very close performance to the fastest method but does not need an extra index. We then utilize the key idea behind MND to approach the min-dist facility replacement problem, which results in two algorithms names MSND and RID. We provide a detailed comparative cost analysis and conduct extensive experiments on the various algorithms. The results show that MND and RID outperform their competitors by orders of magnitude.     

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.     

Improving facility planning with decision technology systems

Facility planning is a complex process that requires art, science, and technology. Several methodologies have been generated to facilitate this process. Computer information systems (CIS) have been developed to deliver these methodologies and to provide knowledge relevant for effective facility planning. Since accurate decisions are required at each step of the process, the development effort has focused on CISs that support decision-making.Traditionally, the support has been provided in a segmented fashion and for separate phases of the decision-making process. To be absolutely effective, the support should be integrated and complete. There have been efforts to provide the required CIS support, but these systems have inherent conceptual shortcomings. Moreover, the newer and enhanced systems create additional problems that will prevent them from providing integrated support for all decision making phases in facility planning.This paper examines the facility planning process. Then traditional and enhanced information systems support is reviewed and the inherent shortcomings and unresolved integration problems are explained. Finally, an alternative approach, referred to as a Decision Technology System (DTS), is proposed to resolve the difficulties.     

Product mix optimization for a semiconductor fab: Modeling approaches and decomposition techniques

To optimize the product mix of a semiconductor fab, the production capabilities and capacities are matched with the demand in the most profitable way. In this paper we address a linear programming model of the product mix problem considering product dependent demand limits (e.g. obligations and demand forecast) and profits while respecting the capacity bounds of the production facility. Since the capacity consumption is highly dependent on choosing from different production alternatives we are implicitly solving a static capacity planning problem for each product mix. This kind of planning approach is supported by the fluid flow concept and complete resource pooling in high traffic. We propose a general model that considers a wide range of objectives, and we introduce a heuristic that is based on the decomposition of the static capacity planning problem. A computational study reports on the quality of the decomposition approaches, and examples from practice demonstrate the versatility of the model.     

Degree of locational freedom in a single facility euclidean minimax location model

The facility location model discussed here is a single-facility, unweighted, minimax problem defined in the plane. This paper introduces a procedure for constructing contour lines and computing the degree of locational freedom according to this model, based on the farthestpoint Voronoi diagram. Bounds and an approximate expression on the degree of locational freedom are also presented. The magnitude of the degree of locational freedom is important for decision-makers. This is because the larger the magnitude, the easier it will be for them to carry out their facility planning. The results of extensive computational tests identify empirically the availability of these bounds. The results also show that the degree of locational freedoms in the case where the center is determined by two demand points is greater than the degrees where the center is determined by three demand points.     

Fix-and-Relax-Coordination for a multi-period location–allocation problem under uncertainty

A multi-period discrete facility location problem is introduced for a risk neutral strategy with uncertainty in the costs and some of the requirements along the planning horizon. A compact 0–1 formulation for the Deterministic Equivalent Model of the problem under two alternative strategies for the location decisions is presented. Furthermore, a new algorithmic matheuristic, Fix-and-Relax-Coordination, is introduced. This solution scheme is based on a specialization of the Branch-and-Fix Coordination methodology, which exploits the Nonanticipativity Constraints and uses the Twin Node Family concept. The results of an extensive computational experience allow to compare the alternative modeling strategies and assess the effectiveness of the proposed approach versus the plain use of a state-of-the-art MIP solver.     

Heuristics for tactical time slot management: a periodic vehicle routing problem view

In this study, we consider a tactical problem where a time slot schedule for delivery service over a given planning horizon must be selected in each zone of a geographical area. A heuristic search evaluates each schedule selection by constructing a corresponding tactical routing plan of minimum cost based on demand and service time estimates. At the end, the schedule selection leading to the best tactical routing plan is selected. The latter can then be used as a blueprint when addressing the operational problem (i.e., when real customer orders are received and operational routes are constructed). We propose two heuristics to address the tactical problem. The first heuristic is a three‐phase approach: a periodic vehicle routing problem (PVRP) is first solved, followed by a repair phase and a final improvement phase where a vehicle routing problem (VRP) with time windows is solved for each period of the planning horizon. The second heuristic tackles the problem as a whole by directly solving a PVRP with time windows. Computational results compare the two heuristics under various settings, based on instances derived from benchmark instances for the VRP with time windows.     

A discounted integrated inspection-maintenance model for a single deteriorating production facility

In this paper, we address the problem of determining optimum inspection schedules for a single deteriorating production system with a predetermined replacement cycle. It is assumed that, at different discrete points in time over the fixed planning horizon, the facility is inspected to detect its operating state and then it goes over an imperfect preventive maintenance routine to enhance its operating performance. Moreover, the facility undergoes minimal repair once detected in an “out‐of‐control” state. We also adopt the concept of discounted cash flow analysis to account properly for the effect of time value of money on the inspection policies. Under these settings, we formulate the discounted integrated inspection‐maintenance problem as a dynamic programming model with general time to failure distribution. After illustrating the model with a numerical example, we perform sensitivity analysis to investigate the effects of some input parameters on the expected present worth and the number of inspections.