A heuristic procedure for the integrated facility layout design and flow assignment problem

We present an efficient iterative heuristic procedure for solving the integrated layout design and product flow assignment problem. The layout design decisions involve planar location of unequal-area machines with duplicates. The product flows are assigned to machines according to the product processing routes. The integrated decision problem is a nonlinear mixed integer model which cannot be efficiently solved using classical methods for large problems. We propose a novel integrated heuristic procedure based on the alternating heuristic, a perturbation algorithm and sequential location heuristic. Since the alternating heuristic between facility layout design and product-machine assignment sub-problems terminates with local optima, we developed a perturbation algorithm based on assignment decisions. The results of an experimental study show that proposed procedure is both efficient and effective in identifying quality solutions for small to very large-sized problems.     

A shape-based block layout approach to facility layout problems using hybrid genetic algorithm

In this paper, a shape-based block layout (SBL) approach for solving facility layout problem with unequal-areas and fixed-shapes is presented. The SBL approach employs hybrid genetic algorithm to find good solution. The existing algorithms for the problem of assigning positions to unequal-area and fixed or approximated shape departments within a given building area can produce solutions with some drawbacks, which require extensive manual revision to create practical layouts and produce irregular building shapes and too much unusable spaces. The objective function of SBL approach minimizes total material handling cost and maximizes space utilization. Experimental results show that the SBL approach is able to improve solution and it can create more practical layout than that of existing approaches.     

Hybrid genetic algorithms for constrained placement problems

When solving real-world problems, often the main task is to find a proper representation for the candidate solutions. Strings of elementary data types with standard genetic operators may tend to create infeasible individuals during the search because of the discrete and often constrained search space. This article introduces a generally applicable representation for 2D combinatorial placement and packing problems. Empirical results are presented for two constrained placement problems, the facility layout problem and the generation of VLSI macro-cell layouts. For multiobjective optimization problems, common approaches often deal with the different objectives in different phases and thus are unable to efficiently solve the global problem. Due to a tree structured genotype representation and hybrid, problem-specific operators, the proposed approach is able to deal with different constraints and objectives in one optimization step     

考虑多重覆盖的应急设施多级协同布局鲁棒优化

应急设施的合理布局是灾后实现物资高效、公平和稳定供应的重要保障.针对突发自然灾害的不确定性,研究基于多重覆盖的应急设施多级协同布局鲁棒优化问题.首先,提出多级设施选址下的多重覆盖水平函数,以最小覆盖水平和期望总成本最优为目标,建立应急设施多级协同选址双目标优化模型;其次,应用基数不确定集和p-鲁棒方法构建两类鲁棒优化模型,分别研究场景内不确定需求和随机场景对设施布局的影响;最后,以湖南省救灾备荒种子储备库选址为例进行实证分析,验证所提出优化模型的有效性.研究结果表明:多级协同布局相比传统布局方案更具优势;鲁棒优化模型能够有效应对不确定情形和随机场景下的物资需求;决策者的风险偏好程度和预算水平对设施协同布局有重要影响,需对二者进行综合权衡.     

An integrated circuit layout design system

An integrated circuit layout design system is presented. The system is effectively combined with a combinatorial optimization technique and man/machine interaction. This optimization technique allows wiring and placement of components to be determined simultaneously. By means of a c.r.t. display, the layout design of an integrated circuit chip is finally improved.     

An improved genetic algorithm for facility layout problems having inner structure walls and passages

This study proposes an improved genetic algorithm (GA) to derive solutions for facility layouts that are to have inner walls and passages. The proposed algorithm models the layout of facilities on gene structures. These gene structures consist of a four-segmented chromosome. Improved solutions are produced by employing genetic operations known as selection, crossover, inversion, mutation, and refinement of these genes for successive generations. All relationships between the facilities and passages are represented as an adjacency graph. The shortest path and distance between two facilities is calculated using Dijkstra's algorithm of graph theory. Comparative testing shows that the proposed algorithm performs better than other existing algorithms for the optimal facility layout design. Finally, the proposed algorithm is applied to ship compartment layout problems with the computational results compared with an actual ship compartment layout.Scope and purposeFacility layout problems (FLPs) concerning space layout optimization have been investigated in depth by researchers in many fields, such as industrial engineering, management science, and architecture, and various algorithms have been proposed to solve FLPs. However, these algorithms for the FLP cannot consider inner structure walls and passages within the block plan (or available area). They are also limited to a rectangular boundary shape of the block plan. Therefore, these algorithms could not be directly applied to problems having the curved boundary shape such as ship compartment layout, and an innovative algorithm which can treat such problems is needed. In this study, an improved genetic algorithm (GA) is proposed for solving problems having the inner structure walls and passages within an available area of a curved boundary. A comparative test of the proposed algorithm was performed to evaluate its efficiency. Finally, the proposed algorithm is applied to ship compartment layout problems with the computational results compared with an actual ship compartment layout. From the comparative test and the preliminary applications made to the ship's compartment layout, we demonstrate that the proposed algorithm has the ability to solve the FLPs having the inner structure walls and passages within the available area of the curved boundary.     

Reinforcement layout and sizing optimization of composite submarine sail structures

A topology optimization approach that makes use of nonlinear design variable-to-sizing relationship is presented. A finite element (FE) model is used to describe the loaded structure, but unlike the microstructure approach, the decision is whether an element in the continuum should have maximum or minimum cross-sectional dimension while its material density and moduli are held constant. This approach is applied to reinforcement layout optimization of a very large and geometrically complex Composite Advanced Sail (CAS) structure under an asymmetric wave slap loading condition. A high-complexity model in the form of multilayered shell and a low-complexity model in the form of stiffened shell are developed for the layout optimization of the CAS and solved for minimum strain energy. The effects of constraints such as buckling instability on optimal placement of internal stiffeners are also explored. Based on the results of the layout optimization, a new FE model of the CAS is developed and optimized for minimum weight. Depending upon the degree of variability in skin thickness, the results show a weight saving of up to 19% over the original model.     

Discrete cooperative particle swarm optimization for FPGA placement

Particle swarm optimization (PSO) is a stochastic optimization technique that has been inspired by the movement of birds. On the other hand, the placement problem in field programmable gate arrays (FPGAs) is crucial to achieve the best performance. Simulated annealing algorithms have been widely used to solve the FPGA placement problem. In this paper, a discrete PSO (DPSO) version is applied to the FPGA placement problem to find the optimum logic blocks and IO pins locations in order to minimize the total wire-length. Moreover, a co-operative version of the DPSO (DCPSO) is also proposed for the FPGA placement problem. The problem is entirely solved in the discrete search space and the proposed implementation is applied to several well-known FPGA benchmarks with different dimensionalities. The results are compared to those obtained by the academic versatile place and route (VPR) placement tool, which is based on simulated annealing. Results show that both the DPSO and DCPSO outperform the VPR tool for small and medium-sized problems, with DCPSO having a slight edge over the DPSO technique. For higher-dimensionality problems, the algorithms proposed provide very close results to those achieved by VPR.     

Solving an extended multi-row facility layout problem with fuzzy clearances using GA

Multi-row facility layout problem (MRFLP) is a class of facility layout problems, which decides upon the arrangement of facilities in some fixed numbers of rows in order to minimize material handling cost. Nowadays, according to the new layout requirements, the facility layout problems (FLPs) have many applications such as hospital layout, construction site layout planning and layout of logistics facilities. Therefore, we study an extended MRFLP, as a novel layout problem, with the following main assumptions: 1) the facilities are arranged in a two-dimensional area and without splitter rows, 2) multiple products are available, 3) distance between each pair of facilities, due to inaccurate and flexible manufacturing processes and other limitations (such as WIPs, industrial instruments, transportation lines and etc.), is considered as fuzzy number, and 4) the objective function is considered as minimizing the material handling and lost opportunity costs. To model these assumptions, a nonlinear mixed-integer programming model with fuzzy constraints is presented and then converted to a linear mixed-integer programming model. Since the developed model is an NP-hard problem, a genetic algorithm approach is suggested to find the best solutions with a minimum cost function. Additionally, three different crossover methods are compared in the proposed genetic algorithm and finally, a sensitivity analysis is performed to discuss important parameters.     

A multi objective genetic algorithm for the facility layout problem based upon slicing structure encoding

This paper proposes a new multi objective genetic algorithm (MOGA) for solving unequal area facility layout problems (UA-FLPs). The genetic algorithm suggested is based upon the slicing structure where the relative locations of the facilities on the floor are represented by a location matrix encoded in two chromosomes. A block layout is constructed by partitioning the floor into a set of rectangular blocks using guillotine cuts satisfying the areas requirements of the departments. The procedure takes into account four objective functions (material handling costs, aspect ratio, closeness and distance requests) by means of a Pareto based evolutionary approach. The main advantage of the proposed formulation, with respect to existing referenced approaches (e.g. bay structure), is that the search space is considerably wide and the practicability of the layout designs is preserved, thus improving the quality of the solutions obtained.     

Effective Memetic Algorithms for VLSI design = Genetic Algorithms + local search + multi-level clustering

Combining global and local search is a strategy used by many successful hybrid optimization approaches. Memetic Algorithms (MAs) are Evolutionary Algorithms (EAs) that apply some sort of local search to further improve the fitness of individuals in the population. Memetic Algorithms have been shown to be very effective in solving many hard combinatorial optimization problems. This paper provides a forum for identifying and exploring the key issues that affect the design and application of Memetic Algorithms. The approach combines a hierarchical design technique, Genetic Algorithms, constructive techniques and advanced local search to solve VLSI circuit layout in the form of circuit partitioning and placement. Results obtained indicate that Memetic Algorithms based on local search, clustering and good initial solutions improve solution quality on average by 35% for the VLSI circuit partitioning problem and 54% for the VLSI standard cell placement problem.     

一种改进的VLSI电路有效布局算法

采用重心矩形约束[1]进行VLSI布局会出现以下问题：(1)布局边界的浪费,出现不可利用的小区域;(2)放置模块时可能会出现模块放置在实际有效区域内却因为重心约束成为非法放置。为了解决该问题,本文提出了一种改进文献[1]的VLSI布局启发式算法：通过设计模块的优先顺序进行合理布局,并辅助于边界矩形来解决重心矩形约束出现的问题;对模块布局放置的多个可能位置进行比较,并将其放置在优先度最高的适当区域。用Banchmark（ami33,ami49）和文献[1]的数据进行测试,结果表明新算法：（1）算法简洁高效,运行时间短;（2）布局结果明显好于文献[1]。     

基于NSGA Ⅱ的多目标车间设施布局优化方法

针对多品种批量生产系统,提出了一种基于NSGAII的多目标车间设施布局优化方法。以物料搬运量(或搬运成本)、非物流关系强度、设施所需总面积为优化目标建立了一类多目标优化模型;针对模型设计了一种改进的非支配排序多目标遗传算法;通过案例分析验证了该方法的有效性。     

Top-Down Layout for Hierarchical Custom Design

Champ, a chip floor-plan program, and Alpha, an automatic cell placement and routing system, provide a method for hierarchical custom VLSI design that is highly automated and completely top-down. The system can handle standard cell blocks as well as macro cells such as RAMs, ROMs, PLAs. Champ consists of initial block placement and block packing Designers can execute initial block placement either manually or automatically using a method based on attractive-repulsive forces. Block packing is performed automatically or interactively through the moving and reshaping of blocks, which is done as the chip boundaries are being shrunk. Following the floor-plan design, Alpha automatically executes cell placement and routing. Using Champ/Alpha, only seven mandays are needed to design a 20,000-gate VLSI layout, using a predesigned standard cell library and predesigned macro cells.     

一种基于子结构分析的基本块重排算法

基本块重排是一类通过重新排布基本块在存储中的位置,以减少转移开销和指令cache失效率的编译优化技术.介绍了一种基于子结构分析的基本块重排算法.该算法通过统计剖视信息中控制流图的边执行频率,基于处理器转移预测策略构建转移开销模型和基本块排布收益模型.算法采用局部子结构优化的策略,改善基本块在存储中的排列顺序,从而减少转移开销,并提高指令cache的使用率,改善程序的总体性能.在UniCore处理器平台上进行了实验.实验结果表明,与其他基本块重排算法相比,该基本块重排算法在更大程度上减少转移开销和指令cache失效率的同时,其时间复杂度保持为O(n×logn).     

基于模拟退火离散粒子群算法的芯片堆叠热布局优化

针对芯片堆叠的热布局优化问题,使用热叠加模型,结合热传导公式,以所有芯片温度的最高值作为评价指标,确定出三维芯片堆叠热布局优化的适应度函数;然后采用模拟退火离散粒子群算法对芯片热布局进行优化。得到优化后的芯片堆叠布局方案,并用Icepak软件对优化后的布局进行仿真验证。仿真结果表明：采用模拟退火离散粒子群算法对三维芯片堆叠进行热布局优化可以使温度分布更加均匀,最高温度明显降低。     

自收缩性的演化算法及其在布局优化问题中的应用

布局优化问题是现代工程应用中广泛存在的一类组合优化问题,但在理论上它却属于NPC(NP-Complete)问题,如果需考虑性能约束,则问题将更难于求解。论文基于演化算法自适应,自组织,自学习的特性,针对布局优化问题自身的特点,提出了一种自收缩性的演化算法(SCEA)。该算法采用浮点编码方式,定义了二元实向量类型的适应值及适应值间的严格偏序关系。算法借鉴日常生活中的一个简单事实—振动容器则装物更多,引入了三类自适应性的收缩算子(其中第三类特别适用于带性能约束的布局优化问题)。此外,文中使用了对带约束的函数优化问题特别有效的多父体杂交算子,并且针对带性能约束的布局优化问题,提出了“零性能约束初始化”过程。文后,引用了两个带性能约束的布局优化问题的已知例子和一个作者构造的较大规模布局优化问题的例子,实验结果表明,前两个问题对比目前已知最好结果无论在求解时间或结果的精度上均有较大突破,后一个问题也获得了相当好的结果,从而充分验证了算法的有效性和可行性。     

求解板材排料问题的新方法

§１．引言 板材排料问题是家具、包装、地毯等行业常见的一个问题．它是指将一批不同种类的待排矩形件全部排放在给定的板材上,使排料所用的板材数量尽可能地少,即板材的利用率尽可能地高．实质上是一个组合优化的二维布局问题,从计算复杂性来看,是一个ＮＰ完全问题,但至今还没有找到解决该问题的有效多项式时间算法．寻求其近似最优解的近似算法是目前解决该问题的途径之一． 国内外已有不少学者在布局问题方面作了一些研究．如有用模拟退火算法解决大规模排料问题,但其解过分依赖于模拟退火算法冷却进度表的参数的选取,而且该算法…     

Towards measuring the effectiveness of a facilities layout

Performance measurement models are essential to support various decision making problems that may arise during life cycle of a facilities layout. Available models are only suitable for early stages in the design phase of life cycle. However, measurement models have a great consequence in other phases also such as production planning, control and when modification to be incorporated due to the changes in market demand, which happens very often in today's global competition. In addition, the existing models have considered only material handling cost as the performance measurement factor. Nevertheless, the empty travel of material handling equipment, layout flexibility and area utilisation have a significant contribution towards the layout effectiveness. It is therefore necessary to have a measurement model to determine the facilities layout's effectiveness by considering all significant factors. A measurement model considering a set of three layout effectiveness factors—facilities layout flexibility (FLF), productive area utilisation (PAU) and closeness gap (CG)—is developed in our research. The proposed model will enable the decision-maker of a manufacturing enterprise to analyse a layout in three different aspects, based on which they can make decision towards productivity improvement. This paper mainly discusses about the measurement of the CG. The CG is developed with respect to the objective of bringing closer the highly interactive facilities/departments. The CG presented in this paper extends other related works by incorporating numerous aspects of layout that include empty travel of material handling equipment, information flow, personnel flow and equipment flow.