USING GRASP TO SOLVE THE COMPONENT GROUPING PROBLEM

Component grouping problems, a type of set-partitioning problem, arise in a number of different manufacturing and material logistics applica tion areas. For example, in circuit board assembly, robotic work cells can be used to insert components onto a number of different types of circuit boards. Each type of circuit board requires particular compone nts, with some components appearing on more than one type. The problem is to decide which components should be assigned to each work cell in order to minimize the number of visits by circuit boards to work cell s. We describe two new heuristics for this problem, based on so-called greedy random adaptive search procedures (GRASP). With GRASP, a local search technique is replicated many times with different starting poi nts. The starting points are determined by a greedy procedure with a p robabilistic aspect. The best result is then kept as the solution. Com putational experiments on problems based on data from actual manufactu ring processes indicate that these GRASP methods outperform, both in s peed and in solution quality, an earlier, network-flow-based heuristic . We also describe techniques for generating lower bounds for the comp onent grouping problem, based on the combinatorial structure of a prob lem instance. The lower bounds for our real-world test problems averag ed within 7%-8% of the heuristic solutions. Similar results are obtain ed for larger, randomly generated problems. (C) 1994 John Wiley & Sons , Inc.