Multi-facility location problems in the presence of a probabilistic line barrier: a mixed integer quadratic programming model

We consider a multi-facility location problem in the presence of a line barrier with the starting point of the barrier uniformly distributed. The objective is to locate n new facilities among m existing facilities minimising the summation of the weighted expected rectilinear barrier distances of the locations of new facilities and new and existing facilities. The proposed problem is designed as a mixed-integer nonlinear programming model, conveniently transformed into a mixed-integer quadratic programming model. The computational results show that the LINGO 9.0 software package is effective in solving problems with small sizes. For large problems, we propose two meta-heuristic algorithms, namely the genetic algorithm and the imperialist competitive algorithm for optimisation. The numerical investigations illustrate the effectiveness of the proposed algorithms.     

A Quadratic Facility Location Problem

This article treats the problem of locating multiple new facilities with respect to multiple existing facilities when there is an interchange of materials between new facilities and between new and existing ones. The “cost” of a solution to the location problem is given as a weighted sum of the square of the Euclidian distances traveled in the interchange of materials. Necessary and sufficient conditions for an optimum location are developed, resulting in the simultaneous solution of a set of linear equations in order to obtain the optimum location. The solution procedure is demonstrated with an example problem.     

Layout planning for facilities with fixed shapes and input and output points

This paper focuses on the facility layout problem in which each facility has a predetermined shape and input and output points. In the problem, facilities are placed within a given floor, and the spatial coordinates and orientation of each facility are to be determined. We give a mixed integer programming (MIP) model for the layout planning problem with the objective of minimizing the sum of rectilinear distances weighted by flow amounts between input and output points of the facilities. Using the MIP model, we develop a two-phase algorithm in which an initial layout is generated in the construction phase and is improved using four improvement methods applied iteratively in the improvement phase. Results of computational experiments show that the proposed algorithm gives better solutions than existing algorithms.     

A rectilinear distance location–relocation problem with a probabilistic restriction: mathematical modelling and solution approaches

In this study, we have considered a multi-period centre facility location–relocation problem in the presence of a probabilistic polyhedral barrier uniformly distributed on a horizontal barrier route in rectilinear plane. The objective function of this location–relocation problem is the minimisation of the cost of maximum expected rectilinear barrier distance from demand points to the new facility plus the relocation cost (i.e. a changeover cost at the beginning of each period) in the form of a mixed integer quadratic-constrained mathematical programming. The computational results show that the non-linear solver of commercial software LINGO is only effective in solving small-sized problems. A linear approximation for the system constraints is proposed so that a new mixed integer linear programming model is generated which is solvable via CPLEX optimisation software. Moreover, we proposed a problem decomposition procedure that reduces the multi-period problem into a number of single-period problems with some modifications. To show the efficiency of the model and solution methodologies, a broad range of numerical examples are performed. Results indicate that the developed problem decomposition procedure obtains the near-optimal solution comparatively with the results obtained from the non-linear solver of LINGO, and that the lower bound problem can be useful for large-sized problems in a reasonable time. Moreover, a practical case example to show the model validity in real world is solved and to reality check from practice, results are compared with the problem without barrier.     

A Greedy Network Flow Algorithm for A Warehouse Leasing Problem

In this paper we consider the problem of a firm which must lease warehouse space over a finite planning horizon. Demand for space in each time period is a random variable with known density function. The firm contracts for warehouse space for each time period at the beginning of the planning horizon via a primary contract. If demand exceeds space in any period, additional space can be obtained via a secondary contract. The leasing problem is shown to be equivalent to a linear programming problem under reasonable assumptions. The dual to the linear program is shown to be equivalent to a network flow problem which can be solved via a greedy algorithm, and admits a rather simple primal variable recovery procedure. Computational evidence indicates that dual problems with some 200,000 arcs can be solved efficiently.     

A Heuristic Programming Algorithm for Warehouse Location

A new heuristic programming method of solving a particular type of warehouse location problem is presented. The problem is to allocate K or less facilities to N possible locations so as to service M demand centers at minimum cost. The algorithm presented is suitable for hand calculation of medium-size problems (50 × 50) or when computerized will readily solve large-scale problems of the order of (600 × 600); i.e., 600 demand centers and 600 possible locations.     

A Minimax Facility Layout Problem Involving Distances Between and Within Facilities

This paper presents a simple solution procedure for the problem of laying out n facilities, where each facility takes up a planar region of known area but with shape not prespecified, so as to minimize the maximum of the following terms: the greatest of the rectilinear distances between all pairs of regions; the greatest of the rectilinear distances within specified regions. The procedure for finding minimax layouts provides several qualitative insights which suggest design guidelines; virtually closed form answers are obtained.     

Tree Network Location Problems With Minimum Separations

We consider the problem of characterizing feasible locations for identical facilities in a tree network when lower bound constraints are imposed on distances between the facilities as well as between each fixed point and the facilities. We first eliminate from the network some fixed points whose associated constraints, are redundant, and then develop a sequential procedure for locating the maximum number of facilities. We relate this maximum number to the consistency of the distance constraints; the resulting information is relevant in solving a certain class of location problems on tree networks.     

An integrated approach for the concurrent determination of the block layout and the input and output point locations based on the contour distance

This paper presents an integrated approach for the facilities design problem. It develops a method for the concurrent determination of the block layout, the locations of departmental input and output (I/O) points using the contour distances between the I/O points, and the material flow paths between the I/O points. The topology of block layouts is represented using two linear sequences (sequence-pair), which allows the layout to have either a slicing or a non-slicing structure. The block layout is obtained from the sequence-pair with a linear programming formulation. Three heuristic methods are then presented to determine for a given block layout the locations of the I/O points on the perimeters of the departments. The flow paths from output to input points are found by determining the shortest paths that follow the perimeters of the departments. The linear programming algorithm, the shortest path algorithm, and the I/O point location heuristics are embedded into a simulated annealing algorithm that modifies the sequence-pair to obtain a high-quality layout based on the contour distances between the I/O points. Results of computational experiments show that the performance of this integrated algorithm compares favourably with those of algorithms using a sequential approach and is capable of solving industrial-sized problems in acceptable computation time.     

On Solving Multifacility Location Problems using a Hyperboloid Approximation Procedure

An iterative solution method is presented for solving multifacility location problems involving rectilinear and/or Euclidean distances. The iterative procedure is based on the use of an approximating function involving hyperboloids, which in the limit approach the cones in the original objective function. Given that the hyperboloid approximation procedure converges, it is shown to converge to the optimum solution. Computational experience with the procedure is described.     

Equivalent primal and dual differentiable reformulations of the Euclidean multifacility location problem

In this paper, we consider two equivalent differentiable reformulations of the nondifferentiable Euclidean multifacility location problem (EMFLP). The first of these is derived via a Lagrangian dual approach based on the optimum of a linear function over a unit ball (circle). The resulting formulation turns out to be identical to the known dual problem proposed by Francis and Cabot [1]. Hence, besides providing an easy direct derivation of the dual problem, this approach lends insights into its connections with classical Lagrangian duality and related results. In particular, it characterizes a straightforward recovery of primal location decisions. The second equivalent differentiable formulation is constructed directly in the primal space. Although the individual constraints of the resulting problem are generally nonconvex, we show that their intersection represents a convex feasible region. We then establish the relationship between the Karush-Kuhn-Tucker (KKT) conditions for this problem and the necessary and sufficient optimality conditions for EMFLP. This lends insights into the possible performance of standard differentiable nonlinear programming algorithms when applied to solve this reformulated problem. Some computational results on test problems from the literature, and other randomly generated problems, are also provided.     

Efficient optimization of cyclic labor days-off scheduling

An efficient method is presented for the optimum solution of the cyclic manpower days-off scheduling problem. This method, which is based on linear programming, allows unequal costs to be considered for different days-off patterns. First, the solution of the dual linear programming model is used to determine the minimum workforce size. Then, a procedure based on the dual solution is introduced to assign the workforce to days-off patterns in order to minimize the total labor cost. The new method offers an alternative to specialized linear or integer programming software, since it requires only few and simple calculations.     

Preprocessing for static and dynamic facility layout problems

Most facility layout problems have departments with unequal areas and have significant rearrangement costs. This paper describes a model and improved algorithm which simultaneously handles these parameters. An existing algorithm solves the dynamic facilities layout problem while permitting the departments to have unequal areas. One part of the algorithm solves a mixed integer programming problem to find the desired block diagram layout. This large, complex problem could only be solved optimally for small problems. Therefore a preprocessing method was developed to prespecify certain obvious department pair orientations, which had previously required binary variables. The method uses estimated location, department sizes, and flow costs to determine the probable variable values. Then, a revised branch and bound strategy solves for the less obvious department pair orientations. Test results show a significant cost reduction on a variety of previously published problems, and feasible solutions to previously unsolved problems. The algorithm found a layout solution to the standard . CRAFT problem which has 10 5% lower costs than the previously best published layout.     

Methods for optimum and near optimum disassembly sequencing

This paper considers disassembly sequencing problems subjected to sequence dependent disassembly costs. In practice, the methods for dealing with such problems rely mainly on metaheuristic and heuristic methods, which intrinsically generate suboptimum solutions. Exact methods are NP-hard and therefore unsuitable to most of the practical problems. Nevertheless, it is useful to have exact methods available that can be applied in order to check, at least medium sized problems, to what extent the heuristically obtained solutions deviate from the optimum solution. The existing exact approaches, which are based on integer linear programming (ILP), become unmanageable, even for the cases of modest product complexity. To alleviate this problem to some extent, the iterative method that has been proposed by Lambert (2006) is applied here. This method is based on repeatedly solving a binary integer linear programming (BILP) problem instead of an ILP problem. The method appears to converge sufficiently quickly to be valuable for dealing with medium sized problems. We then use the iterative method for the validation of a new heuristic method that is also proposed in this paper. Finally, both the heuristic and the iterative BILP methods are implemented on a cellphone from practice consisting of 25 components that are represented, according to a set of precedence relationships, via a disassembly precedence graph.     

Rectangular Layout Problems with Worst-Case Distance Measures

This paper considers two related problems involving the design of rectangular layouts of m activities. In each of the problems, costs are incurred which are nondecreasing in distance between activities. The distance between two activities is either the worst-case rectilinear distance, or the worst-case Tchebyshev distance. Minisum and minimax layout problems are then considered and solution techniques are provided. The solution techniques demonstrate that both the area (e.g., number of square feet) taken up by the facilities, as well as the relative use of the facilities, must be considered in order to solve the layout problems of interest.     

Normative Models for Some Warehouse Sizing Problems

The problem examined is the determination of the optimum size for a warehouse used to store products over a finite planning horizon. Both fixed and changeable warehouse size problems are treated under conditions of deterministic and probabilistic storage demand. The latter is formulated as a linear programming problem and transformed via duality theory into an equivalent network flow problem for efficient solution. Costs considered are those due to warehouse construction, storage of products within the facility, and storage demand not satisfied by storage in the warehouse.     

On the Direct Search Approach to the Rectilinear Facilities Location Problem

A direct search approach to the rectilinear facilities location problem is considered in detail. This approach is shown to be a specialization of the primal simplex method for linear programming. A necessary condition for optimality is also shown to be sufficient in special cases. The main difficulties associated with the direct search approach are discussed, and a few simple examples are given as an illustration.     

A Generalized Assignment Approach to Optimal Facility Layout

The problem is considered of locating facilities of known areas so as to minimize a total cost consisting of costs directly proportional to the average distances between facilities and known points in the plane. An example would be the layout of products in a warehouse so as to minimize the total cost due to moving products to and from warehouse docks. We show that the problem can be accurately represented, and solved efficiently, as a generalized assignment problem, which is a special case of the transportation problem. An interesting special case of the location problem may be solved by a simple ranking procedure.     

Fast Algorithms for the Round Trip Location Problem

This paper presents several fast algorithms for the round trip location problem. I show how to simplify the method given in an article by Chan and Hearn in which only the rectilinear case is addressed and get an algorithm with improved complexity for a given accuracy. An exact solution algorithm (the complexity of which is unknown) that solved test data problems even faster is presented and generalized for Euclidean and ℓ_p distances. Computational results are also presented.     

求解不定二次约束二次规划问题的全局优化算法

不定二次约束二次规划问题广泛应用于芯片设计、无线通信网络、财政金融和众多工程实际问题．目前尚没有通用的全局收敛准则,这使得求解该问题的全局最优解面临着极大挑战．本文使用矩阵的初等变换技巧将原问题转化为等价双线性规划问题,基于等价问题的特征和线性化松弛技巧构造了等价问题的松弛线性规划,通过求解一系列松弛规划问题的最优解逐步逼近原问题的全局最优解．证明了算法的全局收敛性,并进行数值对比和随机实验,实验结果表明算法高效可行．