Premium
Using grasp to solve the component grouping problem
Author(s) -
Klincewicz John G.,
Rajan Arvind
Publication year - 1994
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199412)41:7<893::aid-nav3220410704>3.0.co;2-r
Subject(s) - grasp , heuristics , component (thermodynamics) , heuristic , computer science , mathematical optimization , greedy randomized adaptive search procedure , local search (optimization) , greedy algorithm , probabilistic logic , combinatorial optimization , set (abstract data type) , algorithm , mathematics , artificial intelligence , physics , thermodynamics , programming language
Component grouping problems, a type of set‐partitioning problem, arise in a number of different manufacturing and material logistics application 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 components, 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 cells. 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 points. The starting points are determined by a greedy procedure with a probabilistic aspect. The best result is then kept as the solution. Computational experiments on problems based on data from actual manufacturing processes indicate that these GRASP methods outperform, both in speed and in solution quality, an earlier, network‐flow‐based heuristic. We also describe techniques for generating lower bounds for the component grouping problem, based on the combinatorial structure of a problem instance. The lower bounds for our real‐world test problems averaged within 7%‐8% of the heuristic solutions. Similar results are obtained for larger, randomly generated problems. © 1994 John Wiley & Sons. Inc.