Date of Award


Degree Type


Degree Name



Industrial and Manufacturing Systems Engineering


Engineering, Industrial.




The objectives of this dissertation are to develop methodologies to solve large instances of the following cell formation problems: (1) the problem of allocating machines to part families, (2) the machine-part grouping problem, and (3) the problem of allocating new parts to existing groups. The problem of allocating machines to part families is formulated as 0-1 integer programming models (Model 1 and Model 2). Two approaches to the machine-part grouping problem are presented. The first approach involves the machine group formation problem (Model 3) first and then considers the problem of allocating parts to machine groups (Model 4). Each of these problems is formulated as a 0-1 linear integer programming problem. The second approach is concerned with simultaneous grouping of parts and machines. This problem is formulated as 0-1 non-linear integer programming models (Model 5 and Model 6). These models consider machine and material handling costs, restrictions on the number and size of the groups and the number of machines available in each type. An improved formulation of the single function classification model (Model 7) is suggested to develop partallocation schemes to allocate new parts to the existing part families. Lagrangean relaxation based methods are used to solve the models presented in this dissertation. Alternate relaxations have been compared in terms of the computational time and the quality of bounds obtained. In Models 1 and 2, relaxing the machine group size constraint (Relaxation 2) is found to perform better than relaxing the machine availability constraint. Both the relaxations are relatively insensitive to the initial estimate of the objective function, if underestimated. In Model 4, relaxing the part group size constraint (Relaxation 2) is found to perform better than relaxing the part allocation constraint and both the relaxations are relatively insensitive to the initial estimate, if underestimated. In all the models (Models 1, 2, 3, and 4), the problem structure does not have any significant effect on the computational time and the bounds obtained. An approximate iterative method to solve the simultaneous machine-part grouping models (Models 5 and 6) has been developed and tested using randomly generated problems. The procedure appears to converge almost to the same final solution irrespective of the initial parts allocation chosen. The usefulness of the models to solve large size problems is illustrated using randomly generated problems. An extension of Model 5 to form machine-part groups in the presence of alternate process plans for parts is also presented. Source: Dissertation Abstracts International, Volume: 50-08, Section: B, page: 3637. Thesis (Ph.D.)--University of Windsor (Canada), 1989.