基于路徑搜索的產品設計過程建模

胡從林，容芷君，陳奎生，但斌斌

（武漢科技大學 機械自動化學院，湖北 武漢 430081）

0 引言

隨著全球制造業(yè)市場的快速發(fā)展，企業(yè)面臨著越來越激烈的市場競爭。為了以最快的速度、最低的成本提供質量最優(yōu)的產品來快速響應市場，研究縮短產品設計周期和優(yōu)化產品設計過程的理論與方法具有十分重要的意義。目前，設計過程的優(yōu)化建模 方 法 有 關 鍵 路 徑 法 （Critical Path Method，CPM）、有向圖法、設計結構矩陣（Design Structure Matrix，DSM）法、甘特圖（GANTT）、計算機輔助制造定義方法（Integrated Computer aided manufacturing DEFinition method，IDEF）系列建模方法和Petri網建模方法等［1－2］，根據這些方法，可以從不同角度對設計過程進行建模。其中，CPM和甘特圖對設計過程中的業(yè)務運作、項目管理可以有效地建模；IDEF3可以靜態(tài)地描述整個設計過程，但不支持過程的改進和分析；DSM采用耦合、撕裂等規(guī)則對設計過程進行重組優(yōu)化；Petri網和有向圖都是一種面向圖形的建模方法，可以對設計過程進行動態(tài)描述。設計過程由設計要素組成，設計要素包括設計活動、設計任務、設計實體零部件和設計者等，設計要素之間相互關系的表示和分析是設計過程建模方法的主要內容和目標。因此，在設計過程建模中，對設計要素進行層次劃分，得出設計要素之間的相關性和耦合性，從而減少設計過程的迭代次數，是優(yōu)化產品設計過程的重點。國內外學者對產品設計過程建模進行了大量研究。Mike等［3］在產品設計過程中，考慮結構和功能等多域情況，提出基于域匹配矩陣（Domain Mapping Matrices，DMM）和 DSM 的產品設計過程建模方法；Heiko Duin等［4］在協(xié)同設計的基礎上，應用樹圖網絡建立了產品設計動態(tài)模型；Tang等［5］提出基于DSM的產品設計工程變更模型，用以分析設計要素之間的依賴關系，從而降低設計要素變更對設計過程的影響；郭銀章等［6］通過對決策變遷信息庫中的決策信息進行分析，提出基于Petri網的產品設計過程動態(tài)模型。針對分析設計要素之間的關系往往采用DSM方法，該方法最初由美國學者Steward［7］博士于1981年提出，它是一個特定的研究產品設計過程分析規(guī)劃的方法。20世紀后期，Eppinger等［8］提出了數字化的設計結構矩陣（Numeric Design Structure Matrix，NDSM），發(fā)展到現在，DSM已經成為設計過程建模的主要研究方法之一，圍繞該方法也有一些相關軟件與工具，如 Antares DSM，AcclaroDFSS，IntelliJIDEA 等［9］。DSM方法主要根據設計要素之間的聯(lián)系強度對設計要素進行運算，如劃分、撕裂、綁定和聚類等，從而實現對設計過程的結構建模與分析，但設計要素之間的聯(lián)系強度主觀判斷會直接影響DSM的運算結果，導致產品設計過程建模的不確定性和復雜性，同時DSM方法對復雜產品設計過程建模有一定的局限，其針對大規(guī)模復雜問題的計算速度和精度還有待進一步提高。近年來，針對DSM的局限性，研究設計過程復雜性的設計過程建模方法成為新的焦點［10］。

本文應用基于路徑搜索的方法對產品設計任務進行分析，用有向圖描述產品設計任務之間的依賴關系，定義了有向圖和關系矩陣的轉化規(guī)則。通過所提算法對關系矩陣中元素的路徑進行搜索，根據搜索規(guī)則對設計任務進行重組優(yōu)化，建立層次過程模型。以某大型起重機吊臂設計過程為例說明了該方法的可行性。該方法基于圖論和矩陣方法，避免了DSM方法中關系強度的主觀判斷，同時整合了DSM方法中的劃分、撕裂、聚類等運算，計算過程簡潔明確。

1 產品設計過程建模

產品設計過程是一個動態(tài)、復雜的過程，包含多個設計者、設計約束、設計目標、設計活動和過程變量等要素，這些設計過程要素之間的相互關系構建了設計過程的結構［11］。由于設計任務之間的相互關聯(lián)，設計過程建模成為了產品設計過程的難點。在對產品設計過程進行建模時，模型的可信性既取決于模型的種類，又取決于模型的構造過程。復雜產品設計過程由大量設計任務組成，這些設計任務之間存在著錯綜復雜的相互作用關系，要建立設計過程的數學模型，必須首先正確地表示這些設計任務及其相互之間存在的某種關系，即建立系統(tǒng)的過程模型。過程模型具有以下特性［12］：

（1）過程模型是一種設計關系模型，可用有向連接圖表示。

（2）過程模型是一種以定性分析為主的模型，主要用來分析系統(tǒng)各設計任務之間的關系。

（3）過程模型可用矩陣形式來描述，使用定性分析和定量分析相結合的方式。

（4）過程模型的描述形式正處在數學模型和邏輯分析形式之間，它可以處理宏觀、微觀、定性和定量的問題。

在產品設計過程中，各設計任務之間存在著復雜的依賴關系，從任務相互影響的角度來看，有三種類型：

（1）串行 一個任務要在另一個任務完成之后才可以進行，即B任務需要將A任務的輸出作為其輸入，任務之間存在前后依賴關系。

（2）并行 任務之間不存在相互依賴關系，即任務A和任務B是并行關系。

（3）耦合 任務之間存在雙向交互關系，即A任務需要將B任務的輸出作為它的輸入，同時B任務也需要將A任務的輸出作為它的輸入。

這三種關系類型的有向圖及相應的矩陣映射如圖1所示。

2 基于路徑搜索的建模方法

產品設計模型是一種描述設計要素關系的過程模型，要素之間的關系可以用有向圖來描述［13］。有向圖是反映對象之間關系的一種工具，由一系列節(jié)點和連線組成，節(jié)點表示設計要素，連線表示設計要素之間的關系。用V＝｛v1，v2，…，vn｝表示設計要素集合，E ＝ ｛e1，e2，…，em｝表示設計要素之間關系的集合，G＝〈V，E〉表示有向圖。有向圖和矩陣之間存在對應關系，有向圖中的節(jié)點和連線分別對應矩陣中的元素和元素之間的關系。對設計過程進行建模首先需要明確設計任務之間的關系，然后將設計任務之間的關系轉化為設計過程關系矩陣，最后應用數學方法，如圖論、矩陣方法等進行數學計算，從而建立設計過程模型。由產品設計任務之間的關系，可以得到設計關系矩陣

式中：T ＝ ｛t1，t2，…，tn｝為設 計 任 務 集 合；R ＝｛r1，r2，…，rm｝為設計任務關系的集合；rij表示任務i和任務j之間的影響關系，i，j∈ （T1，Tn），Rij∈（r1，rm）。

在關系矩陣R（如圖2）中：＊表示設計任務i對設計任務j存在影響關系；空白表示設計任務i對設計任務j沒有影響；＋表示設計任務i本身的關系。

圖2所示是有向圖和關系矩陣的對應關系。

路徑搜索是關于矩陣間元素相互關系的一種數學建模方法，即根據搜索矩陣中元素的行和列，來判斷環(huán)路和層級關系?；诼窂剿阉鞯漠a品設計過程建模的算法步驟如下：

步驟1 根據元素之間的關系確定關系矩陣R，并明確矩陣的維數。

步驟2 在關系矩陣中進行搜索，找出行全為空的元素設置為起始任務，列全為空的元素設置為終止任務。如果沒有搜索到行全為空或列全為空的元素，則轉步驟5。

步驟3 把行全為空的元素移動到矩陣最上邊，標出為一個任務塊；把列全為空的元素所在的行移動到矩陣最后一行，標出為一個任務塊。

步驟4 刪除任務塊中的元素，返回步驟1。

步驟5 說明元素間存在環(huán)路（耦合塊），從中找到任意一個環(huán)，把環(huán)中的所有元素標志為一個任務塊。環(huán)搜索規(guī)則為：選擇矩陣中任意一個元素（原則上優(yōu)先選擇和其他元素關聯(lián)比較多的元素作為搜索起點），根據元素之間的關系搜索與其有關聯(lián)的任一個元素，直至再次回到起點元素，形成一個環(huán)路。如果沒有找到回路，則再選擇其他元素進行重復搜索，直至找到一個環(huán)路為止。

步驟6 把環(huán)中所有元素合并到一個新元素中。合并規(guī)則為：只要其他元素和環(huán)中至少一個元素存在關聯(lián)，則該元素就和新元素存在關聯(lián)關系。

步驟7 重構過程關聯(lián)矩陣中的元素，返回步驟1。

步驟8 按照標志任務出現時間的先后，確定最終元素層級關系。

該算法的C＋＋語言編程代碼設計如下：

｛

／／初始化數據

Init（）；

／／元素為0，或讀取的初始數據文件錯誤

if（elements＿count＝＝0）

｛

cout＜＜"元素個數為0，或者文件“data.txt”打開錯誤"＜＜endl；

return false；

｝

／／定義找環(huán)函數Find＿Round的返回值Find＿Round＿Return frr＝init；

while（frr?。?no＿find＿should＿terminate）

｛

／／查找空行和空列，空行往上移，先移上去的在上面；空列往后移，先移上去的在后面

Find＿And＿Delete＿Empty＿Row＿And＿Column（）；

／／臨時變量：找環(huán)過程中臨時存儲環(huán)中的元素（元素的原始標記號）

vector〈int〉container＿find＿raw；

／／臨時變量：找環(huán)過程中臨時存儲環(huán)中的元素（元素在新矩陣中的索引）

vector〈int〉container＿find＿current；

／／找環(huán)

frr＝ Find＿Round（container＿find＿raw ，container＿find＿current）；

／／如果找到環(huán)，就將環(huán)元素合并為一個新的元素G，同時計算新元素與矩陣中其他元素的關系

if（frr＝＝find＿round）

Merge＿Round＿Elements（container＿find＿raw ，container＿find＿current）；

｝

／／合并環(huán)

Classify＿Merge（）；

／／找未成環(huán)的元素

Find＿Signal＿Element（）；

／／計算環(huán)、起始元素、未成環(huán)元素的層級關系

Tidy＿Hierarchy（）；

／／輸出結果

Print＿Result（）；

return true；

｝

3 算例

在產品設計過程建模中，產品設計任務之間往往存在著相互影響的關系，找到任務之間的耦合關系和各個任務之間的層次劃分是建模的關鍵。下面以QTZ80H型塔式起重機吊臂為例，說明基于路徑搜索的建模過程。吊臂的設計開發(fā)涉及總體、結構、傳動、分析計算、液壓、電器控制、標準、工藝和試制等多個環(huán)節(jié)，該設計過程包含17個設計任務：①吊臂設計輸入確定；②截面形式設計；③吊臂材料選定；④變幅形式設計；⑤伸縮方式設計；⑥吊臂根部鉸點位置設計；⑦各節(jié)臂臂長（節(jié)數）設計；⑧變幅液壓缸鉸點位置設計；⑨各節(jié)臂截面參數設計；⑩基本臂設計；?伸縮臂設計；?伸縮機構設計；?設計校核；?制造工藝性分析；?樣機試制（實物）；? 設計修改；?設計定型。任務之間的關系如圖3所示。

由起重機吊臂設計任務之間的關系可以得到各設計任務間的關系矩陣R，矩陣中的元素表示設計任務，如圖4所示。

根據路徑搜索算法找出行為空的元素，第一行為空，標記為起始任務；找出列為空的元素，最后一列元素為空，標記為終止任務，如圖5所示。

刪除行為空的元素和列為空的元素，得到剩余元素的重構關系矩陣R1，如圖6所示。

在R1中進行搜索，如果找不到行為空的元素或者列為空的元素，則說明在R1中存在環(huán)（元素之間的耦合關系）。下面進行環(huán)搜索，任意選擇一個元素作為搜索起點，例如選擇元素10作為搜索起點，可以搜索到元素10受到元素12、元素13、元素15、元素16的影響，轉移到下個鄰近元素12；元素12受元素10、元素11、元素13、元素15、元素16的影響，依次向下進行搜索，就轉移到下個鄰近元素13；元素13受元素9、元素10、元素11、元素12、元素15的影響，轉移到元素15；元素15受到元素16影響，轉移到元素16；元素16受元素10、元素11、元素12影響，回到元素10，形成一個回路G1。環(huán)路G1＝（10，12，13，15，16），如圖7所示。

把元素10，12，13，15，16合并成一個新元素環(huán)G1，找出其他元素與環(huán)路G1的關系，更新矩陣R1，得到重構矩陣R2，如圖8所示。

如果進行重新搜索，也不存在行為空元素或者列為空的元素，則說明R2也存在環(huán)，再根據上面環(huán)的搜索規(guī)則進行搜索得到環(huán)路G11，如圖9所示。

由于環(huán)G1在環(huán)G11中，可以把兩個環(huán)合并到一個環(huán)G0中，則環(huán)G0＝（9，10，11，12，13，15，16），重構關系矩陣R3，如圖10所示。

在矩陣中可以搜索到列為空的元素G0，把G0設置為另一個終止任務。同理，重復以上過程，可以得出懸臂梁多個設計任務之間的耦合層級關系，如圖11所示。

根據路徑搜索算法步驟2，首先確定起始任務為元素1、終止任務為元素17，經過行列變換將起始任務元素和終止任務元素分別調整到矩陣的最上方和最下方。然后經過計算可以得到三個環(huán)（耦合任務），分別記為G0＝（9，10，11，12，13，15，16），G1＝（6，7），G2＝（3，2，14），在同一耦合塊中元素彼此影響比較大，故同一耦合塊中的元素屬于一個層級。元素5和元素8在設計時互不影響、是并行關系，放在一個層級。因此，在對起重機吊臂設計過程建模時，可以把其中的17個設計任務分成7個層級關系，每一個層級里的設計任務在設計過程中的優(yōu)先度相同，并且相互影響比較大，可以構成一個設計模塊；層級越是在最上層的設計任務，對以下層級的任務影響越大；并行任務彼此不影響，可以同時進行設計。

該模型算法實現了計算機編程，提高了計算效率，體現了該算法的實用價值。在該算例中，元素5和元素8是并行關系，計算機自動把兩個元素分在兩個層次，這對產品設計過程建模結果的分析不會產生影響。計算機運算結果如圖12所示。

4 結束語

本文提出一種基于路徑搜索的產品設計過程建模方法，該方法可以對設計要素進行重組優(yōu)化，生成設計結構的耦合層級關系，并應用某大型起重機吊臂的設計過程實例對該方法進行驗證，結果表明該方法清晰、簡明，與實際設計情況相符，為產品設計過程建模提供了可行有效的方法。該方法具有以下特點：①所構建的模型可以和有向圖直接轉化，表達直觀，便于理解；②該方法以圖論與矩陣方法為理論基礎，具有通用性和科學性；③模型算法容易用計算機編程實現，方便過程計算，計算結果可以清晰展現設計過程；④可以通過一次建模，對所有設計要素之間的關系進行分析。本文的后續(xù)研究工作主要針對其他幾種產品設計過程建模算法（可達矩陣法、鄰接矩陣求冪法、撕裂算法等）進行計算機編程，同時根據計算機編程的復雜程度和算法計算速度等指標，對這幾種設計過程建模算法進行比較和改進，從而得到更優(yōu)的設計過程建模方法。

［1］ XIONG Guangleng.The theory and practice of concurrent engineering［M］.Bejing Tsinghua University Press，Springer Press，2001（in Chinese）.［熊光楞.并行工程的理論與實踐［M］.北京：清華大學出版社，施普林格出版社，2001.］

［2］ HUANG Hongzhong，LIU Wei，LI Li.Process modeling of product collaborative design［J］.Computer Integrated Manufacturing Systems，2003，9（11）：955－959（in Chinese）.［黃 洪鐘，劉 偉，李 麗.產品協(xié)同設計過程建模研究［J］.計算機集成制造系統(tǒng)，2003，9（11）：955－959.］

［3］ DANILOVIC M，BROWNING 段 .Managing complex product development projects with design structure matrices and domain mapping matrices［J］.International Journal of Project Management，2007，25（3）：300－314.

［4］ DUIN H，ESCHENB?CHER J，THOBEN 段 .Modelling dynamics in collaboration：an extension to the collaborative network relationship analysis［J］.IFIP Advances in Information and Communication Technology，2011，362：287－294.

［5］ TANG Dunbing，XU Ronghua，TANG Jicheng，et al.Design structure matrix－based engineering change management for product development ［J］.International Journal of Internet Manufacturing and Services，2008，3（1）：231－245.

［6］ GUO Yinzhang，ZENG Jianchao.Dynamic modeling for mechanical product collaborative design process based on OPN and decision rule［J］.China Mechanical Engineering，2011，22（14）：1708－1714（in Chinese）.［郭銀章，曾建潮.基于決策規(guī)則對象Petri網的機械產品協(xié)同設計過程動態(tài)建模［J］.中國機械工程，2011，22（14）：1708－1714.］

［7］ STEWARD 段 .The design structure system：a method for managing the design of complex system［J］.IEEE Transactions on Engineering Management，1981，28（3）：71－74.

［8］ EPPINGER 段 ，NUKALA M，WHITNEY D.Generalized models of design iteration using signal flow graphs［J］.Re－search in Engineering Design，1997，9（2）：112－123.

［9］ Technische Universit?t München.The Design Structure Matrix （DSM）［EB／OL］.［2011－11－16］.http：／／www.dsmweb.org／

［10］ KREIMEYER M，LINDEMANN U.Complexity metrics in engineering design：managing the structure of design processes［M］.Berlin，Germany：Springer－Verlag，2011.

［11］ MA Mingxu，WANG Cheng'en，ZHANG Jiayi，et al.Multi disciplinary design optimization for complex product review［J］.Chinese Joural of Mechanical Engineering，2008，44（6）：15－26（in Chinese）.［馬明旭，王成恩，張嘉易，等.復雜產品多學科設計優(yōu)化技術［J］.機械工程學報，2008，44（6）：15－26.］

［12］ RONG Zhijun，CHEN Kuisheng，YING Baosheng，et al.Structure analysis and optimization of product design proces［J］.China Mechanical Engiineering，2012，23（7）：856－859（in Chinese）.［容芷君，陳奎生，應保勝，等.產品設計過程結構分析和優(yōu)化［J］.中國機械工程，2012，23（7）：856－859.］

［13］ KO 段 .An innovative matrix－based approach for designing product variety ［J］.Systematic Innovation，2010，1（2）：27－43.