The cost of eliminating exceptional elements in group technology cell formation

Many researchers have suggested methods for the formation of machine cells/part families in group technology. However, few of these methods have addressed the possible existence of exceptional elements (EE) in a reasonable manner. EE can be the result of bottleneck machines whose processing is needed by parts assigned to more than one part family. They can also be caused by parts that require processing on machines assigned to more than one machine cell. The existence of EE in cell formation solutions is a nontrivial problem that requires interaction between machine cells intended to be independent for production efficiency. This paper presents a systematic method for identifying opportunities for reducing the number of intercell transfers caused by the existence of EE. The method recognizes how each EE in a cell formation solution may be involved in the creation of intercell transfers. The sequence of operation in each part routeing is also considered. The method then analyses the costs associated with alternative actions for the removal of the EE. The result is a prioritized list (based on relative cost-effectiveness) of the EE-removal actions. The method recognizes that interdependencies exist among EE: actions taken to eliminate one EE may have an effect on others as well. The process is demonstrated with an example.     

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.     

Integrated group technology,cell formation,process planning,and production planning with application to the emergency room

In this paper an integrated approach for the formation of parts and machine families in group technology is developed. The integrated approach is used to solve cell formation, process planning, and production planning simultaneously. The given information is part processing sequence, part production volume, part alternative processing plans, and part processing times. The approach is used to determine the machine-part cells and part processing plans, while the total intercell part flow is minimized. Also, the convergence of the algorithm is investigated. The approach goes across and beyond the group technology methods by considering sequencing, production planning, process planning, and part-machine cellular information simultaneously. Two methods are investigated: exact (optimal) and heuristic. The approach first solves an integer programming problem to find processing plans and then uses a procedure to form the machine-part cells. The proposed approach solves the problem iteratively until a set of plans for machine-part cell formations is obtained with minimal intercell part flow or interflow cost. An example is presented to explain the developed approach. Experimental results are also provided. An extension of the approach for solving the operations planning of an emergency room is also covered. In this extension of the approach, the application of cell formation provides a solution to efficiently managing patients and utilizing resources. By grouping patients by their needed medical procedures, time and resource efficiency is accomplished. An application to ER of University Hospitals of Case Western Reserve University is given.     

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.     

Manufacturing cells' design in consideration of various production factors

A cell formation problem is introduced that incorporates various real-life production factors such as the alternative process routing, operation sequence, operation time, production volume of parts, machine capacity, machine investment cost, machine overload, multiple machines available for machine types and part process routing redesigning cost. None of the cell formation models in the literature has considered these factors simultaneously. A similarity coefficient is developed that incorporates alternative process routing, operation sequence, operation time and production volume factors. Although very few studies have considered the machine capacity violated issue under the alternative process routing environment, owing to the difficulties of the issue discussed here, these studies fail to deal with the issue because they depend on some unrealistic assumptions. Five solutions have been proposed here and are used to cope with this difficulty. A heuristic algorithm that consists of two stages is developed. The developed similarity coefficient is used in stage 1 to obtain basic machine cells. Stage 2 solves the machine-capacity violated issue, assigns parts to cells, selects process routing for each part and refines the final cell formation solution. Some numerical examples are used to compare with other related approaches in the literature and two large size problems are also solved to test the computational performance of the developed algorithm. The computational results suggest that the approach is reliable and efficient in either the quality or the speed for solving cell formation problems.     

A cut-tree-based approach for clustering machine cells in the bidirectional linear flow layout

This paper considers the joint cell clustering-layout problem where machine cells are to be located along the popular bidirectional linear material flow layout. The joint problem seeks to minimize the actual intercell flow cost instead of the typical measure that minimizes the number of intercell movements when the layout problem is excluded from the clustering process. Owing to the computational difficulty, a three-phase approach is proposed using the cut-tree-network model to solve this joint problem. The cell clustering and layout problem is transformed into a multi-terminal network flow model. A cut tree is constructed and partitioned into a number of subgraphs via the selected primary path. Each subgraph is a clustered cell and their locations are assigned to the layout sequence by comparing the cut capacities. Thus, the proposed approach concurrently determines the machine cells and their relative sequences in the bidirectional linear flow layout. Computational procedures are illustrated and additional experiments, with data adapted from the literature, are performed to demonstrate the viability of the approach.     

A genetic algorithm for manufacturing cell formation with multiple routes and multiple objectives

This paper presents a genetic algorithm (GA) approach to the machine-component grouping problem with multiple objectives: minimizing costs due to intercell and intracell part movements; minimizing the total within cell load variation; and minimizing exceptional elements. Manufacturing cells are formed based on production data, e.g. part routing sequence, production volume and workload. Also, we will discuss the implication of part alternative routings and the method we suggest to deal with it. Special genetic operators are developed and multiple experiments are performed. Finally, the results obtained with the proposed algorithm on the tested problems are compared with those of others.     

GT cell formation for minimizing the intercell parts flow

A methodology is proposed to design a GT cell by considering the intercell parts flow in GT cellular manufacturing systems. The problem of GT cell formation is described in a graph using the quantities to be produced in the specified time period and the process routes for producing the products. The objective of this paper is to minimize the total number of parts produced in more than one cell. The problem, formulated as a quadratic assignment problem (QAP), is solved using both Lagrangean relaxation technique and the optimality conditions of quadratic program. Furthermore, in order to obtain the giobal optimal solution rather than the local optimal solution, a branch-and-bound algorithm is employed. Finally, numerical examples are used to show the effectiveness of the solution techniques and GT cell formation procedure. Moreover, a computer simulation is presented, showing the effectiveness of cellular manufacturing systems     

Intercell scheduling: A negotiation approach using multi-agent coalitions

Intercell scheduling problems arise as a result of intercell transfers in cellular manufacturing systems. Flexible intercell routes are considered in this article, and a coalition-based scheduling (CBS) approach using distributed multi-agent negotiation is developed. Taking advantage of the extended vision of the coalition agents, the global optimization is improved and the communication cost is reduced. The objective of the addressed problem is to minimize mean tardiness. Computational results show that, compared with the widely used combinatorial rules, CBS provides better performance not only in minimizing the objective, i.e. mean tardiness, but also in minimizing auxiliary measures such as maximum completion time, mean flow time and the ratio of tardy parts. Moreover, CBS is better than the existing intercell scheduling approach for the same problem with respect to the solution quality and computational costs.     

Genetically assisted optimization of cell layout and material flow path skeleton

A continuous plane manufacturing cell layout and intercell flow path skeleton problem formulation involving rectilinear distances between cell input/output stations is mapped to a genetic search space. Certain properties of such a search space are exploited to design a very efficient method for reduction of a mixed-integer programming problem formulation to an iterative sequence of linear programming problems. This paper reports theoretical and computational insights for efficiently finding good solutions for the above problem formulation, taking advantage of the solution structure and the search stage. The scores of the objective function on a set of test cases indicate better solutions than those previously reported in the literature. The empirical results based on multiple runs also suggest that the method generates final results that are not dependent on the quality of the initial solution; hence the solution search seems to be more global than many of the previous approaches.     

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.     

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.     

Application of simulated annealing to a linear model forthe formulation of machine cells ingroup technology

The central issue in group technology is the cell formation problem, which involves the grouping of parts into families and machines into cells, so that parts with similar manufacturing (and design) attributes are identified and processed by dedicated cells of machines. In the present work, the cell formation problem is modelled as a linear integer programming problem with the objective of minimizing the number of intercellular moves subject to cell-size constraints and taking into account the machine operation sequence of each part. An interesting feature of the proposed formulation is that there is no need of specifying a priori the number of cells to be used, which is automatically adjusted within the solution procedure. A very efficient random search heuristic algorithm, based on the simulated annealing method, is adopted for its solution. The heuristic is tested on a number of problems and its performance is evaluated. Subsequently, a straight forward model is presented to identify the families of parts which are to be processed by the corresponding machine cells.     

Group technology cell formation considering operation sequences and production volumes

In this paper a new approach for minimizing intercell part flows in cellularmanufacturing is proposed. Two types of production data-based part-machine incidence matrices (PMIMs) are developed to reflect the real-field data such as the operation sequences and production volumes of the parts to be manufactured. The type I production data-based PMIM represents the actual flows to or from machines by parts. A 0?1 linear formulation using the type I production data-based PMIM is developed to minimize the total intercell flows. Once the type I production data-based PMIM is obtained, a type II production data-based PMIM is constructed to reflect the actual intercell flows by bottleneck parts requiring operations outside its corresponding cell. Computational results with the well known data sets in literature show that the proposed production data-based PMIMs can be used as the fundamental replacements over the classical binary PMIM in the cell formation problem, and the mathematical model based on the new PMIMs reflecting the real-field data can be applied effectively to proper medium-sized cell formation problems.     

Automatic clustering for generalised cell formation using a hybrid particle swarm optimisation

This paper considers the cell formation (CF) problem in which parts have alternative process routings and the number of machine cells is not known a priori. Very few studies address these two practical issues at the same time. This paper proposes an automatic clustering approach based on a hybrid particle swarm optimisation (PSO) algorithm that can automatically evolve the number and cluster centres of machine cells for a generalised CF problem. In the proposed approach, a solution representation, comprising an integer number and a set of real numbers, is adopted to encode the number of cells and machine cluster centres, respectively. Besides, a discrete PSO algorithm is utilised to search for the number of machine cells, and a continuous PSO algorithm is employed to perform machine clustering. Effectiveness of the proposed approach has been demonstrated for test problems selected from the literature and those generated in this study. The experimental results indicate that the proposed approach is capable of solving the generalised machine CF problem without predetermination of the number of cells.     

RMS中工件路径网络生成方法

利用图论建立RMS中工件路径网络生成模型。给出设备物理布局生成的3种算法：设备物理规划布局算法、基于二次布置问题(QAP)模型的VMC设备物理布局算法以及已有设备物理布局算法。给出AGV路径网络生成算法、AGV路径网络生成改进算法、可替代路径网络生成算法,包括节点间最短路径寻找子算法、路径网络预处理子算法。算法的输入为表示重构对象节点间距离信息的距离矩阵文件和表示某生产周期多工艺路线的流量文件,输出为优化的路径网络。用Visual C 实现了以上算法,实例测试验证了算法的正确性。     

A correct minimal siphons extraction algorithm from a maximal unmarked siphon of a Petri net

When using the machine grouping approach for designing cellular manufacturing cells, improper machine assignment commonly arises resulting in higher intercellular movement of parts. The objective of this paper is therefore to examine the cause of such a problem and to propose a workable optimal solution for it. A machine grouping algorithm that is based in the new machine unit concept is developed and the solution is proven to be optimal at each stage. A comparison of the proposed model with two existing algorithms is presented, followed by a discussion on the behaviour of machine cell formation.     

A two-phase heuristic algorithm for cell formation problems considering alternative part routes and machine sequences

In this paper, we deal with the multi-objective machine cell formation problem. This problem is characterized as determining part route families and machine cells such that the total sum of inter-cell part movements and maximum machine workload imbalance are simultaneously minimized. Together with the objective function, alternative part routes and the machine sequences of part routes are considered in grouping part route families. Also, it is assumed that the number of machine cells is not pre-defined. Owing to the complexity of the problem, a two-phase heuristic algorithm is proposed. Computational experiments were conducted to verify the performance of the algorithm. Throughout the computational experiments, we verified that the two-phase heuristic algorithm is effective for large-scale machine cell formation problems.     

A multi-objective procedure for labour assignments and grouping in capacitated cell formation problems

A hierarchical methodology for the design of manufacturing cells is proposed, which includes labour-grouping considerations in addition to partmachine grouping. It is empirically driven and designed for an interactive decision environment, with an emphasis on fast execution times. The method synthesizes the capabilities of neural network methods for rapid clustering of large partmachine data sets, with multi-objective optimization capabilities of mathematical programming. The procedure includes three phases. In Phase I, part families and associated machine types are identified through neural network methods. Phase II involves a prioritization of part families identified, along with adjustments to certain load-related parameters. Phase III involves interactive goal programming for regrouping machines and labour into cells. In machine grouping, factors such as capacity constraints, cell size restrictions, minimization of load imbalances, minimization of intercell movements of parts, minimization of new machines to be purchased, provision of flexibility, etc. are considered. In labour grouping, the functionally specialized labour pools are partitioned and regrouped into cells. Factors such as minimization of hiring and cross-training costs, ensuring balanced loads for workers, minimization of intercell movements of workers, providing adequate levels of labour flexibility, etc. are considered in a pragmatic manner.     

A sequence-based materials flow procedure for designing manufacturing cells

One of the most important problems in designing a cellular manufacturing system is the formation of machine cells and the grouping of parts. Most of the existing cell design procedures operate on a binary part-machine incidence matrix to identify block diagonality. Important factors such as part operation sequence and demand volume have not been commonly considered in past research. In this paper, a sequence-based materials flow procedure is developed to solve the cell formation problem. The new cell formation procedure is designed to consider operation sequences in accurately determining the costs of inter-cell movement, as well as forward and backward intra-cell movements. Extensive comparisons of the new cell formation procedure with the relevant existing procedures in the literature demonstrate the effectiveness of the new procedure.