DOI: 10.1115/1.1778185. Tree-Based Dependency Analysis in Decomposition and Re-decomposition of Complex Design Problems

Tree-Based Dependency Analysis in Decomposition and Re-decomposition of Complex Design Problems

10.1115/1.1778185

Crossref journal-article

ASME International

Journal of Mechanical Design (33)

Abstract

We have developed a formal method for decomposition of complex design problems in two phases: dependency analysis and matrix partitioning. Of the most distinct characteristic in this method is the support of cost-effective re-decomposition (as is often required in decomposition solution synthesis), where dependency analysis serves as a platform for the enabling of re-decomposition. Yet, this requires that the result of the dependency analysis be robust and thus reusable for re-decomposition. In this paper, after revealing the deficiency in the current practice of dependency analysis, we present an enhanced dependency analysis method that is built on ordinary tree structure (instead of binary tree structure). This new approach, which is more systematic, ensures robust dependency analysis, whose result is insensitive to the arrangement of a tree structure in tree-based dependency analysis. A complete set of tree-based algorithms is also provided, along with their applications to two design examples

Bibliography

Chen, L., Ding, Z., & Li, S. (2005). Tree-Based Dependency Analysis in Decomposition and Re-decomposition of Complex Design Problems. Journal of Mechanical Design, 127(1), 12â23.

Authors 3

Li Chen (first)
Zhendong Ding (additional)
Simon Li (additional)

References 17 Referenced 17

King, J. R. , 1980, “Machine-Component Grouping Formation in Group Technology,” International Journal of Management Science, 8(2), pp. 193–199. (10.1016/0305-0483(80)90023-7)
Chang, T. C., Wysk, R. A., and Wang, H. P., 1985, Computer-aided Manufacturing, Prentice Hall, Englewood Cliffs, N.J.
Kusiak, A., and Cheng, C. H., 1990, “A Branch-and-Bound Algorithm for Solving Group Technology Problems,” Annals of Operational Research, 26, pp. 415–431. (10.1007/BF03543078)
Kusiak, A., and Wang, J., 1993, “Decomposition of Design Process,” ASME J. Mech. Des., 115, pp. 687–695. (10.1115/1.2919255)
Michelena, N., and Papalambros, P. Y., 1995, “A Network Reliability Approach to Optimal Decomposition of Design Problems,” ASME J. Mech. Des., 117(3), pp. 433–440. (10.1115/1.2826697)
Michelena, N. F., and Papalambros, P. Y., 1997, “A Hypergraph Framework for Optimal Model-Based Decomposition of Design Problems,” Computational Optimization and Applications, 8(2), pp. 173–196. (10.1023/A:1008673321406)
Krishnamachari, R. S., and Papalambros, P. Y., 1997, “Optimal Hierarchical Decomposition Synthesis Using Integer Programming,” ASME J. Mech. Des., 119(4), pp. 440–447. (10.1115/1.2826388)
Chen, L., Ding, Z., and Li, S., 2003, “A Formal Two-Phase Method for Decomposition of Complex Design Problems,” ASME J. Mech. Des., in press.
Kusiak, A., and Wang, J., 1995, “Dependency Analysis in Constraint Negotiation,” IEEE Trans. Syst. Man Cybern., 25(9), pp. 1301–1313. (10.1109/21.400508)
Kannapan, S. M., and Marshek, K. M., 1993, “An Approach to Parametric Machine Design and Negotiation in Concurrent Engineering,” Concurrent Engineering: Automation, Tools and Techniques, A. Kusiak, ed., John-Wiley, New York, pp. 509–533.
Wang, K. L., and Jin, Y., 1999, “Modeling Dependencies in Engineering Design,” CD-ROM Proceedings of ASME Design Engineering Technical Conferences, DETC99/DTM-8778, Las Vegas, Nevada, Sept. 12–15.
Park, H., and Cutkosky, M. R., 1999, “Framework for Modeling Dependencies in Collaborative Engineering Processes,” Research in Engineering Design, 11, pp. 84–102. (10.1007/PL00003885)
Chen, L., Ding, Z., and Li, S., 2003b, “Extended Hierarchical Cluster Analysis for the Decomposition of Complex Design Problems,” CD-ROM Proceedings of ASME Design Engineering Technical Conferences, DETC2003/DAC-48728, Chicago, Illinois, Sept. 2–6. (10.1115/DETC2003/DAC-48728)
Kaufman, L., and Rousseeuw, P. J., 1990, Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, New York. (10.1002/9780470316801)
Romesburg, H. C., 1990, Cluster Analysis for Researchers, Robert E. Krieger, Malabar.
Michelena, N., and Papalambros, P. Y., 1995b, “Optimal Model-Based Decomposition of Powertrain System Design,” ASME J. Mech. Des., 117(4), pp. 499–505. (10.1115/1.2826710)
Krishnamachari, R. S., 1996, “A Decomposition Synthesis Methodology for Optimal Systems Design,” PhD Thesis, Department of Mechanical Engineering and Applied Mechanics, University of Michigan, Ann Arbor, MI.

Dates

Type	When
Created	20 years, 5 months ago (March 2, 2005, 6:28 p.m.)
Deposited	5 years, 4 months ago (April 5, 2020, 10:27 p.m.)
Indexed	3 years ago (Aug. 8, 2022, 8:30 a.m.)
Issued	20 years, 7 months ago (Jan. 1, 2005)
Published	20 years, 7 months ago (Jan. 1, 2005)
Published Online	20 years, 5 months ago (March 2, 2005)
Published Print	20 years, 7 months ago (Jan. 1, 2005)

Funders 0

None

JSON

{
  "indexed": {
    "date-parts": [
      [
        2022,
        8,
        8
      ]
    ],
    "date-time": "2022-08-08T12:30:51Z",
    "timestamp": 1659961851941
  },
  "reference-count": 17,
  "publisher": "ASME International",
  "issue": "1",
  "content-domain": {
    "domain": [
      "asmedigitalcollection.asme.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        2005,
        1,
        1
      ]
    ]
  },
  "abstract": "<jats:p>We have developed a formal method for decomposition of complex design problems in two phases: dependency analysis and matrix partitioning. Of the most distinct characteristic in this method is the support of cost-effective re-decomposition (as is often required in decomposition solution synthesis), where dependency analysis serves as a platform for the enabling of re-decomposition. Yet, this requires that the result of the dependency analysis be robust and thus reusable for re-decomposition. In this paper, after revealing the deficiency in the current practice of dependency analysis, we present an enhanced dependency analysis method that is built on ordinary tree structure (instead of binary tree structure). This new approach, which is more systematic, ensures robust dependency analysis, whose result is insensitive to the arrangement of a tree structure in tree-based dependency analysis. A complete set of tree-based algorithms is also provided, along with their applications to two design examples</jats:p>",
  "DOI": "10.1115/1.1778185",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2005,
        3,
        2
      ]
    ],
    "date-time": "2005-03-02T23:28:30Z",
    "timestamp": 1109806110000
  },
  "page": "12-23",
  "update-policy": "http://dx.doi.org/10.1115/crossmarkpolicy-asme",
  "source": "Crossref",
  "is-referenced-by-count": 17,
  "title": "Tree-Based Dependency Analysis in Decomposition and Re-decomposition of Complex Design Problems",
  "prefix": "10.1115",
  "volume": "127",
  "author": [
    {
      "given": "Li",
      "family": "Chen",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Design and Manufacturing Integration Laboratory, Department of Mechanical and Industrial Engineering, University of Toronto, 5 King\u2019s College Road, Toronto, ON, Canada M5S 3G8"
        }
      ]
    },
    {
      "given": "Zhendong",
      "family": "Ding",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Design and Manufacturing Integration Laboratory, Department of Mechanical and Industrial Engineering, University of Toronto, 5 King\u2019s College Road, Toronto, ON, Canada M5S 3G8"
        }
      ]
    },
    {
      "given": "Simon",
      "family": "Li",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Design and Manufacturing Integration Laboratory, Department of Mechanical and Industrial Engineering, University of Toronto, 5 King\u2019s College Road, Toronto, ON, Canada M5S 3G8"
        }
      ]
    }
  ],
  "member": "33",
  "published-online": {
    "date-parts": [
      [
        2005,
        3,
        2
      ]
    ]
  },
  "reference": [
    {
      "key": "2019100523035412700_r1",
      "doi-asserted-by": "crossref",
      "unstructured": "King, J. R. , 1980, \u201cMachine-Component Grouping Formation in Group Technology,\u201d International Journal of Management Science, 8(2), pp. 193\u2013199.",
      "DOI": "10.1016/0305-0483(80)90023-7"
    },
    {
      "key": "2019100523035412700_r2",
      "unstructured": "Chang, T. C., Wysk, R. A., and Wang, H. P., 1985, Computer-aided Manufacturing, Prentice Hall, Englewood Cliffs, N.J."
    },
    {
      "key": "2019100523035412700_r3",
      "doi-asserted-by": "crossref",
      "unstructured": "Kusiak, A., and Cheng, C. H., 1990, \u201cA Branch-and-Bound Algorithm for Solving Group Technology Problems,\u201d Annals of Operational Research, 26, pp. 415\u2013431.",
      "DOI": "10.1007/BF03543078"
    },
    {
      "key": "2019100523035412700_r4",
      "doi-asserted-by": "crossref",
      "unstructured": "Kusiak, A., and Wang, J., 1993, \u201cDecomposition of Design Process,\u201d ASME J. Mech. Des., 115, pp. 687\u2013695.",
      "DOI": "10.1115/1.2919255"
    },
    {
      "key": "2019100523035412700_r5",
      "doi-asserted-by": "crossref",
      "unstructured": "Michelena, N., and Papalambros, P. Y., 1995, \u201cA Network Reliability Approach to Optimal Decomposition of Design Problems,\u201d ASME J. Mech. Des., 117(3), pp. 433\u2013440.",
      "DOI": "10.1115/1.2826697"
    },
    {
      "key": "2019100523035412700_r6",
      "doi-asserted-by": "crossref",
      "unstructured": "Michelena, N. F., and Papalambros, P. Y., 1997, \u201cA Hypergraph Framework for Optimal Model-Based Decomposition of Design Problems,\u201d Computational Optimization and Applications, 8(2), pp. 173\u2013196.",
      "DOI": "10.1023/A:1008673321406"
    },
    {
      "key": "2019100523035412700_r7",
      "doi-asserted-by": "crossref",
      "unstructured": "Krishnamachari, R. S., and Papalambros, P. Y., 1997, \u201cOptimal Hierarchical Decomposition Synthesis Using Integer Programming,\u201d ASME J. Mech. Des., 119(4), pp. 440\u2013447.",
      "DOI": "10.1115/1.2826388"
    },
    {
      "key": "2019100523035412700_r8",
      "unstructured": "Chen, L., Ding, Z., and Li, S., 2003, \u201cA Formal Two-Phase Method for Decomposition of Complex Design Problems,\u201d ASME J. Mech. Des., in press."
    },
    {
      "key": "2019100523035412700_r9",
      "doi-asserted-by": "crossref",
      "unstructured": "Kusiak, A., and Wang, J., 1995, \u201cDependency Analysis in Constraint Negotiation,\u201d IEEE Trans. Syst. Man Cybern., 25(9), pp. 1301\u20131313.",
      "DOI": "10.1109/21.400508"
    },
    {
      "key": "2019100523035412700_r10",
      "unstructured": "Kannapan, S. M., and Marshek, K. M., 1993, \u201cAn Approach to Parametric Machine Design and Negotiation in Concurrent Engineering,\u201d Concurrent Engineering: Automation, Tools and Techniques, A. Kusiak, ed., John-Wiley, New York, pp. 509\u2013533."
    },
    {
      "key": "2019100523035412700_r11",
      "unstructured": "Wang, K. L., and Jin, Y., 1999, \u201cModeling Dependencies in Engineering Design,\u201d CD-ROM Proceedings of ASME Design Engineering Technical Conferences, DETC99/DTM-8778, Las Vegas, Nevada, Sept. 12\u201315."
    },
    {
      "key": "2019100523035412700_r12",
      "doi-asserted-by": "crossref",
      "unstructured": "Park, H., and Cutkosky, M. R., 1999, \u201cFramework for Modeling Dependencies in Collaborative Engineering Processes,\u201d Research in Engineering Design, 11, pp. 84\u2013102.",
      "DOI": "10.1007/PL00003885"
    },
    {
      "key": "2019100523035412700_r13",
      "doi-asserted-by": "crossref",
      "unstructured": "Chen, L., Ding, Z., and Li, S., 2003b, \u201cExtended Hierarchical Cluster Analysis for the Decomposition of Complex Design Problems,\u201d CD-ROM Proceedings of ASME Design Engineering Technical Conferences, DETC2003/DAC-48728, Chicago, Illinois, Sept. 2\u20136.",
      "DOI": "10.1115/DETC2003/DAC-48728"
    },
    {
      "key": "2019100523035412700_r14",
      "doi-asserted-by": "crossref",
      "unstructured": "Kaufman, L., and Rousseeuw, P. J., 1990, Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, New York.",
      "DOI": "10.1002/9780470316801"
    },
    {
      "key": "2019100523035412700_r15",
      "unstructured": "Romesburg, H. C., 1990, Cluster Analysis for Researchers, Robert E. Krieger, Malabar."
    },
    {
      "key": "2019100523035412700_r16",
      "doi-asserted-by": "crossref",
      "unstructured": "Michelena, N., and Papalambros, P. Y., 1995b, \u201cOptimal Model-Based Decomposition of Powertrain System Design,\u201d ASME J. Mech. Des., 117(4), pp. 499\u2013505.",
      "DOI": "10.1115/1.2826710"
    },
    {
      "key": "2019100523035412700_r17",
      "unstructured": "Krishnamachari, R. S., 1996, \u201cA Decomposition Synthesis Methodology for Optimal Systems Design,\u201d PhD Thesis, Department of Mechanical Engineering and Applied Mechanics, University of Michigan, Ann Arbor, MI."
    }
  ],
  "container-title": "Journal of Mechanical Design",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "http://asmedigitalcollection.asme.org/mechanicaldesign/article-pdf/127/1/12/5684847/12_1.pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "syndication"
    },
    {
      "URL": "http://asmedigitalcollection.asme.org/mechanicaldesign/article-pdf/127/1/12/5684847/12_1.pdf",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2020,
        4,
        6
      ]
    ],
    "date-time": "2020-04-06T02:27:43Z",
    "timestamp": 1586140063000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://asmedigitalcollection.asme.org/mechanicaldesign/article/127/1/12/460116/TreeBased-Dependency-Analysis-in-Decomposition-and"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2005,
        1,
        1
      ]
    ]
  },
  "references-count": 17,
  "journal-issue": {
    "issue": "1",
    "published-print": {
      "date-parts": [
        [
          2005,
          1,
          1
        ]
      ]
    }
  },
  "URL": "http://dx.doi.org/10.1115/1.1778185",
  "relation": {},
  "ISSN": [
    "1050-0472",
    "1528-9001"
  ],
  "subject": [],
  "published": {
    "date-parts": [
      [
        2005,
        1,
        1
      ]
    ]
  }
}