A reexamination of the distance-based facility layout problem

In this paper we qualitatively and numerically compare basic modeling approaches to the distance-based facility layout problem and the types of result obtained from them. In the process we observe that when the facility layout problem is modeled as a QAP, one will not necessarily obtain an optimal solution to the layout problem even if the QAP is solved to optimality. We also propose an alternative distance measure, namely, EDIST, which is based on the expected distance between two departments. We illustrate how the EDIST measure addresses some of the well-known shortcomings associated with the centroid-to-centroid distance measure.     

An improved heuristic approach for multi-objective facility layout problem

Multi-objective facility layout problem (mFLP) generates a different layout by varying objectives weights. Since the selection of objective weights in mFLP is critical, stages of designing layout having multiple objectives, the objective weights therefore play an important role in the layout design of mFLP. In practice, it is selected randomly by the layout designer based on his/her past experience that restricts the layout designing process completely designer dependent and thus the layout varies from designer to designer. This paper aims to resolve the issues of selecting the objective weight for each objective. We propose four methods to determine objective weight which makes the design process of mFLP completely designer independent.     

An iterative facility layout algorithm

In this paper we present a facility layout algorithm that iterates between a genetic algorithm with a slicing tree representation and a mixed-integer program with a subset of the binary variables set via the genetic algorithm. The genetic algorithm is very good at finding low-cost solutions while maintaining shape constraints on the departments. The slicing tree representation and the mixed-integer program are compatible in terms of layout representation, with the mixed-integer program representation more general. The mixed-integer program allows us to relax the last remaining constraints of the slicing tree representation of the genetic algorithm. We present our genetic algorithm and the iterative algorithm, while illustrating their performance on test problems from the literature. In 10 of the 12 problems, new lower best-cost solutions are found.     

Coupling ant colony optimization and the extended great deluge algorithm for the discrete facility layout problem

This article uses a hybrid optimization approach to solve the discrete facility layout problem (FLP), modelled as a quadratic assignment problem (QAP). The idea of this approach design is inspired by the ant colony meta-heuristic optimization method, combined with the extended great deluge (EGD) local search technique. Comparative computational experiments are carried out on benchmarks taken from the QAP-library and from real life problems. The performance of the proposed algorithm is compared to construction and improvement heuristics such as H63, HC63-66, CRAFT and Bubble Search, as well as other existing meta-heuristics developed in the literature based on simulated annealing (SA), tabu search and genetic algorithms (GAs). This algorithm is compared also to other ant colony implementations for QAP. The experimental results show that the proposed ant colony optimization/extended great deluge (ACO/EGD) performs significantly better than the existing construction and improvement algorithms. The experimental results indicate also that the ACO/EGD heuristic methodology offers advantages over other algorithms based on meta-heuristics in terms of solution quality.     

An improved facility layout construction method

This study presents a new distance-based facility layout construction technique. Given a two-dimensional (i.e. single-floor) facility layout construction problem in which the order of placement of individual departments is known (a challenging problem in itself), the technique presented herein proposes the use of sub-departments and expected distance functions instead of centroid-to-centroid distances for the placement of departments. In this paper an expected distance function is defined as the probabilistic expectation of the particular distance metric of interest (rectilinear, Euclidean, etc.) in which the parameters involved are defined by random vectors in 2-dimensional Euclidean space. This study presents an enhanced facility layout construction technique that incorporates several enhancements over the well-known systematic layout procedure (SLP). The goal herein is to minimise the error induced by the use of the centroid-to-centroid distances between the departments inherent to the SLP.     

An exact penalty function method for optimising QAP formulation in facility layout problem

A quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new approach is introduced to solve this discrete optimisation problem. First, the discrete optimisation problem is transformed into an equivalent nonlinear optimisation problem involving only continuous decision variables by introducing quadratic inequality constraints. The number of variables, however, remains the same as the original problem. Then, an exact penalty function method is applied to convert this transformed continuous optimisation problem into an unconstrained continuous optimisation problem. An improved backtracking search algorithm is then developed to solve the unconstrained optimisation problem. Numerical computation results demonstrate the effectiveness of the proposed new approach.     

Heuristic approach for solving the multi-objective facility layout problem

A new heuristic approach for the generation of preferred objective weights to solve the multi-objective facility layout problem is presented. By applying a multi-pass halving and doubling procedure, a paired comparison method based on the strength of preference among objectives given by the decision-maker is developed. Furthermore, a ‘prior test’ is proposed to examine the consistency of the paired comparison matrix. An efficient method to transform the inconsistent matrix into a consistent one so the result can closely approximate the decision-maker's original assessments is also offered. The geometric mean method is then employed to obtain the objective weights and the final solution. There are five phases in the proposed heuristic approach. The first generates a basic solution; the second involves constructing a paired comparison matrix by using the multi-pass halving and doubling procedure; the third identifies the consistency of the paired comparison matrix; the fourth transforms the inconsistent matrix into a consistent one; and the fifth generates the preferred weights and obtains the facility layout solution. An illustrative example is given to demonstrate an application of the proposed approach for solving the multi-objective facility layout problem.     

A branch-and-bound algorithm for the single-row equidistant facility layout problem

In this paper, we deal with the single-row equidistant facility layout problem (SREFLP), which asks to find a one-to-one assignment of n facilities to n locations equally spaced along a straight line so as to minimize the sum of the products of the flows and distances between facilities. We develop a branch-and-bound algorithm for solving this problem. The lower bound is computed first by performing transformation of the flow matrix and then applying the well-known Gilmore–Lawler bounding technique. The algorithm also incorporates a dominance test which allows to drastically reduce redundancy in the search process. The test is based on the use of a tabu search procedure designed to solve the SREFLP. We provide computational results for problem instances of size up to 35 facilities. For a number of instances, the optimal value of the objective function appeared to be smaller than the best value reported in the literature.     

Simulated annealing based parallel genetic algorithm for facility layout problem

The facility layout problem (FLP), a typical combinational optimisation problem, is addressed in this paper by implementing parallel simulated annealing (SA) and genetic algorithms (GAs) based on a coarse-grained model to derive solutions for solving the static FLP with rectangle shape areas. Based on the consideration of minimising the material flow factor cost (MFFC), shape ratio factor (SRF) and area utilisation factor (AUF), a total layout cost (TLC) function is derived by conducting a weighted summation of MFFC, SRF and AUF. The evolution operations (including crossover, mutation, and selection) of GA provide a population-based global search in the space of possible solutions, and the SA algorithm can lead to an efficient local search near the optimal solution. By combing the characteristics of GA and SA, better solutions will be obtained. Moreover, the parallel implementation of simulated annealing based genetic algorithm (SAGA) enables a quick search for the optimal solution. The proposed method is tested by performing a case study simulation and the results confirm its feasibility and superiority to other approaches for solving FLP.     

New Tabu search heuristics for the dynamic facility layout problem

A manufacturing facility is a dynamic system that constantly evolves due to changes such as changes in product demands, product designs, or replacement of production equipment. As a result, the dynamic facility layout problem (DFLP) considers these changes and is defined as the problem of assigning departments to locations during a multi-period planning horizon such that the sum of the material handling and re-arrangement costs is minimised. In this paper, three tabu search (TS) heuristics are presented for this problem. The first heuristic is a simple TS heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic TS heuristic. To test the performances of the heuristics, two sets of test problems from the literature are used in the analysis. The results show that the second heuristic out-performs the other proposed heuristics and the heuristics available in the literature.     

A new simulated annealing algorithm for the facility layout problem

In this paper we present an application of simulated annealing to facility layout problems with single and multiple floors. The facility layout problem is highly combinatorial in nature and generally exhibits many local minima. These properties make it a suitable candidate for simulated annealing. Using a new candidate layout generation routine and spacefilling curves, we develop an improvement-type layout algorithm based on simulated annealing that considers an expanded set of department exchanges. The resulting algorithm achieves low-cost solutions that are much less dependent on the initial layout than other approaches. We compare the performance of the simulated-annealing based algorithm with both steepest-descent and randomized approaches from the literature. Unlike other simulated annealing papers which typically present a statistical experiment to evaluate the effect of numerous control settings, all the experiments presented in this paper were conducted with control settings that are constant or easily specified. This approach facilitates the application of the proposed algorithm to real-life facility layout problems in both single and multiple floor facilities. Although the algorithm presented here can be applied to many types of facilities, our primary focus is on production facilities.     

基于损失函数的随机设施布局优化分析

现有的随机设施布局问题的优化方法或是优化总物料处理成本的均值以获得最鲁棒的布局,或是优化其方差以获得最稳定的布局,但两者均只优化了总物料处理成本随机特征中的一个方面.通过引入田口损失函数的概念,建立了新的随机设施布局优化模型,对总物料处理成本的均值和方差同时进行优化求解,相比于现有的优化方法,新方法得到的布局形式能够使系统同时获得较好的鲁棒性和稳定性.     

A cross-entropy approach to the single row facility layout problem

The single row facility layout problem is to arrange a given number of facilities along a straight line so as to minimise the total cost associated with the interactions between the facilities. In this paper, a metaheuristic algorithm based on the cross-entropy method, incorporating a local search procedure and symmetry-breaking techniques, is developed to solve this problem. The proposed algorithm has been tested on some widely used benchmark instances. The computational results show that the proposed algorithm has found the optimal or the best solutions known so far for the instances of size with up to 100 facilities and is competitive with some existing algorithms.     

An interactive approach to computer aided facility layout

In all manufacturing and service industries the layout of facilities is an important determinant of operating efficiency and costs. Whenever the flow of materials or people is complex, computerized procedures offer the only feasible means of developing and evaluating alternative arrangements.

This paper describes an interactive approach to construction and improvement procedures which utilizes a refresh graphics terminal (IMLAC)linked to a PRIME 400 computer. Input includes projected materials flow, estimates of material handling costs, 2-D templates of machines, etc., and an initial layout which can be either existing, proposed, or constructed using the procedure INLAYT. A heuristic procedure, S-ZAKY, utilizes multi-pairwise facility exchange to develop improved layouts based upon an analysis of materials flow. The improved layout is displayed in detail alongside the initial layout at the graphics terminal together with relevant material handling costs. The user may then accept, reject or modify the improved layout using the light-pen attached to the terminal before proceeding to successive iterations until satisfied. An economic evaluation of the projected savings in material handling costs against costs of relayout may be displayed at each iteration. On completion, a fully documented record including drawings may be obtained for every stage in the. procedure.     

Two-level modified simulated annealing based approach for solving facility layout problem

In this paper, we are considering the quadratic assignment model (QAP) of the facility layout problem (FLP) which is known to be NP-hard. We relax the integer constraints of the QAP and solve it on a commercially available package called LINGO 8. In the optimal solution so obtained, X_ij s take real values between zero and one. We identify promising X_ij s having a value strictly greater than 0.5 in the optimal solution and set them to one. We add the constraints (X_ij ?=?1) associated with promising X_ij s into the QAP (with integer restrictions) and resolve using LINGO 8. In all the cases attempted we obtained a superior feasible solution to the QAP which was further improved by the proposed modified simulated annealing (MSA) procedure. An encouraging comparative performance of this procedure is thus reported.     

Maximum weight matching and genetic algorithm for fixed-shape facility layout problem

To achieve efficient facility design, the problem of finding an initial slicing tree of a complete graph may influence the layout solutions in many ways. We introduce a maximum weight-matching algorithm to generate the slicing tree, which is used as an initial solution. This initial solution produces modifications to generate alternative layouts for further selection. The system employs a genetic algorithm (GA) as the search engine with a relationship weight function to obtain good solutions. The model is proposed to solve a fixed-shape layout problem. The research has made contributions to two areas. First, it defines a quality function for the clustering technique to generate an initial slicing tree. Second, it designs a process for generating layout alternatives that can take predetermined location constraints and weights based on relationships among facilities into consideration. We compare our initial slicing tree GA with other approaches in the literature. In addition, computational results to demonstrate the performance characteristics of our algorithm are also evaluated.     

Single-row equidistant facility layout as a special case of single-row facility layout

In this paper we discuss two particular layout problems, namely the Single-Row Equidistant Facility Layout Problem (SREFLP) and the Single-Row Facility Layout Problem (SRFLP). Our aim is to consolidate the two respective branches in the layout literature. We show that the SREFLP is not only a special case of the Quadratic Assignment Problem but also a special case of the SRFLP. This new connection is relevant as the strongest exact methods for the SRFLP outperform the best approaches specialised to the SREFLP. We describe and compare the exact approaches for the SRFLP, the SREFLP and Linear Arrangement that is again a special case of the SREFLP. In a computational study we showcase that the strongest exact approach for the SRFLP clearly outperforms the strongest exact approach tailored to the SREFLP on medium and large benchmark instances from the literature.     

Solving the facility and layout and location problem by ant-colony optimization-meta heuristic

This paper describes a heuristic algorithm for solving the plant/facility location problem by applying ant-colony optimization meta-heuristic. The facility location problem is discussed, and a mathematical formulation is presented. The problem is then modelled as a quadratic assignment problem. An ant algorithm is developed to solve the problem. The results reveal that the proposed algorithm can be adaptively constructed to solve discrete plant location problems. This has been applied to a set of known test problems and appears to be able to compete with other current solutions with encouraging results.     

A heuristic approach on the facility layout problem based on game theory

Facility layout problems are related to the location of all facilities in a plant. Numerous research works related to facility layout have been published. The applicability of these various existing models may be limited by the fact that they all ignore competitive reactions to one's actions. In addition to external competitors, some internal problems of system such as material handling system design affect layout designs. For considering these effects, some researchers have investigated multi-objective approaches that in most cases lead to the optimisation of a weighted sum of score functions. The poor practicability of such an approach is due to the difficulty of normalising these functions and quantifying the weights. To the extent that competitors do react to a firm's actions and also the facility layout problem considers several conflicting objectives by distinct decision makers in the firm, the existing models may be oversimplifications of reality. In this paper, we modelled such a facility layout problem with conflicting objectives under a duopoly Bertrand competition as a game and solved it with a proposed simulated annealing meta-heuristic. Results obtained from solving some numerical examples confirm the effectiveness of the proposed model for the layout design.     

Visual facility layout design system

This paper presents an integrated visual facility layout design system to solve layout problems with geometric constraints on a continual planar site. The system employs a tabu search algorithm as the search engine with heuristic neighbourhood control and a manual interference mechanism to obtain good solutions. The Windows®-based system provides layout designers with a friendly environment that can automatically search a good solution aided by the visual inspection function. The visual inspection function is a mechanism embedded in the search process that dynamically displays the improvement status and allows manual adjustment of facility location during the search. The system also serves as a powerful tool for performing 'what if' analyses for layout designers.