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.     

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.     

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.     

Solving a fixture configuration design problem using genetic algorithm with learning automata approach

Proper fixture design is crucial to workpiece quality assurance in manufacturing. Incorrect fixture design may lead to workpiece deformation during machining. The fixture configuration design is one of the important aspects of fixture design. This paper deals with fixture layout optimization problem. The objective is to minimize the norm of all the passive contact forces satisfying Coulomb friction constraint, work-piece static equilibrium constraint and contact constraint, for the entire cutting operation. To solve this problem, the paper proposes Genetic Algorithm with Learning Automata (GALA) algorithm, which is a population based interconnected learning automata algorithm incorporating genetic operators. The algorithm enjoys the good characteristics of both GA and LA. It is validated with an example of face milling operation. The optimal layout is found to be in tune with empirical facts. Also, for the further investigation of the algorithm, it has been tested on a different problem sets and a comparative study is carried out.     

Solution of facility layout problems with pickup/drop-off locations using random search techniques

Due to non-polynomial hardness, the facility layout problem (FLP) becomes more critical when pickup/drop-off (P/D) locations are considered in the design of an open field layout under a manufacturing environment. This paper proposes an indigenous model of the facility layout problem based on random search techniques and its solution methodology using a genetic algorithm (GA), simulated annealing (SA) and a hybrid algorithm (HA). The paper illustrates the performance of different random search operating parameters in solving the facility layout problem considering P/D locations along the periphery of rectangular machine blocks. The preliminary experiments were carried out on three facility layout test problems having six, eight and ten machines in order to fix the different operating parameters such as crossover operator, crossover rate, initial temperature, temperature reduction factor, number of generations, population size, etc. The results of extensive preliminary experimentation were utilized to solve facility layout problems having 12 and 18 machines and, finally, were compared with the existing procedures in the literature. The experimental tables and related analysis performed via the solution methods by applying GA, SA and HA revealed that random-search-based modeling of FLP considering P/D and its solution as suggested in this paper is worth pursuing.     

抽象物体的2n-叉树表示及其在高维布局问题中的应用

针对高维几何布局问题中布局物体的建模问题,提出2^n－叉树方法,在一般维度下系统地给出了抽象物体的叉树表示法的构造。物体的2^n0－叉树表示是物体八叉树表示理论的向高维扩展,同时也包容八叉树方法向低 维问题的推广。     

A simulated annealing procedure for single row layout problems in flexible manufacturing systems

In this paper we address a layout problem in flexible manufacturing systems (FMSs). A layout type that has been extensively implemented in FMSs is the single row machine layout. In such a configuration machines are arranged along a straight track with a material handling device moving jobs from one machine to another. The single row layout problem (SRLP) deals with the optimal arrangement of the machines for the above configuration. We propose a simulated annealing (SA) heuristic for the solution of SRLP. Extensive computational results, and ways to improve the performance of the SA algorithm through parameter fine-tuning procedures, are reported.     

Sequence selection of stock sheets in two-dimensional layout problems

This paper introduces an optimization algorithm for finding the sequence of stock sheets to use in a two-dimensional bill-of-materials layout problem, when there is more than one size of stock sheet to choose from and when the method for laying each single sheet is already chosen. To reduce computer time and memory requirements for solving this problem, two other heuristic approaches are also proposed. Tests on data from a Wisconsin manufacturer show that the use of multiple sheet sizes can materially reduce the trim losses achieved from a layout system that uses only a single sheet size. The heuristic methods introduced represent progressive stages in the trade-off between layout quality and the computer time and memory required to achieve the layout.     

用蚁群算法解决动态设施布置问题

给出了动态设施布置的数学模型,介绍了一种解决组合优化问题的有效算法--蚁群算法,并用该算法成功地解决了某汽车零件制造厂生产车间的设施布置问题,得到了优良的解决方案,证明了该算法的优越性.     

Advances in discrete material handling system design

The paper presents an outline of the research done in the area of facility layout and discrete material handling system design. The objective of this paper is to observe the trend in the literature in the area of manufacturing system design and predict the direction of future research in this area. The paper attempts to link the areas of facility layout design and material flow network design. A methodology for solving the integrated design problem is presented. An algorithm which aids in solving the combined pick-up/drop-off point location and material handling flowpath problem is outlined.     

基于改进粒子群算法的制造单元设施布局问题研究

为避免单元系统布局和单元内设施布局分开孤立研究所导致的问题解空间损失,利用并行工程的思想对单元布局的两个环节集成考虑,对单元系统布局、单元内设施布置、设施摆放方向进行同时描述,并建立多目标集成优化模型。针对模型的复杂性,设计了改进粒子群算法,算法吸收了遗传算法中的交叉操作算子,具有跳出局部最优解的能力。最后通过求解单元设施布置实例,验证模型和算法的有效性。     

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.     

On solving facility layout problems using genetic algorithms

Tam and Chan (1998) present a parallel genetic algorithm approach to solve the facility layout problem. They adopt a slicing tree representation of a floor layout. The coding scheme represents a layout as a string with three parts. This paper demonstrates the difficulties in applying classical crossover and mutation operators for solving facility layout problems. The paper modifies the representation of Tam and Chan and introduces a new preserving operation, referred to as transplanting , that manages to produce feasible offspring. It also studies the applicability of other genetic operations such as diagonal crossover and cloning in generating feasible offspring. The paper is written in a note format and the reader may refer to Tam and Chan for more details.     

Route planning for automated guided vehicles in a manufacturing facility

Automated guided vehicles (AGVs) are widely used in manufacturing and transporting facilities for the movement of material from one location to another. Research in this area is directed toward the development of a path layout design and routing algorithms for movements of materials. The problem is to design a path layout and a routing algorithm that will route the AGVs along the bi-directional path so that the distance travelled will be minimized. This paper presents a bi-directional path flow layout and a routing algorithm that guarantee conflict-free, shortest-time routes for AGVs. Based on the path layout, a routing algorithm and sufficient, but necessary, conditions, mathematical relationships are developed among certain key parameters of vehicle and path. A high degree of concurrency is achieved in vehicle movement. Routing efficiency is analysed in terms of the distance travelled and the time required for AGVs to complete all pickup and drop-off jobs. Numerical results are presented to compare the performance of the proposed model. The research provides the foundation for a bi-directional path layout design and routing algorithms that will aid the designer to develop complicated path layouts.     

Flexible guidepath design for automated guided vehicle systems

We address the problem of unidirectional guidepath layout design for automated guided vehicle systems- A two-step layout design method to consider both loaded and empty vehicle movements is developed to guarantee a complete layout design. First, the flow path selection (FPS) problem is formulated to design guidepath layout with the objective of minimizing loaded vehicle movements. Both a mathematical model and a heuristic algorithm for FPS are presented. Since AGV guidepath layouts are used by both loaded and empty vehicles, the FPS does not guarantee a closed or complete layout design. For the case when an incomplete or unclosed layout is produced from the first step, a complementary layout design (CLD) approach to convert the incomplete layout into complete one with the consideration of empty vehicle movements is considered in the second step. A heuristic for the CLD problem is developed. An example problem is used to illustrate the whole design approach.     

二维不规则件优化排样的小生境遗传算法

首先采用组合矩形包络算法将二维不规则零件的排样问题转化为矩形件的排样问题;然后将遗传算法与小生境技术相结合,寻找排样件在排样时的最优次序及各自的旋转角度;最后用“最低水平线与填充算法相结合”策略的启发式排样算法实现自动排样。实例表明,该算法是有效的。     

FLEXPERT: facility layout expert system using fuzzy linguistic relationship codes

Linguistic variables, fuzzy statements and fuzzy algorithms, from the theory of fuzzy sets, provide suitable tools to solve ill-defined problems. Unlike conventional techniques that deal only with discrete conditions, like 'on' and 'off', and precise numerical values, fuzzy logic offers an alternate technique that deals with non-discrete conditions, such as 'absolutely important', 'quite important' and 'less important'. This paper presents a new approach, based on the theory of fuzzy logic, to solve the facility layout problem. The proposed approach considers the multicriteria nature of the layout problem and the fuzziness of the input data through the integration of an expert system and a fuzzy algorithm with a facility layout program. The system generates the best layout that satisfies die qualitative as well as the quantitative constraints on the layout problem. This facilitates the incorporation of the knowledge of facility layout experts. A knowledge-based system, named FLEXPERT, has been developed to implement the new approach.     

不规则零件优化排样的神经网络混合优化算法

 提出一种利用人工神经网络求解不规则件排样问题的混合优化方法.该方法首先把排样和制造工艺联系起来,将多边形各边向外扩充,为零件预留加工余量;然后采用自组织特征映射模型（SOM）和Hopfield人工神经网络相结合的方法,运用SOM神经网络对初始在板材内随机排布的不规则零件进行平移,逐步减小不规则零件之间的重叠面积,求得各零件的最优位置,再运用Hopfield神经网络对平移后的零件旋转,进行迭代运算,当能量函数达到稳定状态时,得到各排样零件的最优旋转角度组合,实现自动排样.算法可以解决不规则件和矩形件在规则板材以及不规则板材上的排样问题,实例证明了该算法的有效性和实用性.     

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.     

A genetic algorithm and queuing theory based methodology for facilities layout problem

Facilities layout, being a significant contributor to manufacturing performance, has been studied many times over the past few decades. Existing studies are mainly based on material handling cost and have neglected several critical variations inherent in a manufacturing system. The static nature of available models has reduced the quality of the estimates of performance and led to not achieving an optimal layout. Using a queuing network model, an established tool to quantify the variations of a system and operational performance factors including work-in-process (WIP) and utilisation, can significantly help decision makers in solving a facilities layout problem. The queuing model utilised in this paper is our extension to the existing models through incorporating concurrently several operational features: availability of raw material, alternate routing of parts, effectiveness of a maintenance facility, quality of products, availability of processing tools and material handling equipment. On the other hand, a queuing model is not an optimisation tool in itself. A genetic algorithm, an effective search process for exploring a large search space, has been selected and implemented to solve the layout problem modelled with queuing theory. This combination provides a unique opportunity to consider the stochastic variations while achieving a good layout. A layout problem with unequal area facilities is considered in this paper. A good layout solution is the one which minimises the following four parameters: WIP cost, material handling cost, deviation cost, and relocation cost. Observations from experimental analysis are also reported in this paper. Our proposed methodology demonstrates that it has a potential to integrate several related decision-making problems in a unified framework.