Network flow partitioning procedures for the analysis of cellular manufacturing systems

Abstract

The primary objective of this study is to develop a network-flow based procedure for grouping the machines of a manufacturing system into cells, and the parts to be processed into families, in such a way that the overall intercellular flow of parts is minimized. In order to develop a meaningful comprehensive cell formation approach, the following three important cases are considered: (1) Unrestricted number of cells and unrestricted cell size, (2) Restricted number of cells and unrestricted cell size, and (3) Restricted number of cells and restricted cell size. After designing the machine cells, parts are integrated into part families based on the machine requirements with the restriction on part family size. The network methodology consists of three phases: (1) preprocessing phase for computing the functional relationship between machines for a network modeling of the problem; (2) partitioning phase for manufacturing cell formation; and (3) part family identification phase. The first phase computes the functional relationship between machines based on two kinds of processing information (machine-part matrix and operation sequence) for a network modeling of the problem. The second phase partitions the network for manufacturing cell formation. The 0-1 integer programming model and 0-1 quadratic programming model are proposed and network-flow based solution procedures are developed. Finally, the last phase identifies the part families. A 0-1 integer programming model is formulated and the solution of this model is performed through a network approach that allows the identification of a feasible assignment of parts to machine cells satisfying the restriction on part family size. A state-of-the art optimization procedure known as the relaxation algorithm was used for enhancing the computational efficiency of the proposed methodology. The concept of using a circulation network for the cell formation problem is a new approach. The most important advantages of the proposed network methodology in the cell and part family formation is its extremely efficient computational performance. Computational results indicate that the proposed approach is appropriate for solving large-scale industrial problems including up to several hundreds of machines and several thousands of parts in a microcomputer environment.