IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v41y1994i7p893-912.html
   My bibliography  Save this article

Using grasp to solve the component grouping problem

Author

Listed:
  • John G. Klincewicz
  • Arvind Rajan

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.

Suggested Citation

  • John G. Klincewicz & Arvind Rajan, 1994. "Using grasp to solve the component grouping problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(7), pages 893-912, December.
    • Handle: RePEc:wly:navres:v:41:y:1994:i:7:p:893-912
    DOI: 10.1002/1520-6750(199412)41:73.0.CO;2-R
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199412)41:73.0.CO;2-R
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199412)41:73.0.CO;2-R?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Venugopal, V. & Narendran, T. T., 1992. "Cell formation in manufacturing systems through simulated annealing: An experimental evaluation," European Journal of Operational Research, Elsevier, vol. 63(3), pages 409-422, December.
    2. Ravi Kumar, K. & Kusiak, Andrew & Vannelli, Anthony, 1986. "Grouping of parts and components in flexible manufacturing systems," European Journal of Operational Research, Elsevier, vol. 24(3), pages 387-397, March.
    3. Mulvey, John M. & Beck, Michael P., 1984. "Solving capacitated clustering problems," European Journal of Operational Research, Elsevier, vol. 18(3), pages 339-348, December.
    4. Reza H. Ahmadi & Christopher S. Tang, 1991. "An Operation Partitioning Problem for Automated Assembly System Design," Operations Research, INFORMS, vol. 39(5), pages 824-835, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ahmadi, Reza H. & Matsuo, Hirofumi, 2000. "A mini-line approach for pull production," European Journal of Operational Research, Elsevier, vol. 125(2), pages 340-358, September.
    2. Gary Klein & Jay E. Aronson, 1991. "Optimal clustering: A model and method," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(3), pages 447-461, June.
    3. Boutsinas, Basilis, 2013. "Machine-part cell formation using biclustering," European Journal of Operational Research, Elsevier, vol. 230(3), pages 563-572.
    4. Lu Han & Dachuan Xu & Donglei Du & Dongmei Zhang, 0. "An approximation algorithm for the uniform capacitated k-means problem," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-12.
    5. O. Mahesh & G. Srinivasan, 2006. "Multi-objectives for incremental cell formation problem," Annals of Operations Research, Springer, vol. 143(1), pages 157-170, March.
    6. A I Jarrah & J F Bard, 2011. "Pickup and delivery network segmentation using contiguous geographic clustering," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(10), pages 1827-1843, October.
    7. Mohamed, Zubair M. & Kumar, Ashok & Motwani, Jaideep, 1999. "An improved part grouping model for minimizing makespan in FMS," European Journal of Operational Research, Elsevier, vol. 116(1), pages 171-182, July.
    8. Belarmino Adenso-Díaz & Mónica González & Emérita García, 1998. "A Hierarchical Approach to Managing Dairy Routing," Interfaces, INFORMS, vol. 28(2), pages 21-31, April.
    9. Scheuerer, Stephan & Wendolsky, Rolf, 2006. "A scatter search heuristic for the capacitated clustering problem," European Journal of Operational Research, Elsevier, vol. 169(2), pages 533-547, March.
    10. D'Alfonso, Thomas H. & Ventura, Jose A., 1995. "Assignment of tools to machines in a flexible manufacturing system," European Journal of Operational Research, Elsevier, vol. 81(1), pages 115-133, February.
    11. Lau, Kin-nam & Leung, Pui-lam & Tse, Ka-kit, 1999. "A mathematical programming approach to clusterwise regression model and its extensions," European Journal of Operational Research, Elsevier, vol. 116(3), pages 640-652, August.
    12. Zhou, Lin & Zhen, Lu & Baldacci, Roberto & Boschetti, Marco & Dai, Ying & Lim, Andrew, 2021. "A Heuristic Algorithm for solving a large-scale real-world territory design problem," Omega, Elsevier, vol. 103(C).
    13. Wooseung Jang & Huay H. Lim & Thomas J. Crowe & Gail Raskin & Thomas E. Perkins, 2006. "The Missouri Lottery Optimizes Its Scheduling and Routing to Improve Efficiency and Balance," Interfaces, INFORMS, vol. 36(4), pages 302-313, August.
    14. Mai, Feng & Fry, Michael J. & Ohlmann, Jeffrey W., 2018. "Model-based capacitated clustering with posterior regularization," European Journal of Operational Research, Elsevier, vol. 271(2), pages 594-605.
    15. Stawowy, Adam, 2006. "Evolutionary strategy for manufacturing cell design," Omega, Elsevier, vol. 34(1), pages 1-18, January.
    16. Lu Han & Dachuan Xu & Donglei Du & Dongmei Zhang, 2022. "An approximation algorithm for the uniform capacitated k-means problem," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1812-1823, October.
    17. Logendran, Rasaratnam & Talkington, Diane, 1997. "Analysis of cellular and functional manufacturing systems in the presence of machine breakdown," International Journal of Production Economics, Elsevier, vol. 53(3), pages 239-256, December.
    18. Zheng Wang & Wei Xu & Xiangpei Hu & Yong Wang, 2022. "Inventory allocation to robotic mobile-rack and picker-to-part warehouses at minimum order-splitting and replenishment costs," Annals of Operations Research, Springer, vol. 316(1), pages 467-491, September.
    19. I H Osman & S Ahmadi, 2007. "Guided construction search metaheuristics for the capacitated p-median problem with single source constraint," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(1), pages 100-114, January.
    20. Ah-Pine, Julien, 2022. "Learning doubly stochastic and nearly idempotent affinity matrix for graph-based clustering," European Journal of Operational Research, Elsevier, vol. 299(3), pages 1069-1078.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:41:y:1994:i:7:p:893-912. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.