Manufacturing cell formation using an improved P-median model

The p-median model objective function is modified for the cell formation problem to minimize the variability between parts in a group by considering part similarity to all other parts in the group instead of similarity to an arbitrary median. The heuristic vertex substitution method for solution of the part grouping problem is adapted for this objective function and then modified to provide improved starting points. The theoretical lower bound for the heuristic is developed and shown to be valid for all solutions. Worst case run time is shown to be O(n2) or O(n3) for distance matrix or network inputs respectively. Tests on published problems show that the proposed p-median model method provides as good or better objective function value (OFV) than the OFV of a p-median model in which parts are grouped to an arbitrary median. Likewise the new p-median model is shown, for these published problems, to give as good or better OFV than the algorithms reported by the original authors of the problem. The test problems suggest that other measures of solution quality such as bottlenecks and duplicate machines in addition to OFV become important measures of solution quality for dense problems.