Using grasp to solve the component grouping problem

John G. Klincewicz and Arvind Rajan

Naval Research Logistics (NRL), 1994, vol. 41, issue 7, 893-912

Abstract: 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.

Date: 1994
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199412)41:73.0.CO;2-R

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:41:y:1994:i:7:p:893-912

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().