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.     

OOPPS: an object-oriented process planning system

This paper presents an object-oriented approach to the development of a generative process planning system—Object-Oriented Process Planning Systems (OOPPS). The system consists of three functional modules: object-oriented product model (OOPM) module, object-oriented manufacturing facility model (OOMFM) module, and object-oriented process planner (OOPP). The OOPM has a hierarchical structure with six classes of objects, class Products, class SubAssembly, class Part, class CSGTree, class Solid and class Feature. It can represent a product with all detailed information. The OOMFM is used to represent a cellular manufacturing system including machine cells, machine tools fixtures, and cutting tools. The OOPP generates process plans for parts using a multi-level hierarchical planning approach with four levels: cell-level planning, machine-level planning, fixture-level planning and tool-level planning. At the cell-level, all required operations are determined based on the feature specifications. Machine cells are then selected, based on the selected operations, for the minimal inter-cell movement. The machine-level planning selects the machines within the chosen cells. The fixtures are also selected on the selected machines. At the fixture-level planning, part setups and their sequences are selected. Finally, the tool-level planning determines all details for the process plans. An automated progamming system was also developed to link the OOPP to Smart CAM to generate CNC programs. An example has been used to illustrate the approach.     

Design of robust cellular manufacturing system for dynamic part population considering multiple processing routes using genetic algorithm

In this paper, a comprehensive mathematical model is proposed for designing robust machine cells for dynamic part production. The proposed model incorporates machine cell configuration design problem bridged with the machines allocation problem, the dynamic production problem and the part routing problem. Multiple process plans for each part and alternatives process routes for each of those plans are considered. The design of robust cell configurations is based on the selected best part process route from user specified multiple process routes for each part type considering average product demand during the planning horizon. The dynamic part demand can be satisfied from internal production having limited capacity and/or through subcontracting part operation without affecting the machine cell configuration in successive period segments of the planning horizon. A genetic algorithm based heuristic is proposed to solve the model for minimization of the overall cost considering various manufacturing aspects such as production volume, multiple process route, machine capacity, material handling and subcontracting part operation.     

Part-machine grouping using weighted similarity coefficients

The first step in the transition to cellular manufacturing is part-machine grouping. In this paper, grouping parts into families and machines into cells is done in two phases: by first grouping machines and then assigning parts. Limits both on the number of machines per cell and on the number of parts per family are considered. The number of cells is not fixed. A weighted sum of within-cell voids and out-of-cell operations is used to evaluate the part-machine grouping obtained. In Phase One, weighted similarity coefficients are computed and machines are clustered using a Tabu search algorithm. In Phase Two, part types are assigned to the previously formed groups using a linear minimum cost network flow model. The proposed approach is compared with three heuristics, namely ZODIAC, GRAFICS and MST, on a large number of problems.     

Manufacturing cell formation using a new self-organizing neural network

Cellular manufacturing consists of grouping similar machines in cells and dedicating each of them to process a family of similar part types. In this paper, grouping parts into families and machines into cells is done in two steps: first, part families are formed and then machines are assigned. In phase one, weighted similarity coefficients are computed and parts are clustered using a new self-organizing neural network. In phase two, a linear network flow model is used to assign machines to families. To test the proposed approach, different problems from the literature have been solved. As benchmarks we have used a Maximum Spanning Tree heuristic.     

Clustering algorithm for solving group technology problem with multiple process routings

Cell formation is an important problem in the design of a cellular manufacturing system. Most of the cell formation methods in the literature assume that each part has a single process plan. However, there may be many alternative process plans for making a specific part, specially when the part is complex. Considering part multiple process routings in the formation of machine-part families in addition to other production data is more realistic and can produce more independent manufacturing cells with less intercellular moves between them. A new comprehensive similarity coefficient that incorporates multiple process routings in addition to operations sequence, production volumes, duplicate machines, and machines capacity is developed. Also, a clustering algorithm for machine cell formation is proposed. The algorithm uses the developed similarity coefficient to calculate the similarity between machine groups. The developed similarity coefficient showed more sensitivity to the intercellular moves and produced better machine grouping.     

Formation of machine cells and part families in cellular manufacturing systems using a linear assignment algorithm

This paper presents a linear assignment algorithm for machine-cell and part-family formation for the design of cellular manufacturing systems. The present approach begins with the determination of part-family or machine-cell representatives by means of comparing similarity coefficients between parts or machines and finding a set of the least similar parts or machines. Using the group representatives and associated similarity coefficients, a linear assignment model is formulated for solving the formation problem by allocating the remaining parts or machines and maximizing a similarity index. Based on the formulated linear assignment model, a group formation algorithm is developed. The results of a comparative study based on multiple performance criteria and many existing data sets show that the present approach is very effective and efficient, especially in dealing with large-sized problems.     

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.     

Auction-based cooperation mechanism to parts scheduling for flexible job shop with inter-cells

This paper addresses cell part scheduling (CPS) problem. In this problem, parts may need to visit machines in different cells with consideration Inter-cell transportation time. The processing route of parts can be flexible. The objective is to minimize the overall process make-span. An integer nonlinear programming (INLP) model is formulated to determine the schedule scheme of all parts. An auction-based heuristic approach is proposed to solve it, which focuses on dealing with cooperation between different cells. In this approach, each cell can act as an auctioneer or a bidder. In an auction, it contains call for auction, bid construction, modify bids and winner announcement. A reference matrix is also applied in the auction to guarantee parts to finish as early as possible. Numerical experiments were conducted to test the auction-based approach. The results demonstrate the effectiveness, sensitivity and stability of the proposed auction-based approach, especially suitable for instances in large scale within a short calculating time.     

The sustainable cell formation problem: manufacturing cell creation with machine modification costs

An approach for manufacturing cell formation with machine modification is presented. In cell formation it is often important in practice to be able to reassign parts to additional machine types in order to create better cell configurations. This involves extending the set of parts that certain individual machines can process. Such extensions may be cheaper than simply purchasing additional machines. Thus, there is the possibility of machine modification to reduce inter-cell travel. The cost of such modifications must be balanced by the consequent reduction in inter-cell travel cost. The extended machine cell formation problem to be described involves the specification of which individual machines should be modified to enable them to process additional part types, part-machine assignment, and the grouping of individual machines for cell formation. The objective is to minimize the sum of the machine modification costs and the inter-cell travel. We call this the sustainable cell formation problem (SCFP). As far as the authors are aware, there have not been any solution procedures for this important problem reported in the open literature. It is our purpose to fill this gap by presenting a mixed integer programming model of the SCFP. We also propose and analyze greedy and tabu search heuristics for the design of large-scale systems related to the SCFP. Computational experience with the solution procedures indicates that they are likely to be useful additions to the production engineer's toolkit.     

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

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

Design and implementation of a relational data base for automated process planning

The function of process planning in a manufacturing facility is to identify the processes and the machines required to convert a design into its final form. Majority of the process plans are still made manually. The degree of the process plan detail varies with the shop environment. A feature-based process planning system which interacts with the SDRC I-DEAS solid modeling software is presented. The system operates under the UNIX environment. A relational database model which incorporates manufacturing details including the operation selection, machine selection, tool selection, fixture selection, etc. was developed and implemented. This relational database was structured using Microsoft SQL SERVER for the PC multi-user environment. This database is part of an ongoing research project on automated process planning and scheduling and primarily focuses on prismatic parts. The developed routines generate the Overall Removable Volume (ORV) graphically by comparing the desirable design to the blank work piece. The routines then decompose the ORV into various General Manufacturing Features (GMF) based on concave edges. The recognition routine captures geometrical and topological information and identifies the shape of each GMF. An expert system (using CLIPS expert system shell) analyzes the GMFs and determines appropriate operation(s) for the designed part. The developed expert system is capable of recommending the suitable machines, tools, fixtures, etc.     

A comparative study of similarity measures for manufacturing cell formation

We introduced a spectral clustering algorithm based on the bipartite graph model for the Manufacturing Cell Formation problem in [Oliveira S, Ribeiro JFF, Seok SC. A spectral clustering algorithm for manufacturing cell formation. Computers and Industrial Engineering. 2007 [submitted for publication]]. It constructs two similarity matrices; one for parts and one for machines. The algorithm executes a spectral clustering algorithm on each separately to find families of parts and cells of machines. The similarity measure in the approach utilized limited information between parts and between machines. This paper reviews several well-known similarity measures which have been used for Group Technology. Computational clustering results are compared by various performance measures.     

An Iterative Clustering Approach Based on Material Flow Requirements for Cellular Designs

This paper presents an iterative clustering process involving the addition of cells to a proposed cellular design to determine the best assignment of machines to cells. The assignment of machines to each cell is based on material flow clustering techniques with the objective of minimizing inter-cell flows. To determine the performance of the proposed clustering approach, comparisons are made with an Exhaustive Search (ES) approach to show the relative optimality.     

求解存在运输空间约束多单元协作调度问题的拍卖算法

针对存在运输空间约束的多单元协作调度问题,提出合理的运输模式,建立非线性整数规划模型,对问题进行描述.通过拍卖的方式,将设备资源和运输资源分配给每一个工件,得到问题的可行解,并基于改进的(非)连通图对可行解进一步优化.通过拍卖方式,可以恰当地针对不同时间段的资源进行价值评估,从而提高资源的利用率,减少总的生产时间.拍卖过程分为两部分:车辆资源拍卖和设备资源拍卖.在整个拍卖过程中,车辆和设备分别扮演拍卖者,每个工件扮演竞拍者.通过对比实验,验证了所提出运输模式的合理性以及算法的有效性.     

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.     

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.     

Simultaneous machine-part grouping approach in manufacturing cells

We present a comprehensive model including all of the operational constraints for solving a cell formation problem in cellular manufacturing systems. It is formulated as a generalized quadratic binary programming model with the objective of minimizing total moves evaluated as a weighted sum of inter- and intracell moves. Two most significant operational constraints included in the model are the sequence of operations associated with each part and the capability of assigning machines of the same type to different cells if two or more machines are considered due to workload requirements. The original model is Transformed into a linear binary programming model, and an example problem is solved using a commercial programming package. The final assignment of parts and machines to cells result in a lower total move than that evaluated from a previous study for the same problem.     

Machine-component grouping using genetic algorithms

One major problem in cellular manufacturing is the grouping of component parts with similar processing requirements into part families, and machines into manufacturing cells to facilitate the manufacturing of specific part families assigned to them. The objective is to minimize the total inter-cell and intra-cell movements of parts during the manufacturing process. In this paper, a mathematical model is presented to describe the characteristics of such a problem. An approach based on the concept of genetic algorithms is developed to determine the optimal machine-component groupings. Illustrative examples are used to demonstrate the efficiency of the proposed approach. Indeed, the results obtained show that the proposed genetic approach is a simple and efficient means for solving the machine-component grouping problem.     

Using throughput profit for selecting manufacturing process plan

In a task of process plan selection using workstations, manufacturing process plans have different precedence relationships, unequal operating times, and so on. It is necessary to consider these factors in evaluation models. Due to the use of different machines and tools that would increase the line efficiency with additional cost, a traditional total cost is not a good measure for the selection of manufacturing process plans. Hence, an evaluation model using throughput profit for each manufacturing process plan is proposed. In the first step of the proposed method, the precedence relationships of the manufacturing process for each part are decomposed. Several feasible combinations with different numbers of workstations and different task assignments are generated using a line balancing method. Then, an optimization model with associated throughput profit for process parameters is used for choosing the manufacturing process plans. Implementation examples are presented to illustrate this proposed procedure.