A new approach to the cell formation problem with alternative processing routes and operation sequence

Cellular manufacturing (CM) is an important application of group technology in manufacturing systems. One of the crucial steps in the design of CM is the identification of part families and manufacturing cells. This problem is referred to as cell formation problem (CFP) in the literature. In this article, a solution approach is proposed for CFP, which considers many parameters such as machine requirement, sequence of operations, alternative processing routes, processing time, production volume, budget limitation, cost of machines, etc. Due to the NP-hardness of CFP, it cannot be efficiently solved for medium- to large-sized problems. Thus, a genetic algorithm (GA) is proposed to solve the formulated model. Comparison of the results obtained from the proposed GA to the globally optimum solutions obtained by Lingo Software and those reported in the literature reveals the effectiveness and efficiency of the proposed approach.     

A parallel genetic algorithm for dynamic cell formation in cellular manufacturing systems

Instead of using expensive multiprocessor supercomputers, parallel computing can be implemented on a cluster of inexpensive personal computers. Commercial accesses to high performance parallel computing are also available on the pay-per-use basis. However, literature on the use of parallel computing in production research is limited. In this paper, we present a dynamic cell formation problem in manufacturing systems solved by a parallel genetic algorithm approach. This method improves our previous work on the use of sequential genetic algorithm (GA). Six parallel GAs for the dynamic cell formation problem were developed and tested. The parallel GAs are all based on the island model using migration of individuals but are different in their connection topologies. The performance of the parallel GA approach was evaluated against a sequential GA as well as the off-shelf optimization software. The results are very encouraging. The considered dynamic manufacturing cell formation problem incorporates several design factors. They include dynamic cell configuration, alternative routings, sequence of operations, multiple units of identical machines, machine capacity, workload balancing, production cost and other practical constraints.     

A PSO-based approach to cell formation problems with alternative process routings

Group technology (GT) has been extensively applied to cellular manufacturing system (CMS) design for decades due to many benefits such as decreased number of part movements among cells and increased machine utilisation in cells. This paper considers cell formation problems with alternative process routings and proposes a discrete particle swarm optimisation (PSO) approach to minimise the number of exceptional parts outside machine cells. The approach contains two main steps: machine partition and part-routing assignment. Through inheritance and random search, the proposed algorithm can effectively partition machines into different cells with consideration of multiple part process routings. The computational results are compared with those obtained by using simulated annealing (SA)-based and tabu search (TS)-based algorithms. Experimental results demonstrate that the proposed algorithm can find equal or fewer exceptional elements than existing algorithms for most of the test problems selected from the literature. Moreover, the proposed algorithm is further tailed to incorporate various production factors in order to extend its applicability. Four sample cases are tested and the results suggest that the algorithm is capable of solving more practical cell formation problems.     

Cell formation: the need for an integrated solution of the subproblems

Cellular manufacturing is a viable option in many manufacturing systems. There are various subproblems in the design of a cellular manufacturing system. These are machine group and part family formation, machine duplication, intracell layout and intercell layout. The only comprehensive design strategy that attempts to address all of these is production flow analysis. However, this technique is a sequential strategy where the subproblems mentioned above are assumed nested within each other and are solved in a forward pass with no feedback. This is a satisfactory approach only in cases where the part families are relatively disjoint and machine groups are formed without constraints on machine duplication to eliminate intercell flow. The presence of bottleneck machines and parts renders the problem considerably more complex, as the subproblems influence each other substantially. This paper presents an integrated framework for solving these subproblems by generating a limited set of feasible alternative solutions.     

Efficient algorithm for cell formation with sequence data,machine replications and alternative process routings

Cell formation is an important problem in the design of a cellular manufacturing system. Despite a large number of papers on cell formation being published, only a handful incorporate operation sequence in intercell move calculations and consider alternative process routings, cell size, production volume and allocating units of identical machines into different cells. Modelling the above factors makes the cell formation problem complex but more realistic. The paper develops a model and solution methodology for a problem of cell formation to minimize the sum of costs of intercell moves, machine investment and machine operating costs considering all the factors mentioned above. An algorithm comprised of simulated annealing and local search heuristics has been developed to solve the model. A limited comparison of the proposed algorithm with an optimal solution generated by complete enumeration of small problems indicates that the algorithm produces a solution of excellent quality. Large problems with 100 parts and 50 machine types are efficiently solved using the algorithm.     

Designing cellular manufacturing systems with dynamic part populations

The effectiveness of a cellular manufacturing system is sensitive to fluctuations in the demand for products and the product mix. This paper presents a new formulation of the part family/machine cell formation problem that addresses the dynamic nature of the production environment by considering a multi-period forecast of product mix and demand during the formation of part families and machine cells. The goal of the multi-period formulation is to obtain a cellular design that continues to perform well with respect to the design objectives as the part population changes with time.     

Graph-neural network approach in cellular manufacturing on the basis of a binary system

In the past several years, many studies have been carried out on cellular manufacturing. Group technology is a manufacturing philosophy in which similar parts are identified and grouped together to take advantage of their similarities in manufacturing and design. The main problem in the development of cellular manufacturing is that of cell formation. In this paper, a graph-neural network approach is given for cell formation problems in group technology. Effort has been made to develop an algorithm that is more reliable than conventional methods. A graph-neural network has the advantages of fast computation and the ability to handle large scale industrial problems without the assumption of any parameter and the least exceptional elements in the presence of bottleneck machines and/or bottleneck parts. Two examples from the literature have been solved to demonstrate the advantages of the algorithm.     

Cellular manufacturing systems design with routing flexibility,machine procurement,production planning and dynamic system reconfiguration

This paper investigates the problem of designing cellular manufacturing systems with multi-period production planning, dynamic system reconfiguration, operation sequence, duplicate machines, machine capacity and machine procurement. An important aspect of this problem is the introduction of routing flexibility in the system by the formation of alternate contingency process routings in addition to alternate main process routings for all part types. Contingency routings serve as backups so as to effectively address the reality of part process routing disruptions (in the main routings) owing to machine breakdowns and allow the cellular manufacturing system to operate in a continuous manner even in the event of such breakdowns. The paper also provides in-depth discussions on the trade-off between the increased flexibility obtained versus the additional cost to be incurred through the formation of contingency routings for all parts. Some sensitivity analysis is also performed on some of the model parameters. The problem is modelled and solved through a comprehensive mixed integer programming formulation. Computational results presented by solving some numerical examples show that the routing and process flexibilities can be incorporated within the cellular manufacturing system design without significant increase in the system cost.     

Designing group layout of unequal-area facilities in a dynamic cellular manufacturing system with variability in number and shape of cells

This paper presents a new mixed-integer non-linear programming model for designing the group layout (GL) of unequal-area facilities in a cellular manufacturing system (CMS) under a dynamic environment. There are some features that make the presented model different from the previous studies. These include: (1) manufacturing cells with variable numbers and shapes, (2) machine depot keeping idle machines, (3) machines of unequal-areas, (4) manufacturing cells with rectangle regular shapes established on the continuous shop floor and (5) integration of cell formation and GL as interrelated decisions involved in the design of a CMS in a dynamic environment. The objective function is to minimises the total costs of intra- and inter-cell material handling, machine overhead, machine relocation, machine processing, purchasing machines and forming cells. Since the problem is NP-hard, an efficient simulated annealing (SA) algorithm is developed to solve the presented model. The performance of this model is illustrated by two numerical examples. It is then tested using several test problems with different sizes and settings to verify the computational efficiency of the developed algorithm in comparison to the classical genetic algorithm (GA). The obtained results show that the quality of the solutions obtained by SA is better than GA.     

Design of cellular manufacturing system with quasi-dynamic dual resource using multi-objective GA

A new concept is presented in this paper of quasi-dynamic cell formation for the design of a cellular manufacturing system, based on analysing the fact that static and dynamic cell formation could not reflect the real situation of a modern cellular manufacturing system. Further, workforce resources are integrated into quasi-dynamic cell formation and thus a quasi-dynamic dual-resource cell-formation problem is proposed. For solving this problem, this paper first establishes a non-linear mixed integer programming model, where inter-cell and intra-cell material cost, machine relocation cost, worker operation time, loss in batch quality and worker salary are to be minimised. Then, a multi-objective GA is developed to solve this model. Finally, a real life case study is conducted to validate the proposed model and algorithm. The actual operation results show that the case enterprise significantly decreases its material handling cost and workforce number and obviously increases its product quality after carrying out the obtained scheme.     

Multi-objective cell formation and production planning in dynamic virtual cellular manufacturing systems

This article presents a fuzzy goal programming-based approach for solving a multi-objective mathematical model of cell formation problem and production planning in a dynamic virtual cellular manufacturing system. In a dynamic environment, the product mix and part demand change over a planning horizon decomposed into several time periods. Thus, the cell formation done for one period may be no longer efficient for subsequent periods and hence reconfiguration of cells is required. Due to the variation of demand and necessity of reconfiguration of cells, the virtual cellular manufacturing (VCM) concept has been proposed by researchers to utilise the benefits of cellular manufacturing without reconfiguration charges. In a VCM system, machines, parts and workers are temporarily grouped for one period during which machines and workers of a group dedicatedly serve the parts of that group. The only difference of VCM with a real CM is that machines of the same group are not necessarily brought to a physical proximity in VCM. The virtual cells are created periodically depending on changes in demand volumes and mix, as new parts accumulate during a planning horizon. The major advantage of the proposed model is the consideration of demand and part mix variation over a multi-period planning horizon with worker flexibility. The aim is to minimise holding cost, backorder cost and exceptional elements in a cubic space of machine–part–worker incidence matrix. To illustrate the applicability of the proposed model, an example has been solved and computational results are presented.     

Cellular manufacturing system design using grouping efficacy-based genetic algorithm

This paper presents an algorithm for the design of manufacturing cells and part families. This algorithm is suitable for arriving at a good block diagonal structure for a cellular manufacturing design problem with part machine incidence matrix as input. The objective of this algorithm is the maximisation of grouping efficacy (GE), which is one of the most widely used measures of quality for cellular configurations. Assignment of machines to cells is using genetic algorithm, and part assignment heuristic is based on an effective customised rule. A comparison of the proposed algorithm is made with seven other methods of cell formation by taking 36 problems from the literature and found that the proposed algorithm is performing much better than the others. Finally, the algorithm is extended to form configurations with good GE when there are alternative routes.     

A methodology for designing flexible cellular manufacturing systems

Cell formation in cellular manufacturing deals with the identification of machines that can be grouped to create manufacturing cells and the identification of part families to be processed within each cell. Dynamic and random variations in part demands can negatively impact cell performance by creating unstable machine utilizations. The purpose of this paper is to introduce and illustrate an interactive cell formation method that can be used to design 'flexible' cells. Flexibility in this context refers to routing flexibility (i.e., the ability for the cellular system to process parts within multiple cells) and demand flexibility (i.e., the ability of the cell system to respond quickly to changes in part demand and part mix). Through an experimental analysis using multiple data sets, we also validate the procedure and provide guidelines for parameter settings depending upon the type of flexibility of interest to the user. Finally, trade-offs and interdependences between alternative types of flexibility in the context of cellular systems are illustrated.     

A general search algorithm for cell formation in group technology

Group Technology (GT) is a manufacturing approach, which organizes and uses the information about an item's similarity (parts and/or machines) to enhance efficiency and effectiveness of batch manufacturing systems. The application of group technology to manufacturing requires the identification of part families and formation of associated machine-cells. One approach is the Similarity Coefficient Method (SCM), an effective clustering technique for forming machine cells. SCM involves a hierarchical machine grouping process in accordance with computed ‘similarity coefficients’. While SCM is capable of incorporating manufacturing data into the machine-part grouping process, it is very sensitive to the data to be clustered (Chan and Milner 1982). It has been argued that for SCM to be meaningful, all machines must process approximately the same numbers of parts (Chan and Milner 1982).We present a new approach, based on artificial intelligence principles, to overcome some of these problems by incorporating an evaluation function into the grouping process. Our goal is to provide a method that is both practical and flexible in its use for the process of cell formation. Our method uses the similarity matrix to generate the feasible machine groups. Then an evaluation function is applied to select a machine-cell arrangement through an iterative process. The approach features a graph-based representation (N-tuple) to represent the problem and illustrate the solution strategies. Also, we develop an algorithm to search for the most promising machine groups from the graph. Compared with Single Linkage Clustering and Average Linkage Clustering approaches, our approach attains comparable or better results     

A mathematical model and a heuristic approach for design of the hybrid manufacturing systems to facilitate one-piece flow

One-piece flow is a design rule that entails production in manufacturing cells on a ‘make one, check one, and move-on one’ basis (Black, J.T., 2007. Design rules for implementing Toyota Production System. International Journal of Production Research, 45 (16), 3639–3664), which reduces manufacturing lead time significantly. This paper proposes a sequential methodology comprised of a mathematical model and a heuristic approach (HA) for the design of a hybrid cellular manufacturing system (HMS), to facilitate one-piece flow practice. The mathematical model is employed in the cases of small- and medium-sized problems, and it attempts to minimise the total number of exceptional operations, while considering machine capacities and alternative machines. The machine-part matrix achieved by the mathematical model is input into the flow line design stage of the HA, where backflow within the cells is eliminated. However, for industrial problems, the proposed HA is utilised. After the formation of the cells by clustering, the HA attempts to eliminate exceptional operations of a given cellular configuration together with a functional structure by employing alternative machines, based on the decision rules developed. Later, unidirectional flow within the cells is achieved and the capacity and budget constraints are satisfied. A medium-sized problem is solved by using both of the approaches, namely, the model integrated with the flow-line design stage of the HA and the complete HA. The results are discussed and the limitations are explained.     

Cell formation problem with consideration of both intracellular and intercellular movements

The cellular manufacturing system (CMS) is a well-known strategy which enhances production efficiency while simultaneously cutting down the system-wide operation cost. Most of the researchers have been focused on developing different approaches in order to identify machine-cells and part-families more efficiently. In recent years, researchers have also focused their studies more scrupulously by collectively considering CMS with production volume, operation sequence, alternative routing or even more. However, very few of them have tried to investigate both the allocation sequence of machines within the cells (intra-cell layout) and the sequence of the formed cells (inter-cell layout). Solving this problem is indeed very important in reducing the total intracellular and intercellular part movements which is especially significant with large production volume.

In this paper, a two-phase approach has been proposed to tackle the cell formation problem (CFP) with consideration of both intra-cell and inter-cell part movements. In the first phase, a mathematical model with multi-objective function is formed to obtain the machine cells and part families. Afterwards, in the second phase, another mathematical model with single-objective function is presented which optimizes the total intra-cell and inter-cell part movements. In other words, the scope of problem has been identified as a CFP together with the background objective of intra-cell and inter-cell layout problems (IAECLP). The primary assumption for IAECLP is that only linear layouts will be considered for both intra-cell and inter-cell. In other words, the machine within cells and the formed cells are arranged linearly. This paper studies formation of two mathematical models and used the part-machine incidence matrix with component operational sequence.

The IAECLP is considered as a quadratic assignment problem (QAP). Since QAP and CFP are NP-hard, genetic algorithm (GA) has been employed as solving algorithm. GA is a widespread accepted heuristic search technique that has proven superior performances in complex optimization problems and further it is a popular and well-known methodology. The proposed algorithms for CFP and IAECLP have been implemented in JAVA programming language.     

Dynamic cellular manufacturing system design considering alternative routing and part operation tradeoff using simulated annealing based genetic algorithm

In this paper, an integrated mathematical model of multi-period cell formation and part operation tradeoff in a dynamic cellular manufacturing system is proposed in consideration with multiple part process route. This paper puts emphasize on the production flexibility (production/subcontracting part operation) to satisfy the product demand requirement in different period segments of planning horizon considering production capacity shortage and/or sudden machine breakdown. The proposed model simultaneously generates machine cells and part families and selects the optimum process route instead of the user specifying predetermined routes. Conventional optimization method for the optimal cell formation problem requires substantial amount of time and memory space. Hence a simulated annealing based genetic algorithm is proposed to explore the solution regions efficiently and to expedite the solution search space. To evaluate the computability of the proposed algorithm, different problem scenarios are adopted from literature. The results approve the effectiveness of the proposed approach in designing the manufacturing cell and minimization of the overall cost, considering various manufacturing aspects such as production volume, multiple process route, production capacity, machine duplication, system reconfiguration, material handling and subcontracting part operation.     

Multiple routeings and capacity considerations in group technology applications

This paper addresses the problem of manufacturing cell formation, given multiple part routeings, and multiple functionally similar workcentres. Cellular manufacturing is intended to facilitate production, and thus should be based on projected production requirements. The originality of the approach lies in considering both the manufacturing system as well as projected production, and distributing the demand among alternate routeings in order to obtain a better manufacturing cell design. The suggested choice of part routeings favours the decomposition of the manufacturing system into manufacturing cells in a way that minimizes part traffic, along with satisfying the part demand and workcentre capacity constraints. We show that the problem can be formulated as a linear programming type problem which simultaneously addresses two problems: (i) routeing selection, and (ii) cell formation. The common objective is to minimize the inter-cell traffic in the system. The proposed algorithm iteratively solves two problems. The first problem is formulated as a linear-programming problem, while the latter is approached by an existing heuristic bottom-up aggregation procedure, known as Inter-Cell Traffic Minimization Method (ICTMM), enhanced appropriately.     

Configuration of cellular manufacturing systems using association rule induction

A cell-formation approach based on association rule induction is developed to find the effective configurations for cellular manufacturing systems. To gain the benefits of flexibility and efficiency, the manufacturing system is decomposed into several manageable subsystems by categorizing similar parts into part families and disparate machines into cells. It is advantageous to find the important associations among machines such that the occurrence of some machines in a machine cell will cause the occurrence of other machines in the same cell. Relationships among machines can be found from the process database by inducting association rules. By applying association rules to cell-formation problems, certain sets of machines (machine groups) that frequently process some parts together can be inducted. A data-mining technique referred to as association rule induction is used herein to find the association rules among machines from the process database. Seventeen data sets of various size and complexity were used to evaluate the effectiveness of the proposed cell-formation algorithm based on association rule induction. The performance of the proposed approach is compared with several existing techniques. From the computational results, the proposed approach shows its ability to find quality solutions.     

Design and scheduling of hybridmulti-cell flexible manufacturing systems

The objective of this paper is to minimize machine duplication by increasing its utilization, minimize intercell moves, simplify the scheduling problem and increase the flexibility of the manufacturing system. An integrated approach of design and scheduling alternative hybrid multi-cell flexible manufacturing systems (MCFMSs) in four steps will be presented in this paper. The first step is the implementation of branch and bound techniques which provide tools to design group technology (GT) cells. The second step is balancing the inter-cell workload of GT cells which leads to a hybrid MCFMS with better utilization of the machines. The problem of the exception machines and their utilization and workload balance will be solved within the MCFMScentre. Thus the performance of GT cells can be improved by transferring workloads from a congested (bottleneck) machine in one cell to an alternative one, a less congested (exception) machine in another cell within a group of GT cells forming a MCFMS centre. The third step is the group scheduling; a proposed heuristic method will be used for the scheduling of a family of parts with the objective of minimizing the maximum completion time of each part. The problem of scheduling under MCFMS can be reduced by considering the scheduling of each family of parts. Finally, the flexibility of the system will be enhanced by selecting appropriate machine tools and flexible material handling equipments. This approach is both effective and efficient-it has generated a hybrid MCFMS centre which includes several alternatives, for some benchmark problems in much shorter time than algorithms previously reported in the literature. In addition, the method is conceptually simple and easy to implement.