An improved two-stage optimization-based framework for unequal-areas facility layout

The unequal-areas facility layout problem is concerned with finding the optimal arrangement of a given number of non-overlapping indivisible departments with unequal area requirements within a facility. We present an improved optimization-based framework for efficiently finding competitive solutions for this problem. The framework is based on the combination of two mathematical optimization models. The first model is a nonlinear approximation of the problem that establishes the relative position of the departments within the facility, and the second model is an exact convex optimization formulation of the problem that determines the final layout. Aspect ratio constraints on the departments are taken into account by both models. Our computational results show that the proposed framework is computationally efficient and consistently produces competitive, and often improved, layouts for well-known instances from the literature as well as for new large-scale instances with up to 100 departments.     

A spring-embedding approach for the facility layout problem

The facility layout problem is concerned with finding the most efficient arrangement of a given number of departments with unequal area requirements within a facility. The facility layout problem is a hard problem, and therefore, exact solution methods are only feasible for small or greatly restricted problems. In this paper, we propose a spring-embedding approach that unlike previous approaches results in a model that is convex. Numerical results demonstrating the potential of our model and the efficiency of our solution procedure are presented.     

Applying the sequence-pair representation to optimal facility layout designs

We present a new formulation for the facility layout problem based on the sequence-pair representation, which is used successfully in VLSI design. By tightening the structure of the problem with this formulation, we have extended the solvable solution space from problems with nine departments to problems with eleven departments.     

A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem

Owing to its theoretical as well as practical significance, the facility layout problem with unequal-area departments has been studied for several decades, with a wide range of heuristic and a few exact solution procedures developed by numerous researchers. In one of the exact procedures, the facility layout problem is formulated as a mixed-integer programming (MIP) model in which binary (0/1) variables are used to prevent departments from overlapping with one another. Obtaining an optimal solution to the MIP model is difficult, and currently only problems with a limited number of departments can be solved to optimality. Motivated by this situation, we developed a heuristic procedure which uses a “graph pair” to determine and manipulate the relative location of the departments in the layout. The graph-pair representation technique essentially eliminates the binary variables in the MIP model, which allows the heuristic to solve a large number of linear programming models to construct and improve the layout in a comparatively short period of time. The search procedure to improve the layout is driven by a simulated annealing algorithm. The effectiveness of the proposed graph-pair heuristic is demonstrated by comparing the results with those reported in recent papers. Possible extensions to the graph-pair representation technique are discussed at the end of the paper.     

New heuristic for the dynamic layout problem

The dynamic layout problem addresses the situation where the traffic among the various units within a facility changes over time. Its objective is to determine a layout for each period in a planning horizon such that the total of the flow and the relocation costs is minimized. The problem is computationally very hard and has begun to receive attention only recently. In this paper, we present a new heuristic scheme, based on the idea of viable layouts, which is easy to operationalize. A limited computational study shows that, depending upon how it is implemented, this scheme can be reasonably fast and can yield results that are competitive with those from other available solution methods.     

A two-stage mathematical-programming method for the multi-floor facility layout problem

We present a two-stage method using mathematical-programming techniques for finding high-quality solutions to the multi-floor facility layout problem. The first stage is a mixed-integer linear program that assigns departments to floors such that the total of the vertical interaction costs between departments on different floors is globally minimized. The second stage finds a locally optimal layout for each floor. Two versions of the proposed approach are considered. The first solves the layout of each floor independently of the other floors, and is suitable for up to one elevator location. The second solves the layout of all floors simultaneously and can handle multiple elevator locations. Preliminary computational results show that both versions of the proposed method can efficiently provide a good variety of high-quality solutions in a short amount of time for medium and large-scale problem instances.     

Heuristics for the dynamic facility layout problem with unequal-area departments

The dynamic facility layout problem (DFLP) is the problem of finding positions of departments on the plant floor for multiple periods (material flows between departments change during the planning horizon) such that departments do not overlap, and the sum of the material handling and rearrangement costs is minimized. In this paper, the departments may have unequal-areas and free orientations, and the layout for each period is generated on the continuous plant floor. Because of the complexity of the problem, only small-size problems can be solved in reasonable time using exact techniques. As a result, a boundary search (construction) technique, which places departments along the boundaries of already placed departments, is developed for the DFLP. The solution is improved using a tabu search heuristic. The heuristics were tested on some instances from the DFLP and static facility layout problem (SFLP) literature. The results obtained demonstrate the effectiveness of the heuristics.     

Locating Multiple Competitive Facilities: Spatial Interaction Models with Variable Expenditures

We develop a new framework for location of competitive facilities by introducing non-constant expenditure functions into spatial interaction location models. This framework allows us to capture two key effects – market expansion and cannibalization – within the same model.We develop algorithmic approaches for finding optimal or near-optimal solutions for several models that arise from choosing a specific form of the expenditure functions.     

Contour line construction for a new rectangular facility in an existing layout with rectangular departments

In a recent paper, Savas et al. [S. Savas, R. Batta, R. Nagi, Finite-size facility placement in the presence of barriers to rectilinear travel, Operations Research 50 (6) (2002) 1018–1031] consider the optimal placement of a finite-sized facility in the presence of arbitrarily shaped barriers under rectilinear travel. Their model applies to a layout context, since barriers can be thought to be existing departments and the finite-sized facility can be viewed as the new department to be placed. In a layout situation, the existing and new departments are typically rectangular in shape. This is a special case of the Savas et al. paper. However the resultant optimal placement may be infeasible due to practical constraints like aisle locations, electrical connections, etc. Hence there is a need for the development of contour lines, i.e. lines of equal objective function value. With these contour lines constructed, one can place the new facility in the best manner. This paper deals with the problem of constructing contour lines in this context. This contribution can also be viewed as the finite-size extension of the contour line result of Francis [R.L. Francis, Note on the optimum location of new machines in existing plant layouts, Journal of Industrial Engineering 14 (2) (1963) 57–59].     

IP modeling of the survivable hop constrained connected facility location problem

We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least λ edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for finding its solution. Finally, we report computational results.     

Financial scenario generation for stochastic multi-stage decision processes as facility location problems

The quality of multi-stage stochastic optimization models as they appear in asset liability management, energy planning, transportation, supply chain management, and other applications depends heavily on the quality of the underlying scenario model, describing the uncertain processes influencing the profit/cost function, such as asset prices and liabilities, the energy demand process, demand for transportation, and the like. A common approach to generate scenarios is based on estimating an unknown distribution and matching its moments with moments of a discrete scenario model. This paper demonstrates that the problem of finding valuable scenario approximations can be viewed as the problem of optimally approximating a given distribution with some distance function. We show that for Lipschitz continuous cost/profit functions it is best to employ the Wasserstein distance. The resulting optimization problem can be viewed as a multi-dimensional facility location problem, for which at least good heuristic algorithms exist. For multi-stage problems, a scenario tree is constructed as a nested facility location problem. Numerical convergence results for financial mean-risk portfolio selection conclude the paper.     

STaTS: A Slicing Tree and Tabu Search based heuristic for the unequal area facility layout problem

In this paper, a slicing tree based tabu search heuristic for the rectangular, continual plane facility layout problem (FLP) is presented. In addition to the incorporation of facilities with unequal areas we also integrate the possibility to specify various requirements regarding (rectangular) shape and dimensions of each individual facility by using bounding curves. Therefore, it is possible to solve problems containing facilities of fixed and facilities of flexible shapes at the same time. We present a procedure that calculates the layout corresponding to a given slicing tree on the basis of bounding curves. These layouts are slicing structures which are able to contain empty spaces to guarantee that stringent shape restrictions of facilities are kept. Due to these features this approach is better suited for practical use than so far existing ones. The effectiveness of our approach in terms of objective function value is shown by comparing our results to those found in the literature. Even a large problem instance comprised of 62 facilities has been solved.     

A polyhedral study of triplet formulation for single row facility layout problem

The single row facility layout problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183-190]. For any number of departments n, we prove that the dimension of the triplet polytope is n(n−1)(n−2)/3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral.     

The offshore wind farm array cable layout problem: a planar open vehicle routing problem

In an offshore wind farm (OWF), the turbines are connected to a transformer by cable routes that cannot cross each other. Finding the minimum cost array cable layout thus amounts to a vehicle routing problem with the additional constraints that the routes must be embedded in the plane. For this problem, both exact and heuristic methods are of interest. We optimize cable layouts for real-world OWFs by a hop-indexed integer programming formulation, and develop a heuristic for computing layouts based on the Clarke and Wright savings heuristic for vehicle routing. Our heuristic computes layouts on average only 2% more expensive than the optimal layout. Finally, we present two problem extensions arising from real-world OWF cable layouts, and adapt the integer programming formulation to one of them. The thus obtained optimal layouts are up to 13% cheaper than the actually installed layouts.     

Virtual path layouts optimizing total hop count on ATM tree networks

This paper presents some algorithmic results concerning virtual path layouts for the one-to-many communication problem in ATM tree networks. The ATM network model is based on covering the network with a layout of virtual paths, under some constraints on the allowed load, namely, the number of paths that can share an edge. The quality measure used is the hop count, namely, the number of edges traversed between two vertices that need to communicate. Whereas most former results concerned the maximum hop count of the virtual path layout, our interest here is in measuring its total hop count, or alternatively its average hop count. The paper presents a dynamic programming algorithm for planning ATM network layouts with minimal total hop count for one-to-many requirements under load constraints over the class of tree networks.     

A linear programming embedded probabilistic tabu search for the unequal-area facility layout problem with flexible bays

In this paper, a probabilistic tabu search (PTS) approach is proposed to solve the facility layout problem (FLP) with unequal area departments. For the representation, the flexible bay structure (FBS), which is a very common layout in many manufacturing and retail facilities, is used. In this paper, the FBS is relaxed by allowing empty spaces within bays, which results in more flexibility in assigning departments into bays. In addition, departments are allowed to be located more freely within the bays, and they can have different side lengths as long as they are within the bay boundaries and do not overlap. To achieve these goals, department shapes and their locations within bays are determined LP. A PTS approach is developed to search an overall layout structure that describes relative positions of departments for the relaxed-FBS (RFBS). The proposed LP embedded PTS–RFBS approach is used to solve thirteen FLP instances from the literature with varying sizes. The comparative results show that this approach is very promising and able to find new best solutions for several test problems.     

An efficient tabu algorithm for the single row facility layout problem

The general goal of the facility layout problem is to arrange a given number of facilities to minimize the total cost associated with the known or projected interactions between them. One of the special classes of the facility layout problem is the Single Row Facility Layout Problem (SRFLP), which consists of finding an optimal linear placement of rectangular facilities with varying dimensions on a straight line. This paper first presents and proves a theorem to find the optimal solution of a special case of SRFLP. The results obtained by this theorem prove to be very useful in reducing the computational efforts when a new algorithm based on tabu search for the SRFLP is proposed in this paper. Computational results of the proposed algorithm on benchmark problems show the greater efficiency of the algorithm compared to the other heuristics for solving the SRFLP.     

An integrated fuzzy simulation-fuzzy data envelopment analysis algorithm for job-shop layout optimization: The case of injection process with ambiguous data

This paper puts forward an integrated fuzzy simulation-fuzzy data envelopment analysis (FSFDEA) algorithm to cope with a special case of single-row facility layout problem (SRFLP). Discrete-event-simulation, a powerful tool for analyzing complex and stochastic systems, is employed for modeling different layout formations. Afterwards, a range-adjusted measure (RAM) is used as a data envelopment analysis (DEA) model for ranking the simulation results and finding the optimal layout design. Due to ambiguousness associated with the processing times, fuzzy sets theory is incorporated into the simulation model. Since the results of simulation are in the form of possibility distributions, the DEA model is treated on a fuzzy basis; therefore, a recent possibilistic programming approach is used to convert the fuzzy DEA model to an equivalent crisp one. The proposed FSFDEA algorithm is capable of modeling and optimizing small-sized SRFLP’s in stochastic, uncertain, and non-linear environments. The solution quality is inspected through a real case study in a refrigerator manufacturing company.     

Detailed layout planning for irregularly-shaped machines with transportation path design

In order to obtain a competitive level of productivity in a manufacturing system, efficient machine or department arrangements and appropriate transportation path structures are of considerable importance. By defining a production system’s basic structure and material flows, the layout determines its operational performance over the long term. However, most approaches proposed in the literature provide only a block layout, which neglects important operational details. By contrast, in this paper, we introduce approaches to planning layouts at a more detailed level. Hence, this present paper introduces an integrated approach which allows a more detailed layout planning by simultaneously determining machine arrangement and transportation paths. Facilities to be arranged as well as the entire layout may have irregular shapes and sizes. By assigning specific attributes to certain layout subareas, application-dependent barriers within the layout, like existing walls or columns, can be incorporated. We introduce a new mathematical layout model and develop several improvement procedures. An analysis of the computational experiments shows that more elaborate heuristics using variable neighborhoods can generate promising layout configurations.     

An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem

The irregular strip packing problem is a combinatorial optimization problem that requires to place a given set of two-dimensional polygons within a rectangular container so that no polygon overlaps with other polygons or protrudes from the container, where each polygon is not necessarily convex. The container has a fixed width, while its length can change so that all polygons are placed in it. The objective is to find a layout of the set of polygons that minimizes the length of the container.We propose an algorithm that separates overlapping polygons based on nonlinear programming, and an algorithm that swaps two polygons in a layout so as to find their new positions in the layout with the least overlap. We incorporate these algorithms as components into an iterated local search algorithm for the overlap minimization problem and then develop an algorithm for the irregular strip packing problem using the iterated local search algorithm. Computational comparisons on representative instances disclose that our algorithm is competitive with other existing algorithms. Moreover, our algorithm updates several best known results.