Facility layout by collision detection and force exertion heuristics

Facility layout problem (FLP) considers the optimization of layout costs, primarily on the account of material handling costs. FLP can be solved via mathematical modelling, heuristic or metaheuristic approaches. This paper presents a novel heuristic approach for solving the unequal area FLP. Here, facilities are randomly generated points that exert forces on each other based on a relation matrix. In this setup, every point is a centroid of the respective facility shape and two heuristic methods are used to detect and consequently remove the collisions where the heuristic parameters influence the speed and quality of the final results. Furthermore, a graphic user interface (GUI) is designed to monitor performance of the proposed heuristic algorithm and modify its parameters while running if required. Finally, layout in higher dimensional space, facility rotation and future possible extensions are discussed.     

A genetic algorithm with the heuristic procedure to solve the multi-line layout problem

The paper presents a genetic algorithm-based meta-heuristic to solve the facility layout problem (FLP) in a manufacturing system, where the material flow pattern of the multi-line layout is considered with the multi-products. The matrix encoding technique has been used for the chromosomes under the objective of minimizing the total material handling cost. The proposed algorithm produces a table with the descending order of the data corresponding to the input values of the flow and cost data. The generated table is used to create a schematic representation of the facilities, which in turn is utilized to heuristically generate the initial population of the chromosomes and to handle the heuristic crossover and mutation operators. The efficiency of the proposed algorithm has been proved through solving the two examples with the total cost less than the other genetic algorithms, CRAFT algorithm, and entropy-based algorithm.     

基于Wang-Landau算法的动态设施布局方法

动态设施布局问题是设施在车间内多个阶段的布局规划问题。目前,针对动态设施布局问题,国内外学者对离散模型研究较多,而对连续模型的研究却较少。根据连续动态设施布局的特性与需求,构建了不等面积设施的动态设施布局连续模型。求解该模型的难点在于缺乏一种高效的布局优化方法。Wang-Landau算法是一种改进的蒙特卡罗算法。通过将Wang-Landau算法与空位点放置策略、外推移动策略、内压移动策略三种启发式策略相结合,提出一种基于Wang-Landau抽样的启发式算法,并以此求解该模型。使用文献中已有的测试算例对提出的算法进行测试,计算结果表明,所提出的算法在求解连续动态设施布局问题上是有效的。     

An artificial immune system based algorithm to solve unequal area facility layout problem

This study introduces an artificial immune system (AIS) based algorithm to solve the unequal area facility layout problem (FLP) with flexible bay structure (FBS). The proposed clonal selection algorithm (CSA) has a new encoding and a novel procedure to cope with dummy departments that are introduced to fill the empty space in the facility area. The algorithm showed consistent performance for the 25 test problem cases studied. The problems with 100 and 125 were studied with FBS first time in the literature. CSA provided four new best FBS solutions and reached to sixteen best-so-far FBS solutions. Further, the two very large size test problems were solved first time using FBS representation, and results significantly improved the previous best known solutions. The overall results state that CSA with FBS representation was successful in 95.65% of the test problems when compared with the best-so-far FBS results and 90.90% compared with the best known solutions that have not used FBS representation.     

Efficiency analysis for stochastic dynamic facility layout problem using meta-heuristic,data envelopment analysis and machine learning

The facility layout problem (FLP) is a combinatorial optimization problem. The performance of the layout design is significantly impacted by diverse, multiple factors. The use of algorithmic or procedural design methodology in ranking and identification of efficient layout is ineffective. In this context, this study proposes a three-stage methodology where data envelopment analysis (DEA) is augmented with unsupervised and supervised machine learning (ML). In stage 1, unsupervised ML is used for the clustering of the criteria in which the layouts need to be evaluated using homogeneity. Layouts are generated using simulated annealing, chaotic simulated annealing, and hybrid firefly algorithm/chaotic simulated annealing meta-heuristics. In stage 2, the nonparametric DEA approach is used to identify efficient and inefficient layouts. Finally, supervised ML utilizes the performance frontiers from DEA (efficiency scores) to generate a trained model for getting the unique rankings and predicted efficiency scores of layouts. The proposed methodology overcomes the limitations associated with large datasets that contain many inputs / outputs from the conventional DEA and improves the prediction accuracy of layouts. A Gaussian distribution product demand dataset for time period T = 5 and facility size N = 12 is used to prove the effectiveness of the methodology.     

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.     

Facility layout problems: A survey

Layout problems are found in several types of manufacturing systems. Typically, layout problems are related to the location of facilities (e.g., machines, departments) in a plant. They are known to greatly impact the system performance. Most of these problems are NP hard. Numerous research works related to facility layout have been published. A few literature reviews exist, but they are not recent or are restricted to certain specific aspects of these problems. The literature analysis given here is recent and not restricted to specific considerations about layout design.

We suggest a general framework to analyze the literature and present existing works using such criteria as: the manufacturing system features, static/dynamic considerations, continual/discrete representation, problem formulation, and resolution approach. Several research directions are pointed out and discussed in our conclusion.     

Handling qualitative aspects in Unequal Area Facility Layout Problem: An Interactive Genetic Algorithm

The Unequal Area Facility Layout Problem (UA-FLP) has been addressed using several methods. However, the UA-FLP has only been solved for criteria that can be quantified. Our approach includes subjective features in the UA-FLP, which are difficult to take into account with a more classical heuristic optimization. In this respect, we propose an Interactive Genetic Algorithm (IGA) that allows an interaction between the algorithm and the Decision Maker (DM). Involving the DM's knowledge in the approach guides the search process, adjusting it to his/her preferences at each generation of the algorithm. In this paper, we are concerned with assisting the DM in finding a good solution according with criteria that can be: subjective, unknown at the beginning or changed during the process, so that, the problem addressed differs from a classic optimization problem. In order to avoid overloading the DM, the whole population is classified into clusters by the fuzzy c-means clustering algorithm and only one representative element of each cluster is directly evaluated by the DM. A memory of the best solutions chosen by the DM is kept as a reference. The tests carried out show that the proposed IGA is capable of capturing DM preferences.     

基于遗传算法的设施布置研究

为了进行优良的设施布置,给决策者提供较好的布置方案,提出了变动邻近区域遗传算法。算法在解决设施布置问题时,改进了传统遗传算法中的不足,进而达到用最小成本获得最大效率的目的。通过实例应用,并进行了结果分析。算法在最终解个数、Pareto解个数、Pareto解的均匀程度等性能指标上均优于传统算法。实验结果表明,使用本算法使决策者能以较合理的数据来选择布置方案。     

一种多目标不等面积设施布局问题的启发式算法

多目标不等面积设施布局问题（UA-FLP）是将一些不等面积设施放置在车间内进行布局,要求优化多个目标并满足一定的限制条件。以物料搬运成本最小和非物流关系强度最大来建立生产车间的多目标优化模型,并提出一种启发式算法进行求解。算法采用启发式布局更新策略更新构型,通过结合基于自适应步长梯度法的局部搜索机制和启发式设施变形策略来处理设施之间的干涉性约束。为了得到问题的Pareto最优解集,提出了基于Pareto优化的局部搜索和基于小生境技术的全局优化方法。通过两个典型算例对算法性能进行测试,实验结果表明,所提出的启发式算法是求解多目标UA-FLP的有效方法。     

Solving resource-constrained project scheduling problems: Conceptual validation of FLP formulation and efficient permutation-based ABC computation

In this paper, we propose two alternative approaches, applying the facility layout problem (FLP) concept and integrating the permutation-based artificial bee colony (PABC) algorithm, to effectively tackle the resource-constrained project scheduling problem (RCPSP). In the FLP formulation, the constraints are expressed to design the activities in the space constructed by resource and temporal restrictions, without violating the precedence relationships and overlaps between the activities. For dodging the difficulty of the FLP-based model to treat large-sized instances of NP-hard RCPSP, the permutation representation scheme of the PABC algorithm is in turn introduced utilizing the artificial bee colony (ABC) process to search the best solution for RCPSP. In the procedure, a crossover operator and an insert operator following the update equation of the ABC algorithm are devised to augment the effectiveness of computation, whereas a shift operator subject to the resource utilization ratio value is suggested to diversify the solutions. The makespan is then obtained and improved with the assistance of a serial scheduling scheme and a double justification skill. Subsequently, the computational experiments conducted substantiate the conceptual validity of the proposed facility layout formulation for RCPSP and the comprehensive simulation shows the effectiveness of the PABC algorithm for RCPSP.     

一种改进遗传算法在生产车间设备布局中的应用

生产系统的设备布局设计是一个组合优化的问题。具有非线性,N P难等特性,常规方法较难以求解。文章通过创建生产系统设备布局的数学优化模型。引入了小生境技术,保持了种群的多样性。并且利用精英选择机制,自适应交叉和变异概率等手段,在使种群保持多样化的同时,增强了算法的全局和局部搜索能力,协调了遗传算法大范围粗糙搜索和小范围精细搜索之间的平衡,有效改善了早熟和过早收敛问题,并通过实例验证了其有效性。     

Approaches to uncertainties in facility layout problems: Perspectives at the beginning of the 21<Superscript>st</Superscript> Century

Production uncertainty is one of the most challenging aspects in manufacturing environments in the 21st century. The next generation of intelligent manufacturing is dynamically depending on the production requirements, and success in designing agile facilities is closely related to what extent these requirements are satisfied. This paper presents the most recent advancements in designing robust and flexible facilities under uncertainty. The focus is on exploring the way uncertainty is incorporated in facility design, namely dynamic and stochastic facility layout problems. Recent approaches are explored and categorized in detail, and previous approaches are briefly reviewed in the related categories. Furthermore, research avenues warranting exploration in the emerging field of facility design are also discussed.     

SLP和遗传算法结合在车间设备布局中的应用

用经典的系统布置设计结合遗传算法求解车间设备布局,以高效率获得满意的设计结果,弥补传统SLP设计过程中手工操作的繁琐迭代、易受主观影响、结果不稳定等缺点。并且通过对遗传算法的改进,增强了算法的全局和局部搜索能力。最后,通过实例验证了其有效性。     

An island model genetic algorithm for unequal area facility layout problems

The Unequal Area Facility Layout Problem (UA–FLP) has been addressed by various methods, including mathematical modelling, heuristic and metaheuristic approaches. Nevertheless, each type of approach presents problems such as premature convergence, lack of diversity, or high computational cost. In this paper, for the first time, an Island Model Genetic Algorithm (IMGA) is proposed to solve these subjects in the UA–FLP. The parallel evolution of several populations is used to maintain the population diversity and to obtain a wider sampling of the search space to obtain better quality solutions in fewer generations. Our novel approach was tested with a well-known set of problems taken from the literature and the results were compared with those of previous reports. In most cases, the results obtained by our novel approach improved on the previous results. Additionally, the proposed approach is able to reach good solutions with a wide range of problem sizes and in a reasonable computational time.     

A hybrid multi-population genetic algorithm for the dynamic facility layout problem

Due to inherent complexity of the dynamic facility layout problem, it has always been a challenging issue to develop a solution algorithm for this problem. For more than one decade, many researchers have proposed different algorithms for this problem. After reviewing the shortcomings of these algorithms, we realize that the performance can be further improved by a more intelligent search. This paper develops an effective novel hybrid multi-population genetic algorithm. Using a proposed heuristic procedure, we separate solution space into different parts and each subpopulation represents a separate part. This assures the diversity of the algorithm. Moreover, to intensify the search more and more, a powerful local search mechanism based on simulated annealing is developed. Unlike the available genetic operators previously proposed for this problem, we design the operators so as to search only the feasible space; thus, we save computational time by avoiding infeasible space. To evaluate the algorithm, we comprehensively discuss the parameter tuning of the algorithms by Taguchi method. The perfectly tuned algorithm is then compared with 11 available algorithms in the literature using well-known set of benchmark instances. Different analyses conducted on the results, show that the proposed algorithm enjoys the superiority and outperformance over the other algorithms.     

A graph grammar‐based approach for graph layout

As a two‐dimensional formal tool, graph grammars are capable of handling the layout problems of visual programming languages. Based on an edge‐based graph grammar (EGG), this paper proposes a novel layout approach that uses the unique features of EGG and overcomes the weakness of existing layout approaches. In order to make the approach rigorous yet concise, the graph grammar mechanisms with layout constraints and quantitative analysis techniques are combined together as an integrity. First, the basic notions of EGG are briefly introduced; second, the layout approach is presented that consists of two phases, ie, bottom‐up parsing and top‐down derivation. Finally, a case study is given by taking the standard flowchart as an example to demonstrate the working process of the proposed approach.     

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

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

Mathematical formulation and a new metaheuristic for the constrained double-floor corridor allocation problem

A layout plan for a manufacturing system that is designed without any facility constraints will most likely be infeasible when confronted with reality. Additionally, considering that land available for building industrial plants is limited and its cost is high, it is necessary to investigate the layout planning of two and multi-floor facilities. To address these shortages in the scientific literature, we focus on the double-floor corridor allocation problem (DFCAP) which covers a wide range of complex facility constraints, such as fixed floor constraints, fixed row constraints, fixed positioning constraints, mutual floor constraints, mutual row constraints, sequencing constraints and adjacency constraints. For the model mentioned above, we term it as a constrained DFCAP (cDFCAP). A mixed-integer linear programming model is formulated for the cDFCAP. In order to solve larger realistic problems, a constrained metaheuristic with the memetic algorithm framework customised for solving the cDFCAP is introduced in this work. In our algorithm, four problem-specific heuristic rules to construct a set of initial solutions are developed. In addition, an ideal parameter combination for our constrained memetic algorithm is determined through a Taguchi experimental design. Finally, the results of a set of cDFCAP instances with different sizes (n = 10∼80) report that our provided approach is effective for the considered problem.     

Facility layout design using virtual multi-agent system

This paper presents a novel approach to the facility layout design problem based on multi-agent society where agents’ interactions form the facility layout design. Each agent corresponds to a facility with inherent characteristics, emotions, and a certain amount of money, forming its utility function. An agent’s money is adjusted during the learning period by a manager agent while each agent tries to tune the parameters of its utility function in such a way that its total layout cost can be minimized in competition with others. The agents’ interactions are formed based on market mechanism. In each step, an unoccupied location is presented to all applicant agents, for which each agent proposes a price proportionate to its utility function. The agent proposing a higher price is selected as the winner and assigned to that location by an appropriate space-filling curve. The proposed method utilizes the fuzzy theory to establish each agent’s utility function. In addition, it provides a simulation environment using an evolutionary algorithm to form different interactions among the agents and makes it possible for them to experience various strategies. The experimental results show that the proposed approach achieves a lower total layout cost compared with state of the art methods.