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.     

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.     

Simultaneous variable selection and outlier detection using a robust genetic algorithm

Given a dataset in which it is known that all spectra are representative, without error, and have matching accurate reference values, there are many tools which exist to determine the best set of variables to use for constructing an inverse model, such as partial least squares (PLS). Likewise, given that the best variables are known a priori, there are many tools that can be used to determine if any samples are outliers, either due to inaccurate reference values, or due to invalid spectra. However, in many real-world situations, the reference values contain error and the spectra are imperfect. In this situation, it is not always possible to determine either the best subset of samples or the best subset of variables. This paper presents a new technique for combining a robust outlier determination method with a genetic algorithm optimized for spectral variable selection. No assumptions are made as to the optimum set of variables or as to the amount and structure of the errors present in either the predictor (X) or predictand (Y) variables. The technique is best suited for datasets which contain redundant information, i.e., datasets from designed experiments with no replicates may not produce optimum results, as the experimental design implicitly assumes there are no outlier data.     

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.     

Incorporating cellular manufacturing into supply chain design

This paper presents a mathematical model. The model is used to integrate the design of cellular manufacturing systems with the design of a production network. The objective of the model is to minimize the sum of production and supply-chain costs. The model selects production (facility) locations and forms cells in the selected locations. Two heuristic procedures are presented to solve the model. These procedures are used to generate solutions for several test problems. The test shows the heuristic procedures generate solutions in a reasonable time frame. The results also show that the best solutions were generated by a tabu search procedure. The proposed approach is also compared with an approach that independently selects locations and then forms cells. This second test shows that reduced costs can be obtained using the integrated model.     

Determination of the optimal part orientation in layered manufacturing using a genetic algorithm

Several important factors must be taken into consideration to maximise the efficiency of rapid prototyping (RP) processes. The ability to select the optimal orientation of a build direction is one of the most critical factors in using RP processes, since it affects the quality of the prototyped part, the support structure and the build time. This study aims to determine the optimal part orientation that improves the average weighted surface roughness (AWSR) generated from the stair stepping effect. It also minimises the build time including the structure of the support in fabricating a completely freeform part. To avoid pre-selection operation, which is often troublesome and time-consuming, the genetic algorithm, that considers the fuzzy weight for surface roughness and build time, is used to determine the optimal orientation. The validity of the proposed algorithm is demonstrated by several examples using different RP systems and compared with previous works. The algorithm can help RP users select the best orientation of the part and carry out efficient process planning.     

Optimal part orientation in layered manufacturing using evolutionary stickers-based DNA algorithm

Over recent years, layered manufacturing (LM) has been one of the most important emerging research areas, as well as practice perspective, owing to its capability to reduce the product development time, and therefore time-to-market. In LM, owing to the significant role played by the part orientation in the successful and efficient reduction of the staircase effect, the determination of optimal part orientation is a matter of paramount importance. In this research, the dual parameters problem has been modelled, taking into consideration the constraints pertaining to the rotation of the computer aided design (CAD) model about two axes, while aiming to optimize the objective function that involves layered process error as well as build time. The current paper presents an advanced stickers-based DNA algorithm (SDNA) inspired by the characteristics of deoxyribonucleic acid (DNA) as a tool to achieve the optimal orientation during fabrication of a part. The salient feature of the proposed algorithm is the use of stickers along with DNA memory strand, which are responsible for the representation of information. Moreover, fundamental operations are applied to manipulate the positions of the stickers in essentially all the possible ways. The performance of SDNA has been tested on two standard case studies and the comparisons are made with results obtained from genetic algorithm (GA). The results clearly demonstrate the efficacy of proposed algorithm over GA when applied to the underlying problems.     

Agent-based dynamic part family formation for cellular manufacturing applications

One of the main critique on cellular manufacturing and its algorithms is their inability to handle dynamics events, especially dynamic changes in part spectrum. Unfortunately, there are not many efforts in the literature to overcome this problem. Agent oriented computing provides a marvellous opportunity to handle dynamic problems and to provide effective solutions, if carefully and intelligently implemented. In this paper, we have proposed a novel agent-based clustering algorithm for part family formation in cellular manufacturing by considering dynamic demand changes. However, it is not easy to directly compare the performance of the proposed algorithm with the literature results as there is no benchmark for dynamic cell formation problems. We attempt to compare the performance of the present algorithm on static test problems by dynamically introducing parts in these data-sets to our algorithm. Many results have been presented on these static data-sets by utilising several heuristics, meta-heuristics and optimisation-based algorithms. Although the proposed algorithm is not an optimisation-based algorithm and its operation is directed to handle dynamic changes in the problem domain through negotiation, we have shown that it has ability to provide very good results which are comparable to the best known solutions.     

Complete and fractional cell formation using Kohonen self-organizing map networks in a cellular manufacturing system

The primary objective of group technology (GT) is to enhance the productivity in batch manufacturing environment. The GT cell formation and fractional cell formation are done by using Kohonen self-organizing map (KSOM) networks. The effectiveness of the cell formation is measured with number of exceptional elements, bottleneck parts and grouping efficiency and the effectiveness of the fractional cell formation is measured by number of exceptional elements and the number of machines in the reminder cell. This method is applied to the known benchmarked problems found in the literature and it is found to be equal or best when compared to the other algorithms in terms of minimizing the number of the exceptional elements. The relative merits of using this method with respect to other known algorithms/heuristics in terms of computational speed and consistency are presented.     

Solving a new robust green cellular manufacturing problem with environmental issues under uncertainty using Benders decomposition

A cellular manufacturing system is a practical tool of group technology philosophy in a production environment. Although environmental issues have a significant impact on production processes, green considerations have not been studied in detail for such problems. This article aims to fill the gap by proposing a new mathematical model in which environmental issues, such as pollution caused by production and transportation modes, as well as waste, are considered. In addition, production planning and inventory balance among different periods are considered. Moreover, it is assumed that the processing times of products are uncertain and so a robust optimization approach is used to handle such uncertainty. The presented model is solved by the Benders decomposition algorithm. According to the outputs, the demand has the greatest effect on cell formation cost. Finally, the effect of green parameters on optimality is investigated.     

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.     

Fuzzy ART/RRR-RSS: a two-phase neural network algorithm for part-machine grouping in cellular manufacturing

In this paper an efficient methodology adopting Fuzzy ART neural network is presented to solve the comprehensive part-machine grouping (PMG) problem in cellular manufacturing (CM). Our Fuzzy ART/RRR-RSS (Fuzzy ART/ReaRRangement-ReaSSignment) algorithm can effectively handle the real-world manufacturing factors such as the operation sequences with multiple visits to the same machine, production volumes of parts, and multiple copies of machines. Our approach is based on the non-binary production data-based part-machine incidence matrix (PMIM) where the operation sequences with multiple visits to the same machine, production volumes of parts, and multiple identical machines are incorporated simultaneously. A new measure to evaluate the goodness of the non-binary block diagonal solution is proposed and compared with conventional performance measures. The comparison result shows that our performance measure has more powerful discriminating capability than conventional ones. The Fuzzy ART/RRR-RSS algorithm adopts two phase approach to find the proper block diagonal solution in which all the parts and machines are assigned to their most preferred part families and machine cells for minimisation of inter-cell part moves and maximisation of within-cell machine utilisation. Phase 1 (clustering phase) attempts to find part families and machines cells quickly with Fuzzy ART neural network algorithm which is implemented with an ancillary procedure to enhance the block diagonal solution by rearranging the order of input presentation. Phase 2 (reassignment phase) seeks to find the best proper block diagonal solution by reassigning exceptional parts and machines and duplicating multiple identical machines to cells with the purpose of minimising inter-cell part moves and maximising within-cell machine utilisation. To show the robustness and recoverability of the Fuzzy ART/RRR-RSS algorithm to large-size data sets, a modified procedure of replicated clustering which starts with the near-best solution and rigorous qualifications on the number of cells and duplicated machines has been developed. Experimental results from the modified replicated clustering show that the proposed Fuzzy ART/RRR-RSS algorithm has robustness and recoverability to large-size ill-structured data sets by producing highly independent block diagonal solution close to the near-best one.     

A simulation analysis of factors influencing the flexibility of cellular manufacturing

The performance of cellular manufacturing (CM) systems in a variable demand and flexible workforce environment has been examined using simulation modelling. Discrepancies between academicians and practitioners’ findings with respect to flexibility and uneven machine utilization in CM systems are discussed. The views of two parties were incorporated in simulation models to rectify the existing discrepancies. While the results of this study confirm the previous findings of academicians regarding the deterioration of the performance of CM in a variable product mix situation, it appears that those results may be significantly influenced by considering a flexible workforce. The simulation results show that the practice of using flexible crossed-trained operators can improve the flexibility of CM in dealing with an unstable demand and can reduce load imbalance inherent in machine dedication in manufacturing cells.     

Efficient optimization of process parameters in shadow mask manufacturing using NNPLS and genetic algorithm

A shadow mask, the primary component of a cathode ray tube (CRT), is used to prevent the outer edges of electron beams from hitting incorrect phosphor dots. It is fabricated by means of a photo-etching process consisting of a few hundred/thousand process parameters. A primary concern in the management of the process is to determine the optimal process parameter settings necessary to sustain the desired levels of product quality. The characteristics of the process, including a large number of process parameters and collinear observed data, make it difficult to accomplish the primary concern. To cope with the difficulties, a two-phase approach is employed that entails the identification of a few critical process parameters, followed by determination of the optimal parameter settings. The former is obtained through the operator's domain knowledge and the NNPLS-based prediction model built between process parameters and quality defects. The latter is obtained by solving an optimization problem using a genetic algorithm (GA). A comparative study shows that the proposed approach improves product quality greatly in the shadow-mask manufacturing process.     

A simulated annealing algorithm based on a closed loop layout for facility layout design in flexible manufacturing systems

Facility layout design problems in flexible manufacturing systems (FMS) differ from traditional facility design problems and are more difficult to solve because there are more constraints that must be considered (i.e., cell shape, cell orientation, pick-up and drop-off point positions). The focus of this paper is on the closed loop type layout, which is based on a predetermined layout pattern. This layout pattern is commonly found in manufacturing settings since it requires a simplified material handling system configuration and since it facilitates a modular and expandable layout structure. The open-field type layout problem, where there is no predetermined layout pattern, may potentially have a more efficient configuration, since there are fewer restrictions. However, this problem is more difficult to solve and may result in configurations that are not desirable due to the lack of structure or modularity. The procedure developed in this paper improves the efficiency of the closed loop configuration by changing the rectangular shape of the loop to different sizes. In many cases, the resulting closed loop layout proves to be as efficient as the open field layout. A simulated annealing procedure (SA-CL) is used to search for the configuration that minimizes the total material handling costs. A comparison of the results with existing methods indicates that, based on solution quality and computational time, the SA-CL offers a favourable alternative for efficient layout design.     

多单元制造系统布局设计

从布局设计的角度,提出多单元制造系统的概念,把各种制造系统的布局问题转化为多单元制造系统布局设计问题,包括设备布局和制造单元布局两个方面。对于设备布局问题,给出一种优化建模与虚拟现实技术相结合的求解策略;对于单元布局问题,给出一种集成的布局设计方法。     

Explicit consideration of multiple objectives in cellular manufacturing

Although many methodologies have been proposed for solving the cell-formation problem, few of them explicitly consider the existence of multiple objectives in the design process. In this article, the development of multi-objective genetic programming single-linkage cluster analysis (GP-SLCA), an evolutionary methodology for the solution of the multi-objective cell-formation problem, is described. The proposed methodology combines an existing algorithm for the solution of single-objective cell-formation problems with NSGA-II, an elitist evolutionary multi-objective optimization technique. Multi-objective GP-SLCA is able to generate automatically a set of non-dominated solutions for a given multi-objective cell-formation problem. The benefits of the proposed approach are illustrated using an example test problem taken from the literature and an industrial case study.     

Using an evolutionary algorithm for catalog design

This paper describes an evolutionary algorithm that was developed for catalog design. This algorithm is based on genetic algorithms, but uses an object-oriented coding scheme to represent a design, and introduces unique crossover and mutation operators. To account for the dependence of system performance on both system configuration and component selection, the evolutionary algorithm allows for simultaneous alterations of configurations and components. This new approach allows the consideration of alternate configurations and allows the configurations to evolve to make the best use of the available components. Using this evolutionary algorithm, a piping system was designed in which cooling fluid was delivered to three machines on a manufacturing floor at specified pressures and flow rates. The algorithm was able to find good designs that satisfied the given design specifications.     

A simulation-based multi-objective genetic algorithm (SMOGA) procedure for BOT network design problem

Solving optimization problems with multiple objectives under uncertainty is generally a very difficult task. Evolutionary algorithms, particularly genetic algorithms, have shown to be effective in solving this type of complex problems. In this paper, we develop a simulation-based multi-objective genetic algorithm (SMOGA) procedure to solve the build-operate-transfer (BOT) network design problem with multiple objectives under demand uncertainty. The SMOGA procedure integrates stochastic simulation, a traffic assignment algorithm, a distance-based method, and a genetic algorithm (GA) to solve a multi-objective BOT network design problem formulated as a stochastic bi-level mathematical program. To demonstrate the feasibility of SMOGA procedure, we solve two mean-variance models for determining the optimal toll and capacity in a BOT roadway project subject to demand uncertainty. Using the inter-city expressway in the Pearl River Delta Region of South China as a case study, numerical results show that the SMOGA procedure is robust in generating ‘good’ non-dominated solutions with respect to a number of parameters used in the GA, and performs better than the weighted-sum method in terms of the quality of non-dominated solutions.     

Improving the implementation effectiveness of cellular manufacturing: a comprehensive framework for practitioners

In today's competitive environment cellular manufacturing (CM) is a well-known strategy in improving manufacturing performance. To obtain the full benefits that CM has to offer successful implementation is a critical factor. Evidence indicates that firms converting to CM often struggle with implementation and achieve results that are less than anticipated. A comprehensive review of implementation literature was undertaken and a multi-phase model developed and evaluated through a case study. The framework recognizes the importance of both technical and human aspects of CM and provides practitioners with a better understanding of the various phases in the implementation process, including the many activities and issues which need to be considered for each step. In the case study company, implementation of CM not only provided many of the benefits associated with this form of manufacturing but also allowed operators to become a value-adding link in respect to process and product improvement and new product development.