A volume and material handling cost based heuristic for designing cellular manufacturing cells

One of the major problems in a group technology or cellular manufacturing environment is the formation of part groups and machine cells. Because of the combinatorial nature of the cell formation problem, it is difficult to solve the problem optimally. Most of the procedures related to cell design in cellular manufacturing operate on the part-machine incidence matrix in an attempt to identify block diagonality. If complete block diagonality does not exist, the decision about cell configuration is left to the subjective judgement of the designer. These procedures are also generally based on part routing only, and do not consider part volume and material handling costs. In this paper the authors develop an integer programming model, as well as a heuristic to effectively assign machines to cells. In these procedures they consider component volumes, costs related to movement of components between and within cells, and penalty for not using all machines in a cell visited by a component. Since the integer programming formulation becomes large even for small problems, an efficient heuristic is developed to solve larger problems. The heuristic solutions to 180 randomly generated small problems were compared against the optimal solutions obtained by the integer programming model. The heuristic has been found to identify optimal solutions in all 180 cases. This heuristic is also compared to several well known algorithms on 900 larger test problems. These problems were generated to cover a wide range of environmental situations such as varying levels of block diagonality in the part-machine incidence matrix, and diversity in the component volumes and material handling costs. In 99% of the problems the present heuristic generated solutions which are better or as good as the best solution obtained by other algorithms. Further, in situations where complete block diagonality in the part-machine incidence matrix did not exist, the heuristic produced even better results. Since the maximum number of iterations required in the present heuristic is the number of machines in the problem, the heuristic is computationally efficient.