An elitist strategy genetic algorithm using simulated annealing algorithm as local search for facility layout design

A well-planned arrangement of manufacturing departments on a two-dimensional planar region considerably increases the efficiency of its production systems, which is termed facility layout problem (FLP). Conventional layout design approach often designs intercell layout (determining exact location of each department on shop floor area) and flow path layout design of material handling system (MHS) step by step in a sequential manner. This results in suboptimal solutions for FLP. In this paper, an integrated approach is adopted to design the intercell layout and the flow path layout of MHS simultaneously. The quality of the final layout is evaluated by minimizing total material handling cost. Sequence pair (SP) representation is used for layout encoding. The translation from SP to layout is efficiently made by longest common subsequence (LCS) methodology. An elitist strategy genetic algorithm using simulated annealing (E-GASAA) as a local search mechanism is developed and tested with four test problem instances available in the literature. Elitist strategy is incorporated to enhance convergence characteristic of the proposed algorithm. It is found that the proposed E-GASAA is able to produce best solutions consistently for the test problem instance of different sizes within acceptable computational effort. In addition to that, we tried to reduce the computational load with the help of adopted LCS computation methodology and achieved a good improvement.     

A simulated annealing algorithm to find approximate Pareto optimal solutions for the multi-objective facility layout problem

In this article, we consider the facility layout problem which combines the objective of minimization of the total material handling cost and the maximization of total closeness rating scores. Multi-objective optimization is the way to consider the two objectives at the same time. A simulated annealing (SA) algorithm is proposed to find the non-dominated solution (Pareto optimal) set approximately for the multi-objective facility layout problem we tackle. The Pareto optimal sets generated by the proposed algorithm was compared with the solutions of the previous algorithms for multi-objective facility layout problem. The results showed that the approximate Pareto optimal sets we have found include almost all the previously obtained results and many more approximate Pareto optimal solutions.     

Artificial immune system-based algorithm for the unidirectional loop layout problem in a flexible manufacturing system

Facility layout design is a significant aspect of designing any manufacturing setup and it has a huge impact on the performance of the manufacturing system. Reductions in operating expenses in a manufacturing system is greatly achieved by a good layout design. The problem of finding an optimal layout is hard and deterministic techniques are not suitable for large-sized problems. In this paper, a two-phase layout design is developed. As a first phase of layout design, an artificial immune system (AIS) algorithm is proposed for solving the unidirectional loop layout problem with the consideration of both min_sum and min_max objectives. The computational results showed that the AIS algorithm is efficient in solving layout problems and producing good-quality solutions. In the second phase, shortcuts are introduced in the flow path of the loop layout to enhance the performance of the system. The position of the shortcut in the loop which gives the minimum material handling cost is discovered.     

A genetic algorithm for solving a multi-floor layout design model of a cellular manufacturing system with alternative process routings and flexible configuration

This paper presents a novel integer linear programming model for designing multi-floor layout of cellular manufacturing systems (CMS). Three major and interrelated decisions are involved in the design of a CMS; namely cell formation (CF), group layout (GL), and group scheduling (GS). A novel aspect of this model is concurrently making the CF and GL decisions to achieve an optimal design solution in a multi-floor factory. Other compromising aspects are: multi-floor layout to form cells in different floors is considered, multi-rows layout of equal area facilities in each cell is allowed, cells in flexible shapes are configured, and material handling cost based on the distance between the locations assigned to machines are calculated. Such an integrated CMS model with an extensive coverage of important manufacturing features has not been proposed before and this model incorporates several design features including alternative process routings, operation sequence, processing time, production volume of parts, duplicate machines, machine capacity, new machine purchasing, lot splitting, material flow between machines, intra-cell layout, inter-cell layout, multi-floor layout and flexible configuration. The objective is to minimize the total costs of intra-cell, inter-cell, and inter-floor material handling, new machines purchasing and machine processing. Two numerical examples are solved by the Lingo software to verify the performance of the proposed model and illustrate the model features. Sensitive analysis is also implemented on some model parameters. An improved genetic algorithm (GA) is proposed to derive near-optimal solutions for the integrated model because of its NP hardness. It is then tested using several problems with different sizes and settings to verify the computational efficiency of the developed algorithm in comparison to a classic simulated annealing algorithm and the Lingo software. The obtained results show the efficiency of proposed GA in terms of objective function value and computational time.     

Parallel variable neighborhood search for solving fuzzy multi-objective dynamic facility layout problem

In spite of the classic approaches of solution of dynamic facility layout problem, which only material handling and rearrangement costs are considered as objective function, these problems are the multi-objective problems. In this paper, a mixed integer linear programming formulation is presented for multi-objective dynamic facility layout problem concerning flexible bay structure. In addition, three current objectives in dynamic facility layout problems including minimizing material handling and rearrangement costs, maximizing adjacency rate, and minimizing shape ratio difference have been considered. Also, for solving this problem, two methods including the GAMS software and proposed parallel variable neighborhood search (PVNS) algorithm are used. So, it is worth mentioning that four test problems are solved by them, and the results show that the proposed PVNS algorithm is more efficient than the GAMS software.     

Concurrent cell formation and layout design using scatter search

Two key decisions in designing cellular manufacturing systems are cell formation and layout design problems. In the cell formation problem, machine groups and part families are determined while in the facility layout problem the location of each machine in each cell (intra-cell layout) and the location of each cell (inter-cell layout) are decided. Owing to the fact that there are interactions between two problems, cell formation and layout design problem must be tackled concurrently to design a productive manufacturing system. In this research, two problems are investigated concurrently. Some important and realistic factors such as inter-cell layout, intra-cell layout, operations sequence, part demands, batch size, number of cells, cell size, and variable process routings are incorporated in the problem. The problem is formulated as a mathematical model. Three different methods are described to solve the problem: multi-objective scatter search (MOSS), non-dominated genetic algorithm (NSGA-II), and the ε-constraint method. The methods are employed to solve nine problems generated and adopted from the literature. Sensitivity analysis is accomplished on the parameters of the problem to investigate the effects of them on objective function values. The results show that the proposed MOSS algorithm performs better than NSGA-II and produces better solutions in comparison to multi-stage approaches.     

A genetic algorithm for the inter-cell layout and material handling system design

The traditional optimization processes for the cell system layout (CSL) and material handling system in cellular manufacturing systems (CMSs) were carried out sequentially and separately. The solutions obtained by this means can be far from the total optimum. In this paper, an integrated approach to the problem is proposed that attempts to design CSL and flow path structure simultaneously. The cells in question are assumed to be shape-fixed and have pre-determined pickup/delivery (P/D) stations. A sequence-pair based CSL-generating algorithm allows cells to be placed at any possible position on a continuous floor plan and leads to a corresponding feasible CSL. A grid graph for the CSL is accordingly constructed to provide possible flow paths for the layout. Then, the sum of the traveling distances, determined by the shortest path algorithm, is used to evaluate the CSL. These steps are embedded into a genetic algorithm (GA) that searches the solution space to obtain optimal layouts based on the contour distances between the P/D stations. Computational results demonstrate that the run time required to solve the test problems is quite acceptable given the long-term nature of facility layout decisions. Moreover, a comparison of the computational results with the existing methods indicates that the proposed approach is a viable alternative for effectively generating layout designs for CMS.     

Performance Analysis of Intelligent Robust Facility Layout Design

Design of a robust production facility layout with minimum handling cost (MHC) presents an appropriate approach to tackle facility layout problems in a dynamic volatile environment, in which product demands randomly change in each planning period. The objective of the design is to find the robust facility layout with minimum total material handling cost over the entire multi-period planning horizon. This paper proposes a new mathematical model for designing robust machine layout in the stochastic dynamic environment of manufacturing systems using quadratic assignment problem (QAP) formulation. In this investigation, product demands are assumed to be normally distributed random variables with known expected value, variance, and covariance that randomly change from period to period. The proposed model was verified and validated using randomly generated numerical data and benchmark examples. The effect of dependent product demands and varying interest rate on the total cost function of the proposed model has also been investigated. Sensitivity analysis on the proposed model has been performed. Dynamic programming and simulated annealing optimization algorithms were used in solving the modeled example problems.     

不确定需求下的设备动态布局方法

针对现有车间设备动态布局方法存在的不足,在考虑产品需求不确定性对布局性能稳定性影响的基础上,提出了一种结合模糊理论与改进遗传算法的不等面积设备动态布局方法。分析了产品需求不确定性及其随时间变化特性,引入了三角模糊数描述不确定产品需求;通过分析各生产阶段间的设备重组过程,将动态布局转化为数个静态布局,构建了基于柔性区域结构的不确定需求动态布局模型。结合三角模糊数运算及排序方法与自适应局部搜索机制提出了改进遗传算法,以物料搬运及设备重组费用总和为优化目标,解决不确定需求下的不等面积设备动态布局问题。通过算例测试和实例分析,验证了所提方法的有效性和实用性。     

INTEGRATION OF CELL FORMATION AND LAYOUT DESIGN IN THE UNIDIRECTIONAL LOOP MATERIAL HANDLING ENVIRONMENT

A two-phase approach is proposed to deal with the integration problem in the loop layout. Tabu search is applied to cell construction in phase 1 to minimize the inter-cell flow, and the heuristic for layout design is used as phase 2 to optimize the sum of intra-cell and inter-cell transportation cost. The final computational results demonstrate the validation of the two-phase approach.     

Dynamic facility layout problem based on flexible bay structure and solving by genetic algorithm

Finding positions of departments on the plant floor for multiple periods while minimizing the sum of material handling and rearrangement costs is the base consideration of dynamic facility layout problems (DFLP). In this paper, a new kind of DFLP using flexible bay structure is studied. In a plant layout, based on flexible bay structure, departments are assigned to parallel bays in a plant floor. Departments could be free oriented and may have unequal areas as well as a mixed integer programming formulated to find optimal solutions. Due to complexity, only small-size problems could be solved in logical time while using exact methods. Therefore, a genetic algorithm (GA) was proposed to solve this optimization problem. This method was tested on some test problems of the DFLP literature. The results show the effectiveness of the proposed algorithm.     

Tabu search for multiple-criteria manufacturing cell design

Cellular manufacturing (CM) is an important application of group technology (GT) in which families of parts are produced in manufacturing cells or in a group of various machines. Cell design/formation is the first step in the design of cellular manufacturing systems. Many efforts have been made towards cell design taking into consideration multiple criteria. This paper presents a Pareto-optimality-based multi-objective tabu search (MOTS) algorithm to the machine-part grouping problems with multiple objectives: minimizing the weighted sum of inter-cell and intra-cell moves and minimizing the total cell load variation A new approach is developed to evaluate the non-dominance of solutions produced by the tabu search. Comparisons between MOTS and the genetic algorithm (GA) are done and the results show that MOTS is quite promising in multi-objective cell design .     

A comprehensive approach to facility layout design and cell formation

Group technology (GT) and a facility layout problem share a common factor to optimize, which is the “Intercell Flow or Material Handling Flow”. Most group technology-based approaches use binary part-machine incidence matrix for cell formation. Impacts of flow volume analysis between machine pairs have not been analyzed in the design of cellular manufacturing systems. It is important to analyze the placement of machine cells for reduced material handling costs at the grouping stage itself. This paper develops a method to integrate GT philosophy with a facility layout problem using “From–Between” relationship chart as a tool. A new optimization technique with a “from–to chart” as the primary input, is used to determine the cell formation. A modified grouping efficiency measure is used to determine the efficiency of grouping. A genetic algorithm-based approach is used for machine cell placement within a layout matrix. Cells formed using the proposed approach show reduced intercell flows, high grouping efficiencies and reduced material handling costs when cells are placed in a layout grid compared to existing cell formation approaches.     

A simulation-based approach for risk assessment of facility layout designs under stochastic product demands

In traditional facility layout design method, the facility layout is governed by the flow intensity between departments, which is the product flow quantity between departments. A facility layout design must maintain its efficiency over time while coping with the uncertainty in product demand. An error in the product demand assessment can render the layout inefficient with respect to material handling costs. Analytical models for the determination of the risk involved in a facility layout design are difficult to derive when the problem of size and complexity increases. This paper presents a simulation-based method for predicting the uncertainty associated with the layout. The validation of the simulation approach against analytical procedures is first detailed. The methodology for the simulation based approach is provided. Three scenarios of increasing complexity and size are also detailed. Results from case studies have shown that the procedure results in reduction of risk as high as 80%.     

<Emphasis Type="Bold">Plant Layout Computerised Design: Logistic and Relayout Program (LRP)</Emphasis>

Markets are affected by strong competition in terms of continuous innovation of products and processes, high customer satisfaction and low cost of production. In order to achieve these strategic results it is recommended, or necessary, to rectify lack of organisation. For instance, the increasing costs due to material handling, force factories to check the facility layout and, when necessary, to improve it. The evaluation of a prospective improvement requires a large effort and a well-established skill. The study and the optimisation of plant layout is a strategic activity. This paper represents the last step of a research program on the automatic design of plant layout. The aim is to support the design activity of plant layout by means of an integrated approach, taking into account many criteria, both quantitative and qualitative. In particular, this paper presents a global approach, based on material flow and activity relationships. It is carried out using new software, called LRP (layout and re-layout program), introduced by the authors. A real application in a factory, specialising in the production of electronic devices, is presented.     

A cost based evaluation of a zones formation algorithm in tandem AGV systems

In tandem AGV systems, the shop floor is partitioned into a group of non-overlapping zones, where each is served by a single dedicated vehicle. In this paper, a two phase algorithm for partitioning tandem AGV systems is proposed. The proposed algorithm serves a number of objectives including minimizing the total handling cost, minimizing the maximum workload in the system and minimizing the number of between-zones trips. The algorithm is equipped with parameters to enable the user to select one of these objectives or to optimize a combination of them. The performance of the algorithm regarding the objective of minimizing the material handling cost is evaluated by experimental design. The experiment is based on comparing the solutions obtained by the proposed algorithm with best solutions obtained by a ‘rationalized exhaustive enumeration’ procedure for a group of randomly generated problems. The analytical results showed that the proposed algorithm obtains an average of 99.53% efficiency, and that none of the considered factors has a main significant effect on the performance of the algorithm in regards to the objective of minimizing the total material handling cost, however, a few of the interaction effects are significant.     

基于改进模拟植物生长算法的多层可重构设施布局方法

在对模拟植物生长算法进行改进的基础上,建立了一种多层可重构设施布局方法。该方法引入了空间填充曲线来表征布局方案,可以实现任意两个设施之间的互换,确保设施不被分割;考虑了柔性面积需求、设施形状约束系数、电梯能力约束等因素,使获得的方案更加接近实际情况;建立了以物流成本和重构成本为绩效评价目标的多层可重构设施布局模型;对模拟植物生长算法进行了改进,在此基础上设计了多层可重构设施布局寻优改善算法,该算法具有设置参数简单、全局寻优、搜索速度较快等特点。最后用算例说明了该方法的有效性。     

考虑双联卡箍约束的航空发动机多管成束敷设优化方法

为解决航空发动机多管路成束敷设问题,提出了一种基于双联卡箍约束和改进NSGA-Ⅱ的管路敷设优化方法。提出一种基于混沌反向学习机制和Levy变异算子的改进NSGA-Ⅱ算法,以改善算法收敛性和非支配解分布性。为解决管路和卡箍的装配约束和设计耦合关系,建立了基于双联卡箍约束的路径模式,生成卡箍和路径控制点,综合考虑管路敷设与卡箍布置规则,基于改进NSGA-Ⅱ设计管路-双联卡箍敷设算法,对卡箍位姿参数和管路路径同时求解。根据多管端口相对位置,提出基于聚类分析的管路分组及敷设序列规划方法,调用管路-双联卡箍敷设算法完成多管成束规划。所提敷设方法在管路设计阶段即考虑卡箍布置问题,实现了双联卡箍布置和多管成束敷设的同时自动规划,最后通过测试函数和敷设算例验证了所提方法的有效性。     

Managing a new multi-objective model for the dynamic facility layout problem

In today’s manufacturing environment, the facility layout needs to be adaptable to changes. This situation requires the solution of the dynamic layout problem. But in previous studies of dynamic facility layout optimization, the main objective is to minimize the sum of the re-arrangement and material handling costs. To be more realistic, each of these cost terms in objective function might be of different importance to decision makers. In this research, the objective function has been considered as two distinct functions. This formulation enables decision makers to apply their own views. On the other hand, in the proposed model the adjacency-based objective aims at maximizing adjacency scores between the facilities in a facility layout has also been used. The proposed multi-objective model was defined as a complex combinatorial optimization problem. It has also been the objective of the present study to evaluate some of the known methods that have been proposed to solve the multi-objective problem. The results for test problems showed that the population based metaheuristic methods are useful tools in solving proposed model.     

基于NSGA-II的多目标设备动态布局方法

对多个计划期内需求可预测的车间动态设备布局问题进行了研究.针对这一多目标、多约束的问题,以物流搬运和重布局费用之和、非物流关系以及面积利用率作为优化目标,将动态布局问题转化为重布局过程和多个子计划期的静态布局问题,构建了针对不等面积设备的动态多期布局问题的连续型多目标优化模型.采用带精英策略的非支配遗传算法(Non-dominated Sorting Genetic Algorithm II,NSGA-II)进行求解,克服了传统加权法求解多目标问题时加权系数难以确定和无法保证多目标同时优化的缺点,求解得到Pareto解集,供决策者根据企业实际情况优中选优.通过实例验证了本方法的有效性.