TABU SEARCH-BASED HEURISTICS FOR CELLULAR MANUFACTURING SYSTEMS IN THE PRESENCE OF ALTERNATIVE PROCESS PLANS

When alternative process plans are considered in cellular manufacturin g systems, there is potential for performing an operation required of a part on alternative machines. Under these circumstances, the cell fo rmation problem of determining the assignment of parts and machines to each manufacturing cell can be viewed as being divided into two phase s. 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 manufactur ing cell should be determined. This research examines the first-phase problem. A realistic formulation of the model is presented when the pr oduct-part mixes are stable over the planning horizon. As the problem is proven NP-hard in the strong sense, two different higher-level heur istics, 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 co nducted to compare the performances of the heuristics. In three differ ent 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 inc orporated in packaged software (LINDO and MPSX/MIP 370) as indicated i n some of the published literature.