Heuristic approaches for part assignment in cell formation

Since the cell formation problem is considered to be a complex and multi-criteria problem, then no single algorithm can provide all the promised benefits. To gain more benefits of the cell formation, three heuristic procedures are developed in this paper to give the designer more flexibility to generate cells. Given a cell formation solution, the heuristics are designed to assign parts to the cells in the presence of alternative process plans, multiple alternative (parallel) machines, or when processing times are taken into consideration.     

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.     

Cell formation using multiple process plans

Cell formation (CF) consists of identifying machine groups and part families. Many CF procedures use a part machine matrix as an input and attempt to obtain a block diagonal form. But perfect block diagonalization of parts and machines is not possible is many cases. In this paper we consider a generalized cellular manufacturing (CM) problem, in which each part can have alternate process plans and each operation can be performed on alternate machines. Under these conditions the CF problem of assigning parts and machines to each manufacturing cell can be considered as a two stage process. The first stage deals with the problem of determining a unique process plan for each part. The second stage determines the part families and machine cells. In this research a model for forming part families and machine cells is presented considering alternate process plans. The objective is to analyze how alternate process plans influence and enhance the CM process giving better flexibility to the designer while designing cells for CM.     

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.     

An e-Learning tool considering similarity measures for manufacturing cell formation

Manufacturing cell formation is the first step in the design of cellular manufacturing system. The primary objective of this step is to cluster machines into machine cells and parts into part families so that the minimum of intercell trips will be achieved. This paper will be focused on the configuration of machine cells considering three types of initial machine-part matrix: binary (zero-one) matrix, production volume matrix, and operation time matrix. The similarity measure uses only information from these types of matrix. A pure combinatorial programming formulation will be developed to maximize the sum of similarity coefficients between machine/part pairs. An e-Learning tool/application to help industrial students and engineers for enhancing their cell formation capability is proposed. This tool is designed to include a novel similarity coefficient-based heuristic algorithm for solving the cell formation problem. To determine the performance of the proposed tool, comparison is made with a well-known tool along a case study.     

Formation of general GT cells: an operation-based approach

In this paper, we study the formation of general Group Technology cells based on the operation requirements of parts and operation capabilities of machines. Parts are first grouped into families by using a similarity coefficient based on common operation types. An integer model is then developed to solve the problem of machine group selection. The model takes into account machine cost, variable production cost, setup cost, and intracell material handling cost. A greedy heuristic, a minimum increment heuristic and a simulated annealing heuristic are proposed for solving the model more efficiently. The computational results have shown that the heuristic methods perform well when compared to the optimal solutions. The effect of changing cost structure on the performance of heuristic procedures is also investigated.     

A hybrid GA-AUGMECON method to solve a cubic cell formation problem considering different worker skills

Part quality and consequently customer satisfaction besides cost functions are two of the most important issues for any firm. Balancing between these two goals leads to full utilization from manufacturing resources. Formerly, in cubic cell formation problem, where a part on a machine can be processed by various workers, worker assignment was done just by minimizing inter-cell movement criterion; so, the workers assigned into the processing cell are mostly selected rather than outsider workers. But, it is rational for the ties to be broken by skills of different workers in performing a special part on the dedicated machine. In this paper, a bi-objective cubic cell formation is presented with two non-homogeneous objective functions in order to minimize the inter-cell movements and maximize a part quality index. Quality index for each part is represented through a cubic matrix containing integer values of 1–5 (representing very bad, bad, medium, well and very well), which qualifies the process of part on a specific machine by a specific worker. To solve the problem, a hybrid GA-augmented ε-constraint method (GA-AUGMEON) is developed to reduce time consuming difficulty of AUGMECON method. To validate the model and the GA-AUGMECON algorithm, some randomly generated examples in small and large size are solved.     

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.     

A hybrid grouping genetic algorithm for the cell formation problem

The machine-part cell formation problem consists of constructing a set of machine cells and their corresponding product families with the objective of minimizing the inter-cell movement of the products while maximizing machine utilization. This paper presents a hybrid grouping genetic algorithm for the cell formation problem that combines a local search with a standard grouping genetic algorithm to form machine-part cells. Computational results using the grouping efficacy measure for a set of cell formation problems from the literature are presented. The hybrid grouping genetic algorithm is shown to outperform the standard grouping genetic algorithm by exceeding the solution quality on all test problems and by reducing the variability among the solutions found. The algorithm developed performs well on all test problems, exceeding or matching the solution quality of the results presented in previous literature for most problems.     

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 two-stage model for cost effective part family and machine cell formation

This research presents, implements and tests a two-stage procedure for cost effective part family and machine cell formation. First, the problem is formulated as a mixed integer mathematical model for simultaneous machine grouping and part family assignment. This model, which we refer to as the single-stage model, considers the cost trade-offs of cell configuration, machine procurement and salvage, subcontracting, inter-cell movement, and capital investment, all of which reflect the significance of real life planning aspects. To alleviate the computational burden of this single-stage model, we decompose it into two stages: the first stage is a heuristic for machine cell and part family formations; the second stage integrates the heuristic method with a mathematical program to optimize the various cost aspects. The efficacy of the proposed models is shown through a number of example problems. The results show that the two-stage procedure is powerful in the planing stages of large-size problems where the cost aspects are crucial.     

A hybrid method based on genetic algorithm and dynamic programming for solving a bi-objective cell formation problem considering alternative process routings and machine duplication

Cell formation is one of the first and most important steps in designing a cellular manufacturing system. It consist of grouping parts with similar design features or processing requirements into part families and associated machines into machine cells. In this study, a bi-objective cell formation problem considering alternative process routings and machine duplication is presented. Manufacturing factors such as part demands, processing times and machine capacities are incorporated in the problem. The objectives of the problem include the minimization of the total dissimilarity between the parts and the minimization of the total investment needed for the acquisition of machines. A normalized weighted sum method is applied to unify the objective functions. Due to the computational complexity of the problem, a hybrid method combining genetic algorithm and dynamic programming is developed to solve it. In the proposed method, the dynamic programming is implemented to evaluate the fitness value of chromosomes in the genetic algorithm. Computational experiments are conducted to examine the performance of the hybrid method. The computations showed promising results in terms of both solution quality and computation time.     

A multiple-objective grouping genetic algorithm for the cell formation problem with alternative routings

This paper addresses the cell formation problem with alternative part routings, considering machine capacity constraints. Given processes, machine capacities and quantities of parts to produce, the problem consists in defining the preferential routing for each part optimising the grouping of machines into manufacturing cells. The main objective is to minimise the inter-cellular traffic, while respecting machine capacity constraints. To solve this problem, the authors propose an integrated approach based on a multiple-objective grouping genetic algorithm for the preferential routing selection of each part (by solving an associated resource planning problem) and an integrated heuristic for the cell formation problem.     

The cell formation problem in cellular manufacturing systems—A sequential modelling approach

A sequential modelling approach to the cell formation problem in cellular manufacturing systems is presented in this paper. First, the machines are grouped into cells based on their similarity in parts processing; next the parts are allocated to appropriate machine groups based on the processing requirements. The machine grouping and the parts allocation problems are modelled as 0–1 integer programs. The application of the models is illustrated using a numerical example.     

A decision support system for production scheduling in an ion plating cell

Production scheduling is one of the major issues in production planning and control of individual production units which lies on the heart of the performance of manufacturing organizations. Traditionally, production planning decision, especially scheduling, was resolved through intuition, experience, and judgment. Machine loading is one of the process planning and scheduling problems that involves a set of part types and a set of tools needed for processing the parts on a set of machines. It provides solution on assigning parts and allocating tools to optimize some predefined measures of productivity. In this study, Ion Plating industry requires similar approaches on allocating customer's order, i.e. grouping production jobs into batches and arrangement of machine loading sequencing for (i) producing products with better quality products; and (ii) enabling to meet due date to satisfy customers. The aim of this research is to develop a Machine Loading Sequencing Genetic Algorithm (MLSGA) model to improve the production efficiency by integrating a bin packing genetic algorithm model in an Ion Plating Cell (IPC), such that the entire system performance can be improved significantly. The proposed production scheduling system will take into account the quality of product and service, inventory holding cost, and machine utilization in Ion Plating. Genetic Algorithm is being chosen since it is one of the best heuristics algorithms on solving optimization problems. In the case studies, industrial data of a precious metal finishing company has been used to simulate the proposed models, and the computational results have been compared with the industrial data. The results of developed models demonstrated that less resource could be required by applying the proposed models in solving production scheduling problem in the IPC.     

Bicriteria robotic operation allocation in a flexible manufacturing cell

Consider a manufacturing cell of two identical CNC machines and a material handling robot. Identical parts requesting the completion of a number of operations are to be produced in a cyclic scheduling environment through a flow shop type setting. The existing studies in the literature overlook the flexibility of the CNC machines by assuming that both the allocation of the operations to the machines as well as their respective processing times are fixed. Consequently, the provided results may be either suboptimal or valid under unnecessarily limiting assumptions for a flexible manufacturing cell. The allocations of the operations to the two machines and the processing time of an operation on a machine can be changed by altering the machining conditions of that machine such as the speed and the feed rate in a CNC turning machine. Such flexibilities constitute the point of origin of the current study. The allocation of the operations to the machines and the machining conditions of the machines affect the processing times which, in turn, affect the cycle time. On the other hand, the machining conditions also affect the manufacturing cost. This study is the first to consider a bicriteria model which determines the allocation of the operations to the machines, the processing times of the operations on the machines, and the robot move sequence that jointly minimize the cycle time and the total manufacturing cost. We provide algorithms for the two 1-unit cycles and test their efficiency in terms of the solution quality and the computation time by a wide range of experiments on varying design parameters.     

Manufacturing cell formation with production data using neural networks

Batch type production strategies need adoption of cellular manufacturing (CM) in order to improve operational effectiveness by reducing manufacturing lead time and costs related to inventory and material handling. CM necessitates that parts are to be grouped into part families based on their similarities in manufacturing and design attributes. Then, machines are allocated into machine cells to produce the identified part families so that productivity and flexibility of the system can be improved. Zero-one part-machine incidence matrix (PMIM) generated from route sheet information is commonly presented as input for clustering of parts and machines. An entry of ‘1’ in PMIM indicates that the part is visiting the machine and zero otherwise. The output is generated in the form of block diagonal structure where each block represents a machine cell having more than one machines and a part family. The major limitations of this approach lies in the fact that important production factors like operation time, sequence of operations, and lot size of the parts are not accounted for. In this paper, an attempt has been made to propose a clustering methodology based on adaptive resonance theory (ART) for addressing these issues. Initially, a methodology considering only the operation sequence of the parts has been proposed. Then, the methodology is suitably modified to deal with combination of operation sequence and operation time of the parts to address generalized cell formation (CF) problem. A new performance measure is proposed to quantify the performance of the proposed methodology. The performance of the proposed algorithm is tested with benchmark problems from open literature and the results are compared with the existing methods. The results clearly indicate that the proposed methodology outperforms the existing methods in most cases.     

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.     

Bicriteria robotic cell scheduling

This paper considers the scheduling problems arising in two- and three-machine manufacturing cells configured in a flowshop which repeatedly produces one type of product and where transportation of the parts between the machines is performed by a robot. The cycle time of the cell is affected by the robot move sequence as well as the processing times of the parts on the machines. For highly flexible CNC machines, the processing times can be changed by altering the machining conditions at the expense of increasing the manufacturing cost. As a result, we try to find the robot move sequence as well as the processing times of the parts on each machine that not only minimize the cycle time but, for the first time in robotic cell scheduling literature, also minimize the manufacturing cost. For each 1-unit cycle in two- and three-machine cells, we determine the efficient set of processing time vectors such that no other processing time vector gives both a smaller cycle time and a smaller cost value. We also compare these cycles with each other to determine the sufficient conditions under which each of the cycles dominates the rest. Finally, we show how different assumptions on cost structures affect the results.     

Cell formation in flexible manufacturing systems under resource constraints

In this paper, the cell formation problem in Flexible Manufacturing Systems under resource constraints is discussed. A 0–1 integer programming model is developed to form the machine-part groups and to decide on the number of machines and the number of copies of tools required to achieve minimum overall system cost. The model takes into account the processing time available on any machine, tool lives and the processing requirements of the parts. The model is illustrated using a numerical example.