When alternative process plans are considered in cellular manufacturing systems, there is potential for performing an operation required of a part on alternative machines. Under these circumstances, the cell formation problem of determining the assignment of parts and machines to each manufacturing cell can be viewed as being divided into two phases. The first phase deals with the problem of determining the number of machines of each type and a unique process plan for each part. In the second phase, the assignment of parts and machines to each manufacturing cell should be determined. This research examines the first-phase problem. A realistic formulation of the model is presented when the product-part mixes are stable over the planning horizon. As the problem is proven NP-hard in the strong sense, two different higher-level heuristics, based upon a concept known as tabu search, are presented. Each heuristic is further extended into two methods: 1 and 2. An extensive statistical analysis, based upon randomized block design, has been conducted to compare the performances of the heuristics. In three different problem structures attempted with a block size of 10, the results obtained show the superior performance of heuristic 2 over 1 with both methods. This further substantiates the fact that there is clearly a need for efficient heuristics to solve problems in manufacturing cell design that have any practical significance and one cannot rely on an exhaustive search algorithm such as the branch-and-bound technique incorporated in packaged software (LINDO and MPSX/M1P 370) as indicated in some of the published literature.