Two-stage approach for machine-part grouping and cell layout problems

Cellular manufacturing system (CMS) which is based on the concept of group technology (GT) has been recognized as an efficient and effective way to improve the productivity in a factory. In recent years, there have been continuous research efforts to study different facet of CMS. Most of them concentrated on distinguishing the part families and machine cells either simultaneously or individually with the objective of minimizing intercellular and intracellular part movements. This is known as machine-part grouping problem (MPGP) which is a crucial process while designing CMS. Nevertheless, in reality some components may not be finished within only one cell, they have to travel to another cell(s) for further operation(s). Under this circumstance, intercellular part movement will occur. Different order/sequence of machine cells allocation may result in different total intercellular movement distance unit. It should be noted that if the production volume of each part is very large, then the total number of intercellular movement will be further larger. Therefore, the sequence of machine cells is particularly important in this aspect. With this consideration, the main aim of this work is to propose two-stage approach for solving cell formation problem as well as cell layout problem. The first stage is to identify machine cells and part families, which is the essential part of MPGP. The work in second stage is to carry out a macro-approach to study the cell formation problem with consideration of machining sequence. The impact of the sequencing for allocating the machine cells on minimizing intercellular movement distance unit will be investigated in this stage. The problem scope, which is a MPGP together with the background of cell layout problem (CLP), has been identified. Two mathematical models are formulated for MPGP and CLP respectively. The primary assumption of CLP is that it is a linear layout. The CLP is considered as a quadratic assignment problem (QAP). As MPGP and QAP are NP-hard, genetic algorithm (GA) is employed as solving algorithm. GA is a popular heuristic search technique and has proved superior performance on complex optimization problem. In addition, an industrial case study of a steel member production company has been employed to evaluate the proposed MPGP and CLP models, and the computational results are presented.     

A novel approach to determine cell formation,intracellular machine layout and cell layout in the CMS problem based on TOPSIS method

This paper deals with the cellular manufacturing system (CMS) that is based on group technology (GT) concepts. CMS is defined as identifying the similar parts that are processed on the same machines and then grouping them as a cell. The most proposed models for solving CMS problems are focused on cell formation and intracellular machine layout problem while cell layout is considered in few papers. In this paper we apply the multiple attribute decision making (MADM) concept and propose a two-stage method that leads to determine cell formation, intracellular machine layout and cell layout as three basic steps in the design of CMS. In this method, an initial solution is obtained from technique for order preference by similarity to the ideal solution (TOPSIS) and then this solution is improved. The results of the proposed method are compared with well-known approaches that are introduced in literature. These comparisons show that the proposed method offers good solutions for the CMS problem. The computational results are also reported.     

An efficient approach to determine cell formation,cell layout and intracellular machine sequence in cellular manufacturing systems

Cellular manufacturing systems (CMS) are used to improve production flexibility and efficiency. They involve the identification of part families and machine cells so that intercellular movement is minimized and the utilization of the machines within a cell is maximized. Previous research has focused mainly on cell formation problems and their variants; however, only few articles have focused on more practical and complicated problems that simultaneously consider the three critical issues in the CMS-design process, i.e., cell formation, cell layout, and intracellular machine sequence. In this study, a two-stage mathematical programming model is formulated to integrate the three critical issues with the consideration of alternative process routings, operation sequences, and production volume. Next, because of the combinatorial nature of the above model, an efficient tabu search algorithm based on a generalized similarity coefficient is proposed. Computational results from test problems show that our proposed model and solution approach are both effective and efficient. When compared to the mathematical programming approach, which takes more than 112 h (LINGO) and 1139 s (CPLEX) to solve a set of ten test instances, the proposed algorithm can produce optimal solutions for the same set of test instances in less than 12 s.     

CLASS: An algorithm for cellular manufacturing system and layout design using sequence data

Cell formation problem in CMS design has received the attention of researchers for more than three decades. However, use of sequence data for cell formation has been a least researched area. Sequence data provides valuable information about the flow patterns of various jobs in a manufacturing system. Therefore, it is only natural to expect that use of sequence data must result in not only identifying the part families and machine groups but also the layout (sequence) of the machines within each cell. Unfortunately, such an approach has not been taken in the past while solving CMS design problem using sequence data. In this paper, we fill this gap in the literature by developing an algorithm that not only identifies the cells but also the sequence of machines in the cells in a simultaneous fashion. The numerical computations of the algorithm with the available problems in the literature indicate the usefulness of the algorithm. Further, it also points to the untapped potential of such an approach to solve CMS design and layout problem using sequence data.     

An Electromagnetism-like algorithm for cell formation and layout problem

Implementation of cellular manufacturing systems (CMS) is thriving among manufacturing companies due to many advantages that are attained by applying this system. In this study CMS formation and layout problems are considered. An Electromagnetism like (EM-like) algorithm is developed to solve the mentioned problems. In addition the required modifications to make EM-like algorithm applicable in these problems are mentioned. A heuristic approach is developed as a local search method to improve the quality of solution of EM-like. Beside in order to examine its performance, it is compared with two other methods. The performance of EM-like algorithm with proposed heuristic and GA are compared and it is demonstrated that implementing EM-like algorithm in this problem can improve the results significantly in comparison with GA. In addition some statistical tests are conducted to find the best performance of EM-like algorithm and GA due to their parameters. The convergence diagrams are plotted for two problems to compare the convergence process of the algorithms. For small size problems the performances of the algorithms are compared with an exact algorithm (Branch & Bound).     

Development of bacteria foraging optimization algorithm for cell formation in cellular manufacturing system considering cell load variations

The cellular manufacturing system (CMS) is considered as an efficient production strategy for batch type production. The CMS relies on the principle of grouping machines into machine cells and grouping machine parts into part families on the basis of pertinent similarity measures. The bacteria foraging optimization (BFO) algorithm is a modern evolutionary computation technique derived from the social foraging behavior of Escherichia coli bacteria. Ever since Kevin M. Passino invented the BFO, one of the main challenges has been the employment of the algorithm to problem areas other than those of which the algorithm was proposed. This paper investigates the first applications of this emerging novel optimization algorithm to the cell formation (CF) problem. In addition, for this purpose matrix-based bacteria foraging optimization algorithm traced constraints handling (MBATCH) is developed. In this paper, an attempt is made to solve the cell formation problem while considering cell load variations and a number of exceptional elements. The BFO algorithm is used to create machine cells and part families. The performance of the proposed algorithm is compared with a number of algorithms that are most commonly used and reported in the corresponding scientific literature such as K-means clustering, the C-link clustering and genetic algorithm using a well-known performance measure that combined cell load variations and a number of exceptional elements. The results lie in favor of better performance of the proposed algorithm.     

A bacteria foraging algorithm based cell formation considering operation time

The cellular manufacturing system (CMS) is considered as an efficient production strategy for batch type production. The CMS relies on the principle of grouping machines into machine cells and grouping machine parts into part families based on pertinent similarity measures. The bacteria foraging algorithm (BFA) is a new in development computation technique extracted from the social foraging behavior of Escherichia coli (E. coli) bacteria. Ever since Kevin M. Passino invented the BFA, one of the main challenges has been employment of the algorithm to problem areas other than those for which the algorithm was proposed. This research work inquires the first applications of this emerging novel optimization algorithm to the cell formation (CF) problem. In addition, a newly developed BFA-based optimization algorithm for CF is discussed. In this paper, an attempt is made to solve the cell formation problem meanwhile taking into consideration number of voids in cells and a number of exceptional elements based on operational time of the parts required for processing in the machines. The BFA is suggested to create machine cells and part families. The performance of the proposed algorithm is compared with a number of algorithms that are most commonly used and reported in the corresponding scientific literature such as similarity coefficients methods (SCM), rank order clustering (ROC), ZODIAC, GRAFICS, MST, GATSP, GP, K-harmonic clustering (KHM), K-means clustering, C-link clustering, modified ART1, GA (genetic algorithm), evolutionary algorithm (EA), and simulated annealing (SA) using defined performance measures known as modified grouping efficiency and grouping efficacy. The results lie in favor of better performance of the proposed algorithm.     

Applying simulated annealing for designing cellular manufacturing systems using MDmTSP

The design of cellular manufacturing systems involves many structural and operational issues. One of the important design steps is the formation of part families and machine cells (cell formation). Despite a large number of papers on cell formation published worldwide, only a handful incorporates operation sequence in layout design (intra-cell move calculations). We propose a solution to solve the part-family and machine-cell formation problem considering the within-cell layout problem, simultaneously. In this paper, the cellular manufacturing system is formulated as a multiple departures single destination multiple travelling salesman problem (MDmTSP) and a solution methodology based on simulated annealing is proposed to solve the formulated model. Numerical examples show that the proposed method is efficient and effective in finding optimal solutions. The results also indicate that the proposed approach performs well compared to some well-known cell formation methods.     

一种结合多目标免疫算法和线性规划的双行设备布局方法

设备布局对于提高生产效率和降低运营成本具有重要意义. 本文针对半导体加工制造中常见的双行设备布局问题, 提出了一种结合多目标免疫算法和线性规划的双行设备布局方法来同时优化物料流成本和布局面积两个目标. 首先, 建立了问题的混合整数规划模型;其次, 针对问题既含有组合方面(机器排序)又含有连续方面(机器精确位置)的特点, 分别设计了一种多目标免疫算法来获取非支配的机器排序集合, 提出了一种基于线性规划的方法来构造任一非支配机器排序对应的连续的非支配解集;最后, 由所有连续的非支配解来构造最后Pareto解. 实验结果表明, 该方法对于小规模问题能获得最优Pareto解, 对于大规模问题能够获得具有良好分布性的Pareto解且其质量远好于NSGA-II和精确算法获得的解.     

Solving a group layout design model of a dynamic cellular manufacturing system with alternative process routings,lot splitting and flexible reconfiguration by simulated annealing

This paper presents a novel mixed-integer non-linear programming model for the layout design of a dynamic cellular manufacturing system (DCMS). In a dynamic environment, the product mix and part demands are varying during a multi-period planning horizon. As a result, the best cell configuration for one period may not be efficient for successive periods, and thus it necessitates reconfigurations. 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 in a dynamic environment. The proposed model integrating the CF and GL decisions can be used by researchers and practitioners to design GL in practical and dynamic cell formation problems. Another compromising aspect of this model is the utilization of multi-rows layout to locate machines in the cells configured with flexible shapes. Such a DCMS model with an extensive coverage of important manufacturing features has not been proposed before and incorporates several design features including alternate process routings, operation sequence, processing time, production volume of parts, purchasing machine, duplicate machines, machine capacity, lot splitting, intra-cell layout, inter-cell layout, multi-rows layout of equal area facilities and flexible reconfiguration. The objective of the integrated model is to minimize the total costs of intra and inter-cell material handling, machine relocation, purchasing new machines, machine overhead and machine processing. Linearization procedures are used to transform the presented non-linear programming model into a linearized formulation. Two numerical examples taken from the literature are solved by the Lingo software using a branch-and-bound method to illustrate the performance of this model. An efficient simulated annealing (SA) algorithm with elaborately designed solution representation and neighborhood generation is extended to solve the proposed 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 with the Lingo software. The obtained results show that the proposed SA is able to find the near-optimal solutions in computational time, approximately 100 times less than Lingo. Also, the computational results show that the proposed model to some extent overcomes common disadvantages in the existing dynamic cell formation models that have not yet considered layout problems.     

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.     

A hybrid genetic-variable neighborhood search algorithm for the cell formation problem based on grouping efficacy

Cell formation problem attempts to group machines and part families in dedicated manufacturing cells such that the number of voids and exceptional elements in cells are minimized. In this paper, we presented a linear fractional programming model with the objective of maximizing the grouping efficacy while the number of cells is unknown. To show the effectiveness of the proposed model, two test problems were applied. Then, to solve the model for real-sized applications, a hybrid meta-heuristic algorithm in which genetic algorithm and variable neighborhood search are combined. Using the grouping efficacy measure, we have also compared the performance of the proposed algorithm on a set of 35 test problems from the literature. The results show that the proposed GA-VNS method outperforms the state-of-the-art algorithms.     

New integration of preventive maintenance and production planning with cell formation and group scheduling for dynamic cellular manufacturing systems

This paper proposes a new integration method for cell formation, group scheduling, production, and preventive maintenance (PM) planning problems in a dynamic cellular manufacturing system (CMS). The cell formation sub-problem aims to form part families and machine groups, which minimizes the inter-cell material handling, under-utilization, and relocation costs. The production planning aspect is a multi-item capacitated lot-sizing problem accompanied by sub-contracting decisions, while the group scheduling problem deals with the decisions on the sequential order of the parts and their corresponding completion times. The purpose of the maintenance sub-problem is to determine the availability of the system and the time when the noncyclical perfect PM must be implemented to reduce the number of corrective actions. Numerical examples are generated and solved by Bender’s decomposition pack in GAMS to evaluate the interactions of the proposed model. Statistical analysis, based on a nonparametric method, is also used to study the behavior of the model’s cost components in two different situations. It is shown that by adding the PM planning decisions to the tactical decisions of the dynamic CMS, the optimal configuration and production plans of the system are heavily affected. The results indicate that omitting the PM actions increases the number of sudden failures, which leads to a higher total cost. Finally, it is concluded that the boost in the total availability of the dynamic CMS is one of the main advantages of the proposed integrated method.     

BASE: A bacteria foraging algorithm for cell formation with sequence data

A cellular manufacturing system (CMS) is considered an efficient production strategy for batch type production. A CMS relies on the principle of grouping machines into machine cells and grouping parts into part families on the basis of pertinent similarity measures. The bacteria foraging algorithm (BFA) is a newly developed computation technique extracted from the social foraging behavior of Escherichia coli (E. coli) bacteria. Ever since Kevin M. Passino invented the BFA, one of the main challenges has been employment of the algorithm to problem areas other than those for which the algorithm was proposed. This research work studies the first applications of this emerging novel optimization algorithm to the cell formation (CF) problem considering the operation sequence. In addition, a newly developed BFA-based optimization algorithm for CF based on operation sequences is discussed. In this paper, an attempt is made to solve the CF problem, while taking into consideration the number of voids in the cells and the number of inter-cell travels based on operational sequences of the parts visited by the machines. The BFA is suggested to create machine cells and part families. The performance of the proposed algorithm is compared with that of a number of algorithms that are most commonly used and reported in the corresponding scientific literature, such as the CASE clustering algorithm for sequence data, the ACCORD bicriterion clustering algorithm and modified ART1, and using a defined performance measure known as group technology efficiency and bond efficiency. The results show better performance of the proposed algorithm.     

A parametric model for cell formation and exceptional elements’ problems with fuzzy parameters

This paper introduces a new fuzzy mathematical model based on the fuzzy parametric programming (FPP) approach for the cellular manufacturing system (CMS) design. The aim of the proposed model is to handle two important problems of CMS design called cell formation (CF) and exceptional elements (EE) simultaneously in fuzzy environment. The model is capable to express vagueness of all the system parameters and gives the decision-maker (DM) alternative decision plans for different grades of precision. So, it is expected to provide a more realistic CMS design for real life problems. To illustrate the model proposed here, an example with fuzzy extension in data set is adopted from literature and computational results are presented.This paper was presented in the 2nd Group Technology/Cellular Manufacturing-World Symposium, Ohio University, Ohio, USA, July 28–30.     

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.     

CMS环境下基于智能优化算法的单元间布局问题研究*

研究了单元制造系统(CMS)设计中单元间布局设计问题,从单元制造系统的实际出发,提出了一种基于割树(Slicing-tree)的单元间布局设计模型.该模型考虑了单元形状约束、单元I/O点位置优化等诸因素对布局结果的影响.针对基于割树的描述形式,采用遗传算法求解,提出了一种新的割树编码方案,克服了以往编码方案易产生非法子串、不能覆盖整个解空间以及实现困难等缺点.计算结果表明,该算法是有效的、可行的.     

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.     

用CLP技术解决动画自动生成中的布局规划问题*

以本实验室研制的一个多重论域的约束逻辑程序设计系统BPUCLP为基础,提出用约束逻辑程序(Constraint Logic Programming,CLP)解决布局规划问题。该方法用几何模型表示对象,用算术约束描述对象间的位置关系,并通过BPUCLP的约束求解机制为各个位置变量取值。该方法实现了二维人物初始布局规划和三维卧室家具布局规划。实验证明该方法是有效的。     

Manufacturing cell formation in the presence of flexible cell locations and material transporters

The effect of cell locations and material transporters in the formation of manufacturing cells is investigated in this paper. Automated guided vehicles (AGVs) using a tandem configuration are considered and a first-come-first-served (FCFS) principle is applied for transporting the material between machines or between the input/output (I/O) and a machine. Using the time taken to perform material transfers as a suitable measure, a polynomial programming model is developed for the problem. As the model can be shown strongly NP-hard, a higher-level heuristic algorithm based upon a concept known as ‘tabu search’ is presented. An example problem is solved to further demonstrate that cell locations indeed have a significant impact when material transfers are used in the design of manufacturing cells.