Simulated annealing heuristics for the dynamic facility layout problem

In today's economy, manufacturing plants must be able to operate efficiently and respond quickly to changes in product mix and demand. Therefore, this paper considers the problem of arranging and rearranging (when there are changes between the flows of materials between departments) manufacturing facilities such that the sum of the material handling and rearrangement costs is minimized. This problem is known as the dynamic facility layout problem (DFLP). In this paper, two simulated annealing (SA) heuristics are developed for the DFLP. The first SA heuristic (SA I) is a direct adaptation of SA to the DFLP. The second SA heuristic (SA II) is the same as SA I with a look-ahead/look-back strategy added. To test the performance of the heuristics, a data set taken from the literature is used in the analysis. The results obtained show that the proposed heuristics are very effective for the dynamic facility layout problem.     

Dynamic facility layout problem in footwear industry

Dynamic facility layout problem (DFLP) deals with the arrangement of machines in a site as to minimize the sum of materials handling and re-layout costs by considering multi periods. The DFLP studies in the literature provide several different algorithms and utilize the well known test problems to assess their performance. However, real life applications are overlooked. The industries such as footwear and clothing are prone to seasonal demand changes. Therefore, time horizons and layout/re-layout of the machines within the facility should be studied carefully. This study considers a footwear facility and several scenarios are generated by using the real life data. A clonal selection based algorithm is proposed to solve the real life DFLP. The performance of the algorithm, further the effect of time periods on solution quality and applicability of the results are tested and promising results are obtained.     

A simulated annealing heuristic for the dynamic layout problem with budget constraint

Facility layout problem has been extensively studied in the literature because the total material handling cost can be a significant portion in the operational costs for a company and in the manufacturing cost of a product. Today’s severe global competition, rapid changes in technology and shortening life cycle of products force companies to evaluate and modify their facility layout in a periodic fashion. This type of layout problems is categorized as the dynamic facility layout problem (DFLP). As a realistic dimension of the problem, one has to consider also the limited budget to cover the cost of changing the layout. In this study, we propose a simulated annealing heuristic for the DFLP with budget constraint, and show the effectiveness of this heuristic on a set of numerical experiments.     

A clonal selection algorithm for dynamic facility layout problems

The dynamic facility layout problem (DFLP) aims to minimize the sum of handling and re-layout costs by devising an individual layout for each distinctive production period. It is a complex combinatorial optimization problem. This paper proposes a clonal selection algorithm (CSA) for DFLP. The algorithm is capable of being extended to more general cases although equal area machines and standardized handling equipments with identical unit costs are assumed for the time being. The performance of the proposed algorithm is examined by using three test problems from the literature. CSA reached the best known solutions–even found better solutions for large sized problems–in 88% of the instances, while each of the former methods was successful only in a small fraction of those 50 problems. CSA also outperformed all the present methods as regards solution times.     

A simulated annealing algorithm for dynamic layout problem

Increased level of volatility in today's manufacturing world demanded new approaches for modelling and solving many of its well-known problems like the facility layout problem. Over a decade ago Rosenblatt published a key paper on modelling and solving dynamic version of the facility layout problems. Since then, various other researchers proposed new and improved models and algorithms to solve the problem. Balakrishnan and Cheng have recently published a comprehensive review of the literature about this subject. The problem was defined as a complex combinatorial optimisation problem. The efficiency of SA in solving combinatorial optimisation problems is very well known. However, it has recently not been applied to DLP based on the review of the available literature. In this research paper a SA-based procedure for DLP is developed and results for test problems are reported.

Scope and purpose

One of the characteristic of today's manufacturing environments is volatility. Under a volatile environment (or dynamic manufacturing environment) demand is not stable. To operate efficiently under such environments facilities must be adaptive to changing demand conditions. This requires solution of the dynamic layout problem (DLP). DLP is a complex combinatorial optimisation problem for which optimal solutions can be found for small size problems. This research paper makes use of a SA algorithm to solve the DLP. Simulated annealing (SA) is a well-established stochastic neighbourhood search technique. It has a potential to solve complex combinatorial optimisation problems. The paper presents in detail how to apply SA to solve DLP and an extensive computational study. The computational study shows that SA is quite effective in solving dynamic layout problems.     

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 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.     

A hybrid approach for dynamic routing planning in an automated assembly shop

Highly turbulent environment of dynamic job-shop operations affects shop floor layout as well as manufacturing operations. Due to the dynamic nature of layout changes, essential requirements such as adaptability and responsiveness to the changes need to be considered in addition to the cost issues of material handling and machine relocation when reconfiguring a shop floor’s layout. Here, based on the source of uncertainty, the shop floor layout problem is split into two sub-problems and dealt with by two modules: re-layout and find-route. GA is used where changes cause the entire shop re-layout, while function blocks are utilised to find the best sequence of robots for the new conditions within the existing layout. This paper reports the latest development to the authors’ previous work.     

An improved algorithm for layout design in cellular manufacturing systems

Layout has a significant role on the efficiency of manufacturing systems, but it has not received attention of researchers in comparison to cell formation in cellular manufacturing systems. In this paper, a mathematical model for facility layout in a cellular manufacturing system is proposed that minimizes both inter-cell and intra-cell material handling costs. A variant of simulated annealing algorithm is developed to solve the model. The developed algorithm produces solutions with better quality and less computation time in comparison with the benchmarked algorithm. The superiority of the algorithm in computation time is considerable especially when the size of the problem increases.     

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

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

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.     

Solving a multi-floor layout design model of a dynamic cellular manufacturing system by an efficient genetic algorithm

This paper presents a mixed-integer programming model for a multi-floor layout design of cellular manufacturing systems (CMSs) in a dynamic environment. A novel aspect of this model is to concurrently determine the cell formation (CF) and group layout (GL) as the interrelated decisions involved in the design of a CMS in order to achieve an optimal (or near-optimal) design solution for a multi-floor factory in a multi-period planning horizon. Other design aspects are to design a multi-floor layout to form cells in different floors, a multi-rows layout of equal area facilities in each cell, flexible reconfigurations of cells during successive periods, distance-based material handling cost, and machine depot keeping idle machines. This model incorporates with an extensive coverage of important manufacturing features used in the design of CMSs. The objective is to minimize the total costs of intra-cell, inter-cell, and inter-floor material handling, purchasing machines, machine processing, machine overhead, and machine relocation. Two numerical examples are solved by the CPLEX software to verify the performance of the presented model and illustrate the model features. Since this model belongs to NP-hard class, an efficient genetic algorithm (GA) with a matrix-based chromosome structure is proposed to derive near-optimal solutions. To verify its computational efficiency in comparison to the CPLEX software, several test problems with different sizes and settings are implemented. The efficiency of the proposed GA in terms of the objective function value and computational time is proved by the obtained results.     

Evolutionary algorithms for constrained engineering problems

Evolutionary computation techniques have been receiving increasing attention regarding their potential as optimization techniques for complex problems. Recently these techniques were applied in the area of industrial engineering; the most-known applications include scheduling and sequencing in manufacturing systems, computer-aided design, facility layout and location problems, distribution and transportation problems, and many others. Industrial engineering problems usually are quite hard to solve due to a high complexity of the objective functions and a significant number of problem-specific constraints; often an algorithm to solve such problems requires incorporation of some heuristic methods. In this paper we concentrate on constraint handling heuristics for evolutionary computation techniques. This general discussion is followed by three test case studies: truss structure optimization problem, design of a composite laminated plate, and the unit commitment problem. These are typical highly constrained engineering problems and the methods discussed here are directly transferrable to industrial engineering problems.     

Supply facility and input/output point locations in the presence of barriers

This paper studies a facility location model in which two-dimensional Euclidean space represents the layout of a shop floor. The demand is generated by fixed rectangular-shaped user sites and served by a single supply facility. It is assumed that (i) communication between the supply point and a demand facility occurs at an input/output (I/O) point on the demand facility itself, (ii) the facilities themselves pose barriers to travel and (iii) distance measurement is as per the L₁-metric. The objective is to determine optimal locations of the supply facility as well as I/O points on the demand facilities, in order to minimize total transportation costs. Several, increasingly more complex, versions of the model are formulated and polynomial time algorithms are developed to find the optimal locations in each case.Scope and purposeIn a facility layout setting, often a new central supply facility such as a parts supply center or tool crib needs to be located to serve the existing demand facilities (e.g., workstations or maintenance areas). The demand facilities are physical entities that occupy space, that cannot be traveled through, and that receive material from the central facility, through a perimeter I/O (input/output or drop-off/pick-up) point. This paper addresses the joint problem of locating the central facility and determining the I/O point on each demand facility to minimize the total material transportation cost. Different versions of this problem are considered. The solution methods draw from and extend results of location theory for a class of restricted location problems. For practitioners, simple results and polynomial time algorithms are developed for solving these facility (re) design problems.     

Heuristic transporter routing model for manufacturing facility design

In this study, a transporter routing problem is analyzed and adapted for use in manufacturing facility design. Given fixed facility layout and predetermined material flow paths, this study determines the minimum number of transporters required to transfer material within a given manufacturing facility with minimal handling effort. The manufacturing facility design problem is particularly complex and involves the sub-problems such as design of the material network and the transporter routing problem, which provides the fleet size and the routing of each transporter over the flow network. The problem is formulated as an integer program. To solve the problem, we used a heuristic and integrated vehicle routing model. We also developed a heuristic solution program and several tests along with an industrial example to indicate the effectiveness of this method.     

A multi-objective scatter search for a dynamic cell formation problem

Cellular manufacturing system—an important application of group technology (GT)—has been recognized as an effective way to enhance the productivity in a factory. Consequently, a multi-objective dynamic cell formation problem is presented in this paper, where the total cell load variation and sum of the miscellaneous costs (machine cost, inter-cell material handling cost, and machine relocation cost) are to be minimized simultaneously. Since this type of problem is NP-hard, a new multi-objective scatter search (MOSS) is designed for finding locally Pareto-optimal frontier. To demonstrate the efficiency of the proposed algorithm, MOSS is compared with two salient multi-objective genetic algorithms, i.e. SPEA-II and NSGA-II based on some comparison metrics and statistical approach. The computational results indicate the superiority of the proposed MOSS compared to these two genetic algorithms.     

Locating input and output points in facilities design - acomparison of constructive, evolutionary, and exact methods

This paper formulates and compares four new approaches to optimally locate the input and output station for each department within a facility design such that material handling costs are minimized. This problem is an NP-hard combinatorial problem with many real-life applications of considerable economic consequence. A genetic algorithm (GA) is shown to be an effective and efficient optimization method when compared to integer programming, simulated annealing, and three versions of a greedy constructive heuristic on a suite of test problems of varying size. Seeding versus random initialization of GA populations are compared     

Solving the design of distributed layout problem using forecast windows: A hybrid algorithm approach

In today’s competitive environment, manufacturing facilities have to be more responsive to the frequent changes in product mix and demand by realigning their organizational structure for minimizing material handling cost. However, manufacturing firms are reluctant to modify the layout as it leads to operation disruption and excess rearrangement cost. In this paper, we present an alternative approach for designing a multi-period layout (i.e., distributed layout) that maintains a tradeoff between re-layout cost and cost of excess material handling. Obtaining an optimal solution to distributed layout problem is generally a difficult task, owing to larger size of quadratic assignment problem. In order to overcome the aforementioned drawback, a meta-heuristic, named ‘CSO-DLP’ (Clonal Symbiotic Operated-Distributed Layout Planning) is developed for designing a distributed layout that jointly determines the arrangement of department and flow allocation among them. It inherits its trait from Symbiotic algorithm and Clonal algorithm. In addition to these; the concept of ‘forecast window’ is used, which evaluates the layout for varying number of periods at a given time. The proposed meta-heuristic is applied on a benchmark dataset and the effect of system parameters, such as rearrangement cost, department disintegration, and duplication are investigated and benchmarked in this paper.     

A fast two-stage hybrid meta-heuristic algorithm for robust corridor allocation problem

The optimisation of the corridor allocation problem (CAP) belongs to the optimisation of the efficiency of the automated production line. The goal is to reduce the material handling cost (MHC) in the production process through a reasonable layout of the facilities, so as to save expenses for the enterprise. In recent years, with the acceleration of market changes, product design and production process adjustments have become more frequent, and more attention has been paid to the research on the layout of facilities under the condition of changes in the flow of materials between production facilities over time. On the basis of the CAP model, this paper considers the optimisation problem of row layout when the flow of materials between facilities fluctuates in a certain range. The new model can be utilised to obtain the overall optimisation solution under the condition of the floating material flow matrix, so as to achieve the goal of optimising the total MHC in the entire production process. As the new model introduces more variables and intermediate parameters, a two-stage solution method is previously required, which greatly increases the time to solve the problem. This paper proposes a targeted meta-heuristic algorithm optimisation method combining the advantages of tabu search algorithm and harmony search algorithm, which simplifies the solution phase of calling the precise solver in the two-stage algorithm of row facility layout problem, improves the problem solving efficiency, and makes the solution of large-scale problems become possible. The proposed model is verified through Lingo software, and then the model and the hybrid algorithm in the MATLAB environment are verified with each other. Finally, the proposed simplified algorithm is utilised to solve the large-scale problems that could not be solved by the two-stage algorithm before.     

The center location-dependent relocation problem with a probabilistic line barrier

This paper presents a new mixed-integer nonlinear programming (MINLP) for a multi-period rectilinear distance center location-dependent relocation problem in the presence of a probabilistic line-shaped barrier that uniformly occurs on a given horizontal route. In this problem, the demand and location of the existing facilities have a dynamic nature and the relocation is dependent to the location of new facilities in previous period. The objective function of the presented model is to minimize the maximum expected weighted barrier distance between the new facility and the existing facilities during the planning horizon. The optimum solution of small-sized test problems is obtained by the optimization software. For large-size test problems which the optimization software is unable to find the optimum solution in the runtime limitation, two meta-heuristics based on the genetic algorithm (GA) and imperialist competitive algorithm (ICA) are applied. To validate the meta-heuristics, a lower bound problem based on the forbidden region instead of the line barrier is generated. Related results of numerical experiments are illustrated and are then compared.