A close neighbour algorithm for designing cellular manufacturing systems

The first step in creating a cellular manufacturing system is to identify machine groups and form part families. Clustering and data organization (CDR) algorithms (such as the bond energy algorithm) and array sorting (ARS) methods (such as the rank order clustering algorithm) have been proposed to solve the machine and part grouping problem. However, these methods do not always produce a solution matrix that has a block diagonal structure, making visual identification of machine groups and part families extremely difficult. This paper presents a ‘close neighbour algorithm’ to solve this problem. The algorithm overcomes many deficiencies of the CDR and ASM methods. The algorithm is tested against ten existing algorithms in solving test problems from the literature. Test results show that the algorithm is very reliable and efficient.     

A multi-objective genetic algorithm approach to the design of cellular manufacturing systems

In this paper, a multi-objective integer programming model is constructed for the design of cellular manufacturing systems with independent cells. A genetic algorithm with multiple fitness functions is proposed to solve the formulated problem. The proposed algorithm finds multiple solutions along the Pareto optimal frontier. There are some features that make the proposed algorithm different from other algorithms used in the design of cellular manufacturing systems. These include: (1) a systematic uniform design-based technique, used to determine the search directions, and (2) searching the solution space in multiple directions instead of single direction. Four problems are selected from the literature to evaluate the performance of the proposed approach. The results validate the effectiveness of the proposed method in designing the manufacturing cells.     

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 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 robust cell formation approach for varying product demands

In cellular manufacturing environments, manufacturing cells are generally formed based on deterministic product demands. In this paper, we consider a system configuration problem with product demands expressed in a number of probabilistic scenarios. An optimization model integrating cell formation and part allocation is developed to generate a robust system configuration to minimize machine cost and expected inter-cell material handling cost. A two-stage Tabu search based heuristic algorithm is developed to find the optimal or near optimal solutions to the NP-hard problem. Numerical examples show that this model leads to an appropriate compromise between system configuration costs and expected material handling costs to meet the varying product demands. These example problems also show that the proposed algorithm is effective and computationally efficient for small or medium size problems.     

Exact and approximate algorithms for part-machine clustering based on a relationship between interval graphs and Robinson matrices

An important manufacturing cell formation problem requires permutations of the rows (parts) and columns (machines) of a part-machine incidence matrix such that the reordered matrix exhibits a block-diagonal form. Numerous objective criteria and algorithms have been proposed for this problem. In this paper, a new perspective is offered that is based on the relationship between the consecutive ones property associated with interval graphs and Robinson structure within symmetric matrices. This perspective enables the cell formation problem to be decomposed into two permutation subproblems (one for rows and one for columns) that can be solved optimally using dynamic programming or a branch-and-bound algorithm for matrices of nontrivial size. A simulated annealing heuristic is offered for larger problem instances. Results pertaining to the application of the proposed methods for a number of problems from the literature are presented.     

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.     

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.     

Cell formation using a Fuzzy Min-Max neural network

This paper proposes the application of a Fuzzy Min-Max neural network for part family formation in a cellular manufacturing environment. Once part families have been formed, a minimum cost flow model is used to form the corresponding machine cells. For simplicity, the input data are in the form of a binary part- machine incidence matrix, although the algorithm can work with an incidence matrix with continuous values. The application of Fuzzy Min-Max is interpreted in physical terms and compared with a related neural network applied previously for cell formation, the Fuzzy ART network. Both neural networks have similarities and differences that are outlined. The algorithms have been programmed and applied to a large set of problems from the literature. Fuzzy Min-Max generally outperforms Fuzzy ART, and the computational times are small and similar in both algorithms.     

A genetic scheduling methodology for virtual cellular manufacturing systems: an industrial application

Effective solutions to the cell formation and the production scheduling problems are vital in the design of virtual cellular manufacturing systems (VCMSs). This paper presents a new mathematical model and a scheduling algorithm based on the techniques of genetic algorithms for solving such problems. The objectives are: (1) to minimize the total materials and components travelling distance incurred in manufacturing the products, and (2) to minimize the sum of the tardiness of all products. The proposed algorithm differs from the canonical genetic algorithms in that the populations of candidate solutions consist of individuals of different age groups, and that each individual's birth and survival rates are governed by predefined aging patterns. The condition governing the birth and survival rates is developed to ensure a stable search process. In addition, Markov Chain analysis is used to investigate the convergence properties of the genetic search process theoretically. The results obtained indicate that if the individual representing the best candidate solution obtained is maintained throughout the search process, the genetic search process converges to the global optimal solution exponentially.

The proposed methodology is applied to design the manufacturing system of a company in China producing component parts for internal combustion engines. The performance of the proposed age-based genetic algorithm is compared with that of the conventional genetic algorithm based on this industrial case. The results show that the methodology proposed in this paper provides a simple, effective and efficient method for solving the manufacturing cell formation and production scheduling problems for VCMSs.     

A multi-period scheduling method for trading-off between skilled-workers allocation and outsource service usage in dynamic CMS

In this paper, a new method is proposed for short-term period scheduling of dynamic cellular manufacturing systems in a dual resource constrained environment. The aim of this method is to find best production strategy of in-house manufacturing using worker assignment (both temporary and skilled workers) and outsourcing, while part demands are uncertain and can be varied periodically. For this purpose, a multi-period scheduling model has been proposed which is flexible enough to use in real industries. To solve the proposed problem, a number of metaheuristics are developed including Branch and Bound; a hybrid Tabu Search and Simulated Annealing algorithms and a hybrid Ant Colony Optimization and Simulated Annealing algorithms. A Taguchi method (L₂₇ orthogonal optimisation) is used to estimate parameters of the proposed method in order to solve experiments derived from the literature. For evaluating the system imbalance in dynamic market demands, a new measuring index is developed. Our findings indicate that the uncertain market demands affects the part allocating which may induce workstation-load variations that yield to cell-load variation accordingly. To solve this problem, two methods are offered. The results show that promoting staff and using freezing technique are promising ways to reduce system imbalance while confronting with the mentioned condition. The outcomes also show the superiority of the proposed hybrid method in providing solutions with better quality.     

CF-GGA: A grouping genetic algorithm for the cell formation problem

In manufacturing, the machine-part cell formation (MPCF) problem addresses the issues surrounding the formation of part families based on the processing requirements of the components, and the identification of machine groups based on their ability to process specific part families. Past research has shown that one key aspect of attaining efficient groupings of parts and machines is the block-diagonalization of the given machine-part (MP) incidence matrix. This paper presents and tests a grouping genetic algorithm (GGA) for solving the MPCF problem and gauges the quality of the GGA's solutions using the measurements of efficiency (Chandrasekharan and Rajagopalan 1986a) and efficacy (Kumar and Chandrasekharan 1990). The GGA in this study, CF-GGA, a grouping genetic algorithm for the cell formation problem, performs very well when applied to a variety of problems from the literature. With a minimal number of parameters and a straightforward encoding, CF-GGA is able to match solutions with several highly complex algorithms and heuristics that were previously employed to solve these problems.     

A genetic algorithm for facility layout

Facility layout is an important aspect of designing any manufacturing setup. However, the problem of finding optimal layouts is hard and deterministic techniques are not computationally feasible. In this work a genetic algorithm is presented for obtaining efficient layouts. The different aspects involved in the design of efficient genetic algorithms are discussed in detail. It is shown that the population maintained by the genetic algorithm for facility layout should consist of feasible solutions only. A new efficient crossover operator is developed. Experimental results obtained with the proposed algorithm on test problems taken from the literature are promising.     

A multi-objective and integrated model for supply chain scheduling optimization in a multi-site manufacturing system

In a supply chain, scheduling plays a significant role in coordinating and cooperation. This article considers an integration of supplier and vehicle scheduling problems in terms of vehicle routing determination for transporting raw materials from the suppliers to some manufacturing centres. The aim is to minimize the total tardiness of all assigned orders to the suppliers and simultaneously minimize the total travelled distance of the vehicles. Most manufacturing companies, which have to manage their suppliers as an industrial unit, experience this problem. A new metaheuristic algorithm called the multiple league championship algorithm (MLCA), inspired by championship matches, is proposed to solve this problem. To show the efficiency of MLCA, it is compared with two different algorithms used for the problems in the literature that are closest to this problem and a soccer-based algorithm called golden ball. The experimental results prove that the proposed algorithm has better performance than these algorithms.     

Multi-objective optimization of engineering systems using game theory and particle swarm optimization

This study proposes particle swarm optimization (PSO) based algorithms to solve multi-objective engineering optimization problems involving continuous, discrete and/or mixed design variables. The original PSO algorithm is modified to include dynamic maximum velocity function and bounce method to enhance the computational efficiency and solution accuracy. The algorithm uses a closest discrete approach (CDA) to solve optimization problems with discrete design variables. A modified game theory (MGT) approach, coupled with the modified PSO, is used to solve multi-objective optimization problems. A dynamic penalty function is used to handle constraints in the optimization problem. The methodologies proposed are illustrated by several engineering applications and the results obtained are compared with those reported in the literature.     

Effective two-phase p-median approach for the balanced cell formation in the design of cellular manufacturing system

In this paper, we present an effective two-phase p-median approach for the balanced cell formation (CF) in the design of cellular manufacturing system. In phase 1, the p-median mathematical model of machine CF, which adopts a linear integer programming formulation, is developed. Our formulation uses a new similarity coefficient based on the generalised nonbinary part-machine incidence matrix (PMIM) which incorporates realistic manufacturing aspects such as setup time, processing time, operation sequences and lot size of parts and duplicate machine types. In phase 2, a systematic part assignment procedure based on the new classification scheme of part types is established in pursuit of balancing the workload among machine cells. New efficiency measures for evaluating the quality of the binary and nonbinary PMIM-based block diagonal solutions are proposed to judge the degree of cell load imbalance. Computational experiments with moderately intermediate-sized data-sets selected from the literature show effectiveness of our two-phase p-median approach for the balanced CF.     

Part-machine cell formation in group technology using a simulated annealing-based meta-heuristic

The part-machine cell formation problem (PMCFP) is a crucial step in the design of a cellular manufacturing system and has received considerable research attention over the last five decades. This study proposes a simulated annealing-based meta-heuristic for solving the PMCFP. The effectiveness of the proposed approach is compared to conventional algorithms across a set of PMCFPs available in the literature. Computational results using four types of performance measures show that the proposed simulated annealing-based meta-heuristic is highly effective by comparison with conventional algorithms for PMCFPs on the same test problems.     

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.     

A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times

In this paper, we contemplate the problem of scheduling a set of n jobs in a no-wait flexible flow shop manufacturing system with sequence dependent setup times to minimising the maximum completion time. With respect to NP-hardness of the considered problem, there seems to be no avoiding application of metaheuristic approaches to achieve near-optimal solutions for this problem. For this reason, three novel metaheuristic algorithms, namely population based simulated annealing (PBSA), adapted imperialist competitive algorithm (AICA) and hybridisation of adapted imperialist competitive algorithm and population based simulated annealing (AICA?+?PBSA), are developed to solve the addressed problem. Because of the sensitivity of our proposed algorithm to parameter's values, we employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm to enhance solutions accuracy. These proposed algorithms were coded and tested on randomly generated instances, then to validate the effectiveness of them computational results are examined in terms of relative percentage deviation. Moreover, some sensitive analyses are carried out for appraising the behaviour of algorithms versus different conditions. The computational evaluations manifestly support the high performance of our proposed novel hybrid algorithm against other algorithms which were applied in literature for related production scheduling problems.     

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.