A modified-procedure for converting a dual graph to a block layout

The main difficulty associated with the application of graph theory to facilities layout is the conversion of the dual graph into a block layout. Hassan and Hogg (1989) presented a procedure to solve this problem. This paper gives some comments and critiques related to the problem and demonstrates that their procedure does not always work in a manner consistent with the adjacencies specified by the dual graph. In addition, rules for improving the procedure are developed. The paper is written in note format and the reader needs to refer to Hassan and Hogg (1989) for understanding the procedure and undefined notations.     

A new approach to the block layout problem

The main problem concerned with applying graph theory to facilities layout is the conversion of the dual graph to a block layout. This paper presents a new method of producing a planar orthogonal layout or floorplan of a set of facilities subject to adjacency and area constraints. It improves upon previous approaches by accepting any maximal planar graph representing the adjacencies as input. Simple selection criteria for choosing the next facility to be inserted into the floorplan are used. Further, any sensible orthogonal shape for the facilities in the resulting floorplan can be generated.     

Some observations on converting a dual graph into a block layout

Al-Hakim (1992) claims the existence of some pitfalls with the procedure of Hassan and Hogg (1989) for converting a dual graph into a block layout. This note explains the necessary conditions in order for the procedure of Hassan and Hogg to work, and illustrates that Al-Hakim's examples were not solved because they deviated from these conditions. The note also discusses the suggestions of Al-Hakim and points out that they will not succeed in addressing all situations     

Evaluation of an application of graph theory to the layout problem

When designing a facility layout it is desirable to obtain an optimum design which satisfies certain necessary relationships among departments. Recent research has indicated that applying graph theory to the layout problem can result in the development of improved solutions, but little can be found to indicate how much better the resultant solutions are. The objectives of this paper are to develop a graph theory approach based on research experience and suggestions of Moore, Carrie and Seppanen, to develop a general computer program implementing the procedure and to compare its performance with that of CRAFT, CORELAP and ALDEP. The comparisons are based upon the adjacency relationships satisfied in the resultant layouts. The procedure finds the graph G equivalent to the problem being solved and then generates one of its maximal spanning trees, which after being transformed to its ‘string’ equivalent, is used to extract a maximal planar sub-graph of G. The dual of this sub-graph represents the desired solution. This approach allowed two usual problems to be avoided; firstly, testing for planarity of a graph and secondly, testing for cycles in the generation of a maximal spanning tree. The resultant PL/1 program, called graph and string-oriented layout (GASOL), is used to solve a standard set of eight problems, i.e. Nugent's problem set. The generated layouts were then compared to those obtained by CRAFT, CORELAP, and ALDEP on the same set of problems. The results of these comparisons showed that GASOL satisfies more of the number of layout adjacencies and achieves higher ‘scored’ layout arrangements than either CRAFT, CORELAP, or ALDEP, As a consequence more flow or material handling volume is included in a GASOL layout. The increase in the number of adjacencies ranges from a low of 53% to a high of 63.1%. This computational experience suggests that a graph theory approach to the layout problem can provide significantly improved results over those obtained by these existing computerized layout routines, with moderately increased computational times.     

On constructing a block layout by graph theory

This paper examines the problem of developing block layouts using graph theory. It is shown that there are several limitations associated with such layouts, particularly when facility relationships are represented quantitatively by a from-to chart. A modification to conventional construction-type layout procedures is presented which allows a graph theoretic block layout to be developed, regardless of the type of facility relationships used, and without performing all the steps required in the graph theoretic approach. This new method helps to avoid the limitations of the approach and alleviate its computational burden.     

The Vertex Splitting Algorithm for facilities layout

The graph theoretic facility layout problem (GTFLP) seeks the best spatial arrangement of a set of facilities, which minimizes the total transportation cost of material flow between facilities, or maximizes total facility adjacency benefits. The GTFLP has applications in arranging rooms within a building floorplan, placing machines on a factory floor, controls on an instrument panel, or components on a circuit board. For this reason, the GTFLP is an important problem within industrial design. The GTFLP comprises two phases: the generation of a highly weighted maximal planar graph (MPG), whose edges specify adjacencies required in the layout, and the drawing of an orthogonal geometric dual to this MPG, called the block plan, under given area requirements for each facility. The first phase is NP-complete, and has been researched extensively; in the absence of a polynomial time algorithm, it appears there is little future for further research in this area. The second phase however has received far less attention due to the difficulties in not only determining algorithms for generating layouts, but also the hurdles encountered in automating these methods. This paper presents a new approach to finding a block plan from an arbitrary MPG, with facility area requirements.     

A hybrid approach for concurrent layout design of cells and their flow paths in a tree configuration

The layout design of multiple-cell automated manufacturing systems includes cell layout design and flow path layout design. Traditional layout methods often treat these two as separate problems and the sequence for solving them is usually cell layout first and flow path layout later. However, approaches of these kinds have one major drawback, that is, they may produce cell layouts that are awkward or difficult for designers to conduct flow path layouts, or cell layouts that do not turn out to be as good as expected after flow path layouts have been performed. Other drawbacks of traditional layout methods include irregular shapes of cells, inaccurate calculations of flow distances, etc. This paper addresses the layout problem of cells and their connecting flow paths in a tree configuration. The proposed layout procedure is designed to avoid the aforementioned drawbacks of traditional layout methods by emphasizing concurrent layout design of cells and flow paths. It combines a search algorithm and mathematical programming models. The search algorithm has a backtracking procedure that allows one to explore alternative layouts, while the mathematical programming models help one obtain accurate layouts of cells and flow paths. The proposed layout procedure also interacts with designers and allows designers to include their qualitative consideration into the layout design. As a result, one can obtain more accurate and good-quality layouts with the proposed layout procedure.     

The machine layout within a TFT-LCD bay with a multiple-stacker crane in-line stocker

In this paper, we study the machine layout problem in a TFT-LCD (thin-film transistor liquid-crystal display) bay with a multiple-stacker crane in-line stocker. Unlike other material-handling systems, such as automated guided vehicles and conveyors that only have a transportation function, in-line stockers have both transportation and storage functions. They rely on stacker cranes to perform their transportation function. The in-line stocker in a TFT-LCD bay is often divided into zones. Each zone is served by a stacker crane. Due to its multiple-zone in-line stocker, solving a TFT-LCD bay's machine layout requires us to determine not only the positions of the machines, but also the zone division design. The objectives include the minimisation of total flow distance and the workload balance between stacker cranes. We propose a layout procedure that adopts heuristic and mathematical approaches to assist us in accomplishing the aforementioned tasks. An example problem mimicking a real-case problem was solved to illustrate the proposed layout procedure. The layout design found by the proposed layout procedure was validated with computer simulations. It was also compared with layouts obtained by approaches proposed by other researchers. The simulation and comparison results demonstrate the capability of the proposed layout method in producing a feasible and good machine layout in a TFT-LCD bay with a multiple-stacker crane in-line stocker.     

The value of the shortest loop covering all work centers in a manufacturing facility layout

In this study we develop mathematical models to design circular material flow systems. We first develop a tight formulation to find the shortest loop covering all work centers within a manufacturing facility layout. The shortest loop is an attractive solution for most types of conveyors and power-and-free systems, where the length of the flow path is the major driver of the total cost. We develop a primal as well as a dual graph formulation and discuss their one-to-one correspondence in node-edge as well as in connectivity constraints. Our solution times outperform other optimization models available for the facility layout shortest loop design problem. We then approach trip-based material handling, such as automated guided vehicle systems, where the total loaded and empty trip distance is the major driver of the total cost. The problem in these systems evolves into concurrent design of the loop, pickup and dropoff station, and the empty vehicle dispatching policies. On the foundation of the shortest loop model, we propose a decomposition heuristic for design of trip-based flow systems. Computational results indicate that the heuristic provides high quality and robust solutions.     

RMS中工件路径网络生成方法

利用图论建立RMS中工件路径网络生成模型。给出设备物理布局生成的3种算法：设备物理规划布局算法、基于二次布置问题(QAP)模型的VMC设备物理布局算法以及已有设备物理布局算法。给出AGV路径网络生成算法、AGV路径网络生成改进算法、可替代路径网络生成算法,包括节点间最短路径寻找子算法、路径网络预处理子算法。算法的输入为表示重构对象节点间距离信息的距离矩阵文件和表示某生产周期多工艺路线的流量文件,输出为优化的路径网络。用Visual C 实现了以上算法,实例测试验证了算法的正确性。     

SHAPE: A construction algorithm for area placement evaluation

A construction algorithm for the plant layout problem is presented. The problem is formulated as a generalized assignment problem with the objective of minimizing total movement costs. The solution algorithm is a heuristic that utilizes an analogy to the special case of locating one item within a warehouse repetitively for placing and constructing departments. The procedure is sensitive to the departmental areas and approaches the problem as one of area placement. The algorithm provides a large degree of regularity in departmental shape and overall layout outline without having to pre-specify any particular shape. The compact and simple computational nature of the algorithm makes it suitable for adaption to an interactive microcomputer environment.     

The relationship between the physical layout of the work stations and the productivity of a saturated single-hoist production line

Over the past fifteen years a growing number of research workers have become interested in the problem of how to optimize the productivity of treatment lines fed by one of several hoists. Their work has concentrated mainly on scheduling the moves of the hoist. However, the layout of the stations is always taken as a constant. The aim of this paper is to underline the relationship between the physical layout of the stations and the productivity of a treatment line. We focus on saturated single-hoist production lines. After introducing a model of this problem, we focus on a particular class of layout that is commonly used by industrial users. We show first that this class does minimize the hoist moving time during a cycle time. In the following part, we show that this particular class of layout is, however, not dominant in all cases for maximizing the productivity of the line. Before concluding our study, we propose a branch and bound algorithm to process the optimal layout for maximizing the productivity of a saturated single-hoist production line. The studies show that this procedure is very efficient.     

A simulated annealing algorithm based on a closed loop layout for facility layout design in flexible manufacturing systems

Facility layout design problems in flexible manufacturing systems (FMS) differ from traditional facility design problems and are more difficult to solve because there are more constraints that must be considered (i.e., cell shape, cell orientation, pick-up and drop-off point positions). The focus of this paper is on the closed loop type layout, which is based on a predetermined layout pattern. This layout pattern is commonly found in manufacturing settings since it requires a simplified material handling system configuration and since it facilitates a modular and expandable layout structure. The open-field type layout problem, where there is no predetermined layout pattern, may potentially have a more efficient configuration, since there are fewer restrictions. However, this problem is more difficult to solve and may result in configurations that are not desirable due to the lack of structure or modularity. The procedure developed in this paper improves the efficiency of the closed loop configuration by changing the rectangular shape of the loop to different sizes. In many cases, the resulting closed loop layout proves to be as efficient as the open field layout. A simulated annealing procedure (SA-CL) is used to search for the configuration that minimizes the total material handling costs. A comparison of the results with existing methods indicates that, based on solution quality and computational time, the SA-CL offers a favourable alternative for efficient layout design.     

A construction algorithm for the machine layout problem with fixed pick-up and drop-off points

A construction algorithm which considers some practical aspects of the machine layout problem is presented. The methodology considers machine dimensions and their input and output locations with flow data. The layout is generated on a continuum, considering the best configuration and orientation of input and output locations of machines to minimize the material flow cost. The location procedure searches along the boundary of existing machines. A bi-criterion optimization approach is proposed to overcome one of the weaknesses inherited by construction procedures. The suggested construction procedure is implemented on a microcomputer and applied to solve some test problems with encouraging results.     

A two-stage simulated annealing procedure for block layout problems

Rules for setting simulated annealing control parameters are proposed for block layout problems where different material-handling devices are dynamically assigned to individual material movements as layout solutions are perturbed. Recognizing the high cost of computing materials-handling cost in this type of problem, the rules are based on adapting an existing two-stage simulated annealing procedure to accelerate convergence. Experimental results suggest that the application of these rules yields solution quality comparable with other single and two-stage simulated annealing algorithms but with significantly fewer re-evaluations of the objective function.     

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 genetic algorithm for optimal unequal-area block layout design

The use of a genetic algorithm (GA) to optimise the binary variables in a mixed-integer linear programming model for the block layout design problem with unequal areas that satisfies area requirements is analysed. The performance of a GA is improved using a local search through the possible binary variables assignment; results encourage the use of this technique to find a set of feasible solutions for the block layout design with more than nine departments.     

Matching Based Interactive Facility Layout

This paper is concerned with the development of an interactive block layout system which utilizes b-matching as the optimization component. The objective function utilized by the b-matching is to maximize a weighted sum of adjacent departments. The b-matching model is a relaxation of the layout problem, hence human interaction is critical to overcome the factors not captured by the model.     

Optimal solution for the flow path design problem of a balanced unidirectional AGV system

An optimal flow path layout (FPL) design method is introduced as a handy tool for an automated guided vehicle (AGV) system planing stage. The problem is analysed and formulated by linear mixed-integer programming. A procedure based on the branch-and-bound depth-first search technique is proposed to solve the FPL problem. The procedure is implemented as an efficient computer program and yields an optimal solution in a small number of iterations. Using the transportation model for calculating the required and optimal flow of empty vehicles, system balance is achieved. Finally, two examples are given. A simple illustrative example is discussed to demonstrate the procedure, and a realistic FPL problem with 23 nodes, 66 arcs and nine pick-up/delivery stations is solved.     

Retracted: Stability analysis of blocky structure system using discontinuity layout optimization

The collapse mechanism identification and limit load calculation of block composite structures are essential tasks in practical engineering. In this work, the discontinuity layout optimization (DLO) is utilized to simulate a stable blocky system structure under static and pseudostatic loading by considering soil–structure interaction effects. The program refers to the discretization of the system under consideration by utilizing the potential slip lines to connect nodes. Then, linear programming is applied to identify the critical layout. The DLO procedure is extended to mimic rotations in the approximate simulation of rotational and translational failures along boundaries, thus simulating the mechanism on the rotating block. The simulated failure mechanism and collapse load are consistent with the experimental observations and numerical modeling results. Furthermore, the procedure is applied to two potential practical applications: the stability analysis of a jointed rock slope and concrete masonry retaining wall. The results show that the DLO is a simple but scientific method for identifying the mechanism of the critical failure of blocky structures.