IDEAS home Printed from https://ideas.repec.org/a/spr/comgts/v9y2012i3p323-338.html
   My bibliography  Save this article

An exact model for cell formation in group technology

Author

Listed:
  • Dmitry Krushinsky
  • Boris Goldengorin

Abstract

Despite the long history of the cell formation problem (CF) and availability of dozens of approaches, very few of them explicitly optimize the objective of cell formation. These scarce approaches usually lead to intractable formulations that can be solved only heuristically for practical instances. In contrast, we show that CF can be explicitly modelled via the minimum multicut problem and solved to optimality in practice (for moderately sized instances). We consider several real-world constraints that can be included into the proposed formulations and provide experimental results with real manufacturing data. Copyright The Author(s) 2012

Suggested Citation

  • Dmitry Krushinsky & Boris Goldengorin, 2012. "An exact model for cell formation in group technology," Computational Management Science, Springer, vol. 9(3), pages 323-338, August.
  • Handle: RePEc:spr:comgts:v:9:y:2012:i:3:p:323-338
    DOI: 10.1007/s10287-012-0146-2
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10287-012-0146-2
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s10287-012-0146-2?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Olivier Goldschmidt & Dorit S. Hochbaum, 1994. "A Polynomial Algorithm for the k-cut Problem for Fixed k," Mathematics of Operations Research, INFORMS, vol. 19(1), pages 24-37, February.
    2. Ng, Shu Ming, 1993. "Worst-case analysis of an algorithm for cellular manufacturing," European Journal of Operational Research, Elsevier, vol. 69(3), pages 384-398, September.
    3. Chen, Ja-Shen & Heragu, Sunderesh S., 1999. "Stepwise decomposition approaches for large scale cell formation problems," European Journal of Operational Research, Elsevier, vol. 113(1), pages 64-79, February.
    4. Yin, Yong & Yasuda, Kazuhiko, 2006. "Similarity coefficient methods applied to the cell formation problem: A taxonomy and review," International Journal of Production Economics, Elsevier, vol. 101(2), pages 329-352, June.
    5. Vila Goncalves Filho, Eduardo & Jose Tiberti, Alexandre, 2006. "A group genetic algorithm for the machine cell formation problem," International Journal of Production Economics, Elsevier, vol. 102(1), pages 1-21, July.
    6. Ravi, R. & Sinha, Amitabh, 2008. "Approximating k-cuts using network strength as a Lagrangean relaxation," European Journal of Operational Research, Elsevier, vol. 186(1), pages 77-90, April.
    7. Yang, Miin-Shen & Yang, Jenn-Hwai, 2008. "Machine-part cell formation in group technology using a modified ART1 method," European Journal of Operational Research, Elsevier, vol. 188(1), pages 140-152, July.
    8. R Bhatnagar & V Saddikuti, 2010. "Models for cellular manufacturing systems design: matching processing requirements and operator capabilities," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 827-839, May.
    9. William T. McCormick & Paul J. Schweitzer & Thomas W. White, 1972. "Problem Decomposition and Data Reorganization by a Clustering Technique," Operations Research, INFORMS, vol. 20(5), pages 993-1009, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Mohd Fahmi Bin Mad Ali & Mohd Khairol Anuar Bin Mohd Ariffin & Aidin Delgoshaei & Faizal Bin Mustapha & Eris Elianddy Bin Supeni, 2023. "A Comprehensive 3-Phase Framework for Determining the Customer’s Product Usage in a Food Supply Chain," Mathematics, MDPI, vol. 11(5), pages 1-20, February.
    2. Mohd Fahmi Bin Mad Ali & Mohd Khairol Anuar Bin Mohd Ariffin & Faizal Bin Mustapha & Eris Elianddy Bin Supeni, 2021. "An Unsupervised Machine Learning-Based Framework for Transferring Local Factories into Supply Chain Networks," Mathematics, MDPI, vol. 9(23), pages 1-31, December.
    3. Alena Otto & Erwin Pesch, 2017. "Operation of shunting yards: train-to-yard assignment problem," Journal of Business Economics, Springer, vol. 87(4), pages 465-486, May.

    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. Wu, Tai-Hsi & Chung, Shu-Hsing & Chang, Chin-Chih, 2010. "A water flow-like algorithm for manufacturing cell formation problems," European Journal of Operational Research, Elsevier, vol. 205(2), pages 346-360, September.
    2. Boris Goldengorin & Dmitry Krushinsky & Jannes Slomp, 2012. "Flexible PMP Approach for Large-Size Cell Formation," Operations Research, INFORMS, vol. 60(5), pages 1157-1166, October.
    3. Wu, Tai-Hsi & Chang, Chin-Chih & Yeh, Jinn-Yi, 2009. "A hybrid heuristic algorithm adopting both Boltzmann function and mutation operator for manufacturing cell formation problems," International Journal of Production Economics, Elsevier, vol. 120(2), pages 669-688, August.
    4. Vakharia, Asoo J. & Mahajan, Jayashree, 2000. "Clustering of objects and attributes for manufacturing and marketing applications," European Journal of Operational Research, Elsevier, vol. 123(3), pages 640-651, June.
    5. Papaioannou, Grammatoula & Wilson, John M., 2010. "The evolution of cell formation problem methodologies based on recent studies (1997-2008): Review and directions for future research," European Journal of Operational Research, Elsevier, vol. 206(3), pages 509-521, November.
    6. Berna H. Ulutas, 2019. "An immune system based algorithm for cell formation problem," Journal of Intelligent Manufacturing, Springer, vol. 30(8), pages 2835-2852, December.
    7. Hahsler, Michael, 2017. "An experimental comparison of seriation methods for one-mode two-way data," European Journal of Operational Research, Elsevier, vol. 257(1), pages 133-143.
    8. Angra, Surjit & Sehgal, Rakesh & Samsudeen Noori, Z., 2008. "Cellular manufacturing--A time-based analysis to the layout problem," International Journal of Production Economics, Elsevier, vol. 112(1), pages 427-438, March.
    9. Berardi, Victor L. & Zhang, Guoqiang & Felix Offodile, O., 1999. "A mathematical programming approach to evaluating alternative machine clusters in cellular manufacturing," International Journal of Production Economics, Elsevier, vol. 58(3), pages 253-264, January.
    10. Mohd Fahmi Bin Mad Ali & Mohd Khairol Anuar Bin Mohd Ariffin & Aidin Delgoshaei & Faizal Bin Mustapha & Eris Elianddy Bin Supeni, 2023. "A Comprehensive 3-Phase Framework for Determining the Customer’s Product Usage in a Food Supply Chain," Mathematics, MDPI, vol. 11(5), pages 1-20, February.
    11. Ponce, Diego & Puerto, Justo & Temprano, Francisco, 2024. "Mixed-integer linear programming formulations and column generation algorithms for the Minimum Normalized Cuts problem on networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 519-538.
    12. Geert Soete & Wayne DeSarbo & George Furnas & J. Carroll, 1984. "The estimation of ultrametric and path length trees from rectangular proximity data," Psychometrika, Springer;The Psychometric Society, vol. 49(3), pages 289-310, September.
    13. Rym Ben Bachouch & Jihène Tounsi & Chouari Borhen, 2020. "Home health care scheduling activities," Post-Print hal-03229580, HAL.
    14. Mohd Fahmi Bin Mad Ali & Mohd Khairol Anuar Bin Mohd Ariffin & Faizal Bin Mustapha & Eris Elianddy Bin Supeni, 2021. "An Unsupervised Machine Learning-Based Framework for Transferring Local Factories into Supply Chain Networks," Mathematics, MDPI, vol. 9(23), pages 1-31, December.
    15. Aalaei, Amin & Davoudpour, Hamid, 2017. "A robust optimization model for cellular manufacturing system into supply chain management," International Journal of Production Economics, Elsevier, vol. 183(PC), pages 667-679.
    16. Yang, Miin-Shen & Yang, Jenn-Hwai, 2008. "Machine-part cell formation in group technology using a modified ART1 method," European Journal of Operational Research, Elsevier, vol. 188(1), pages 140-152, July.
    17. Mark Velednitsky & Dorit S. Hochbaum, 0. "Isolation branching: a branch and bound algorithm for the k-terminal cut problem," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-21.
    18. Stawowy, Adam, 2006. "Evolutionary strategy for manufacturing cell design," Omega, Elsevier, vol. 34(1), pages 1-18, January.
    19. Zamani, Reza & Lau, Sim Kim, 2010. "Embedding learning capability in Lagrangean relaxation: An application to the travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 201(1), pages 82-88, February.
    20. Tatiana Zaslavskaia & Il'Ia Muchnik, 1975. "A linguistic method for the classification of multidimensional social objects," Quality & Quantity: International Journal of Methodology, Springer, vol. 9(3), pages 203-227, September.

    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:spr:comgts:v:9:y:2012:i:3:p:323-338. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.