基于聚類分析的大容量耦合設計任務規(guī)劃的研究

田啟華 梅月媛 杜義賢 周祥曼

三峽大學機械與動力學院，宜昌，443002

0 引言

以往在大容量耦合設計中，某些耦合設計任務集僅因其部分設計任務之間存在較強的依賴關(guān)系而直接采用串行執(zhí)行方式，造成原本可以并行執(zhí)行的依賴關(guān)系相對較弱的耦合設計任務也按照串行方式執(zhí)行。這種較為籠統(tǒng)的做法不僅延長了設計任務的執(zhí)行周期，更因串行耦合設計任務的規(guī)劃需考慮設計任務的執(zhí)行順序而造成有效規(guī)劃方案會隨著任務數(shù)的增多即容量的增大而呈現(xiàn)出爆炸增長[1]，因此，有必要深入分析耦合設計任務之間的內(nèi)在聯(lián)系，并對其進行有效的分類和合理的規(guī)劃，以縮短大容量耦合設計任務的執(zhí)行周期，快速有效地獲得耦合設計任務最佳規(guī)劃方案，從而提升企業(yè)對市場需求的快速反應能力。

有關(guān)設計任務之間的內(nèi)在聯(lián)系以及設計任務的合理規(guī)劃問題一直是學術(shù)界的研究熱點，并已取得了相應的研究成果。DUIN等[2]在協(xié)同設計的基礎(chǔ)上，應用樹圖網(wǎng)絡建立了產(chǎn)品設計任務動態(tài)模型；宋小文等[3]提出了一種無強制解耦的并行設計過程規(guī)劃方法，通過對各類子任務執(zhí)行優(yōu)先級的定義，完善了并行設計過程的規(guī)劃；邢樂斌等[4]采用模糊排序算法確定了設計任務之間的串行或并行耦合關(guān)系，并建立了設計任務的網(wǎng)絡圖；胡從林等[5]通過有向圖和可達矩陣對設計任務進行劃分，快速建立了設計任務之間的耦合層次關(guān)系；王志亮[6]分別利用基于時間-耦合度和基于時間-序列的撕裂算法對串行耦合設計任務進行了序列優(yōu)化；李玉家等[7]建立了并行產(chǎn)品開發(fā)過程中任務規(guī)劃問題的數(shù)學模型，并利用遺傳算法對數(shù)學模型進行求解。以上研究就如何解決耦合設計任務規(guī)劃問題提供了較好的思路，但它們大多沒有考慮設計任務的數(shù)量對設計任務規(guī)劃的影響，因此在解決大容量耦合設計任務規(guī)劃問題上，這些研究提供的方法還存在一定的局限性。

本文針對現(xiàn)階段在大容量串行耦合設計任務的規(guī)劃問題研究中存在的不足，研究基于聚類分析的耦合設計任務規(guī)劃新方法，以達到縮短產(chǎn)品開發(fā)周期和快速有效地獲得最佳任務規(guī)劃方案的目的。

1 聚類分析用于耦合設計任務分類的可行性分析

基于聚類分析的大容量耦合設計任務規(guī)劃方法的思想是：將大容量耦合設計任務集劃分成若干小容量耦合設計任務子集，通過對各個任務數(shù)少的子任務集的規(guī)劃實現(xiàn)對整個設計任務的快速規(guī)劃。目前，任務的劃分通常涉及劃分、割裂、聯(lián)合、聚類[8]這四種方法，聚類分析(cluster analysis)算法的優(yōu)勢在于它是一種探索性的分析方法，在分類的過程中，不需要事先指定分類的標準，能夠從反映樣本之間相似性的數(shù)據(jù)出發(fā)，自動地對樣本進行分類，并且可以根據(jù)需求靈活地控制類的數(shù)量[9]。

為了對樣品進行聚類分析，就需要得到表征衡量樣品之間相似性的數(shù)據(jù)。聚類分析以相似系數(shù)將樣本之間的相似關(guān)系量化。若用sij表示樣品i和樣品j之間的相似系數(shù)，則應滿足：

(1)

性質(zhì)越接近的樣品，它們的相似系數(shù)的值越接近1；而彼此越無關(guān)的樣品，它們的相似系數(shù)的值越接近于0。度量n個設計任務兩兩之間的相似性，可以得到一個n×n維的相似系數(shù)矩陣S：

(2)

聚類分析就是以相似矩陣S為出發(fā)點，對n個樣品進行分類。分類之后的樣品之間存在類內(nèi)、類間兩種關(guān)系。類內(nèi)關(guān)系的樣品之間存在相對較大的相似性，而類間關(guān)系的樣品之間則存在相對較弱的相似性。

設計任務之所以產(chǎn)生耦合，是因為任務之間存在信息依賴。這種依賴關(guān)系使設計過程出現(xiàn)反復與迭代，伴隨這種迭代反復的是設計任務間頻繁的信息交互[10]。因此，為了保證耦合設計任務的順利開展，需要對任務間在信息上的依賴關(guān)系進行量化。通常采用耦合強度表征兩任務之間的依賴關(guān)系，如aij表示任務j輸出對任務i輸出的耦合強度，而aji則表示任務i輸出對任務j輸出的耦合強度，它們滿足：

(3)

n個設計任務存在的信息依賴關(guān)系可用一個n×n維的耦合強度矩陣C表示：

(4)

定義Aij=aij+aji(i≠j)，用它表示任務i與任務j之間的耦合度。計算任意兩個不同任務之間的耦合度，并定義相同任務之間的耦合度為1，即得到耦合設計任務集的耦合度矩陣F：

(5)

其中，Aij滿足：

(6)

Aij數(shù)值越大，任務i與任務j之間的依賴關(guān)系越緊密，即表明兩個任務之間存在較高的相似性，反之，Aij數(shù)值越小，表明兩個任務之間存在越低的相似性。所以Aij數(shù)值大小也是對耦合設計任務相似關(guān)系強弱的一種度量。另外，比較式(1)、式(6)可知，耦合度矩陣F與相似系數(shù)矩陣S的元素的取值范圍是一致的，因此，通過反映耦合設計任務依賴關(guān)系的耦合度矩陣F對耦合設計任務進行聚類分析，進而實現(xiàn)耦合設計任務的有效分類是可行的。

類似地，聚類分析后的耦合設計任務之間也會存在兩種關(guān)系：同一子集的任務關(guān)系；不同子集的任務關(guān)系。同一子集的設計任務之間耦合度相對較高，不同子集的設計任務之間耦合度相對較低。因此，耦合度較高的同一子集的設計任務采用串行執(zhí)行的方式，而不同子集間由于耦合度較低，各個設計任務盡可能地獨立于其他子集，有利于在設計過程中應用并行執(zhí)行的方式來縮短開發(fā)周期。另外，對于n個設計任務，若分配給m個設計團隊，按照串行耦合方式執(zhí)行，有效的規(guī)劃方案總共有mn×n!個，數(shù)量十分龐大。聚類分析通過將耦合設計任務進行有效的分類，實際上是將大容量耦合設計任務集的規(guī)劃問題轉(zhuǎn)化為小容量耦合設計任務子集的規(guī)劃問題，相當于減少了設計任務n的個數(shù)，從而可以有效地減少規(guī)劃方案的數(shù)量。

2 基于聚類分析的耦合設計任務分類

在進行聚類分析前，需要將設計任務之間的相似性參數(shù)轉(zhuǎn)換成設計任務之間的距離參數(shù)。設計任務之間的距離與設計任務之間的相似性具有相反的物理意義，若兩個設計任務之間的距離越近，則表明兩個設計任務越相似，反之越遠，則表明越疏遠。整個設計中兩兩任務之間的距離通過n×n維的距離矩陣D進行描述，其元素dij表示任務i與j之間的距離，是一個綱量一的量。距離矩陣D與相似系數(shù)矩陣S存在如下關(guān)系：

D=E-S

(7)

式中，E為n×n維的全1矩陣。

通過第1章的分析，本文即以耦合度矩陣C來表示任務之間的相似性，通過式(7)得到耦合設計任務的距離矩陣D，并據(jù)此對大容量耦合設計任務集進行聚類分析。

另外，聚類前還需要定義類間距離的計算方法，類與類之間距離定義方法的不同，決定了不同的聚類方法。本文采用類平均法，定義兩類之間的距離為這兩類元素兩兩之間距離的平均，即

(8)

式中，p、q為類的編號；Dpq為類Gp與Gq之間的距離；dij為任務i與j之間距離，任務i、j分別屬于類Gp、Gq；np、nq分別為類Gp、Gq中設計任務的數(shù)量。

耦合設計任務的聚類過程可描述如下：

(1)根據(jù)式(7)并結(jié)合耦合度矩陣C計算得到耦合設計任務的距離矩陣D，設為D(0)，并將n個設計任務各自集結(jié)成一類，分別計為類G1、類G2、…、類Gn；

(2)找出D(0)的下三角非對角線最小元素，將對應的Gp和Gq合并成一個新類，設為Gr，Gr={Gp,Gq}，在D(0)中去掉Gp、Gq所在的行和列，并通過式(8)計算新類與其余各類之間的距離，將這些距離值作為第一行、第一列元素與D(0)中去掉Gp、Gq所在行列后的矩陣結(jié)合，得到n-1階矩陣D(1)。對D(1)重復上述對D(0)一樣的操作，得到D(2)，如此進行，直到所有任務并成一類為止；

(3)作出體現(xiàn)整個耦合設計任務分類過程的聚類樹狀圖；

(4)根據(jù)任務規(guī)劃需求，確定設計任務的分類數(shù)量。

下面以一個簡單的5×5耦合設計任務集來分析說明采用類平均聚類分析方法劃分耦合設計任務集的計算步驟。設表示這5個設計任務之間耦合強度關(guān)系的耦合強度矩陣C如下：

1 2 3 4 5

以耦合度度量任意兩個任務之間的相似性，根據(jù)式(5)，得到一個5×5維的相似系數(shù)矩陣S(0)：

1 2 3 4 5

根據(jù)式(7)，計算得到設計任務的距離矩陣D，記為D(0)：

1 2 3 4 5

將5個設計任務各自集結(jié)成一類，分別為類G1、G2、G3、G4、G5。通過觀察，D(0)下三角非對角元素中，第5行第1列元素的數(shù)值最小，那么將G1、G5合并成一個新類，記為G6，G6={G1、G5}。根據(jù)式(8)，計算新類G6與其他類的距離：

得到一個新4×4維相似性矩陣D(1)如下：

6 2 3 4

從D(1)可以看出類G2、G4之間的距離最小，因此將G2、G4合并成G7，G7={G2、G4}，同樣地，根據(jù)式(8)計算新類G7與其他類的距離：

進而得到3×3維的矩陣D(2)：

7 6 3

從D(2)可以看出，類G6、G3距離最小，聚為類G8，G8={G6、G3}={G1、G5、G3}，至此只剩下G8、G7兩類，它們之間的距離為

最后，將G8、G7合成一類G9，G9包含了全部5個設計任務。作出聚類樹狀圖，見圖1。

圖1 設計任務聚類樹狀圖Fig.1 Clustering diagram of design task

上述分析實例中的5個設計任務通過聚類分析后可以分為以下情況。5類：{1}、{2}、{3}、{4}、{5}；4類：{1,5}、{3}、{2}、{4}；3類：{1,5}、{3}、{2,4}；2類：{1,5,3}、{2,4}；甚至僅為1類：{1,2,3,4,5}。不同的分類方式下對應的耦合設計任務規(guī)劃方案不同，項目管理人員可通過比較不同分類方式下的任務執(zhí)行周期長短來決定最終的分類數(shù)量。

3 基于聚類分析的耦合設計任務的規(guī)劃方法

耦合設計任務的規(guī)劃包括確定設計任務的團隊分配和執(zhí)行順序兩方面內(nèi)容。無論是否通過聚類分析解決大容量耦合設計任務的規(guī)劃問題，都需要建立耦合設計任務的時間計算模型，再通過求解該模型得到最佳耦合設計任務規(guī)劃方案。整個耦合設計任務的執(zhí)行時間包含了子集內(nèi)部任務執(zhí)行時間與各子集間任務交互時間。

3.1 子集內(nèi)部設計任務時間求解模型的建立及求解

假設通過聚類分析將含有n個設計任務的大容量耦合設計任務劃分成了p個子集(p=1,2,…,n)。同一子集內(nèi)的設計任務采用串行執(zhí)行方式。本文引入工作轉(zhuǎn)移矩陣(work transformation matrix,WTM)模型求解串行耦合設計任務的執(zhí)行時間。WTM模型要求所有的耦合任務并行執(zhí)行，但在實際中有可能出現(xiàn)其中一些任務由于受到資源約束或設計要求的改變等原因需要延遲，并在稍后的過程中才能執(zhí)行。為此，SMITH等[11]提出了多階段WTM設計過程，具體做法是，將n個耦合設計任務劃分到r(r≤n)個階段中，在第一個階段中，一個有限任務集的所有任務并行執(zhí)行；接下來的每個階段所執(zhí)行的任務均包含兩個部分，即該階段的任務集和前一階段任務集的返工。這樣，當r=n時，每個階段只需執(zhí)行一個任務，下一個階段的任務包括當前任務和前一個任務的返工。此時任務的執(zhí)行過程與串行迭代經(jīng)典模型——馬爾可夫鏈模型(圖2)的描述一致。因此，當r=n時，用多階段的WTM設計迭代模型求解串行耦合集設計任務的執(zhí)行時間是可行的。

圖2 具有3個任務的馬爾可夫鏈模型Fig.2 Markov chain model with three tasks

聚類分析后的每個子耦合設計任務集都對應了一個WTM，用W表示，以任務子集p1對應的Wp1為例進行說明。設np1為子集p1包含的設計任務的個數(shù)，Wp1可以拆分成兩個單獨的np1×np1維的數(shù)值矩陣：返工量矩陣Rp1(非對角矩陣)和任務周期矩陣Zp1(對角矩陣)[12]，即Wp1=Rp1+Zp1。

Rp1的元素(rp1)ij表示子集p1內(nèi)的設計任務i在任務j之前完成，i在隨后返工的返工量的比例大小。根據(jù)第1章的分析可知，任務耦合程度的大小體現(xiàn)了設計任務依賴關(guān)系的強弱。在實際設計過程中，依賴關(guān)系越強意味著設計任務在執(zhí)行過程中需要做越多的假設，導致設計任務存在較大程度的返工量，依賴越弱則表示設計任務存在較小程度的返工量[1，13]。因此，從矩陣元素的性質(zhì)方面考慮，可以將任務返工量矩陣R視為耦合強度矩陣C。

Zp1的元素(mp1)ii表示任務i單獨完成的執(zhí)行周期，其值取決于設計任務的團隊分配方案。事實上，由于返工迭代引起的設計周期的延長只占耦合設計任務總設計周期的一小部分，總時間的長短更多地取決于初始執(zhí)行周期的長短，所以為了縮短產(chǎn)品研發(fā)時間，只需將任務分配給執(zhí)行該設計任務花費時間最少的設計團隊即可，由此可以確定耦合設計任務的執(zhí)行周期矩陣Zp1。

在任務分配方案確定，亦即任務執(zhí)行周期矩陣Zp1確定的基礎(chǔ)上，推斷出p1中的第一個設計任務的執(zhí)行周期T1為

T1=‖(Zp1)[I-K1(Rp1)K1]-1K1Up1‖1

(9)

式中，I為np1×np1維的單位矩陣；Up1為初始工作量矩陣，是一個np1×1維的全1矩陣；K1為第一階段的任務分布矩陣，是一個np1×np1維的{0,1}布爾矩陣，其中的元素定義如下：

第二個設計任務的執(zhí)行周期

T2=‖(Zp1)[I-K2(Rp1)K2]-1(K2-K1)Up1‖1

(10)

其中，K2為第二階段的任務分布矩陣，其中的元素定義如下：

進而可以推斷出第x(x=1,2,…,n)個設計任務的執(zhí)行周期Tx為

Tx=‖(Cp1)[I-Kx(Rp1)Kx]-1(Kx-Kx-1)Up1‖1

(11)

其中，Kx為第x階段的任務分布矩陣。Kx中的元素定義如下：

則子任務集p1中的所有設計任務在串行執(zhí)行模式下的時間計算模型Tp1為

(12)

同理，建立其他子任務集的時間求解模型Tp2、Tp3、…、Tpp。

由于各子集間的耦合度較低，所有子任務集采用并行執(zhí)行方式，因此在各子任務集獨立并行階段，設計任務的執(zhí)行周期T1取決于執(zhí)行時間最長的子任務集的設計時間，即

T1=max{Tp1,Tp2,Tp3,…,Tpp}

(13)

在任務分配方案確定的基礎(chǔ)上，串行耦合設計子任務集的規(guī)劃就只包含如何確定設計任務的執(zhí)行順序這一個內(nèi)容。對于分別包含了np1、np2、…、npp個設計任務的子任務集p1、p2、…、pp，在任務分配方案確定的基礎(chǔ)上，有效的規(guī)劃方案仍分別有(np1)!、(np2)!、…、(npp)!種之多，因此，需要采用有效的尋優(yōu)算法從這些方案中找出最佳的任務規(guī)劃方案。考慮到遺傳算法在一些離散優(yōu)化問題中得到了非常有效的應用[14]，本文采用遺傳算法求解時間模型，用以解決串行耦合集設計任務的執(zhí)行順序的尋優(yōu)問題。

串行耦合設計任務每一個執(zhí)行序列在遺傳算法中都對應了一個編碼的染色體。染色體的長度表示耦合集包含的任務個數(shù)，每個編碼位表示設計任務的編號。例如：有6個設計任務的耦合任務集{1,2,3,4,5,6}，則|2|5|6|3|1|4|就是一個合法的染色體，它表示在串行執(zhí)行模式下，任務將按照該染色體確定的順序2-5-6-3-1-4執(zhí)行。利用遺傳算法對執(zhí)行順序?qū)?yōu)的具體過程如下：首先，準備一批表示起始搜索點的初始任務規(guī)劃方案G，利用選擇、交叉、變異3種方式對這個初始群體P進行遺傳操作，實現(xiàn)執(zhí)行序列的優(yōu)化，得到新一代群體G+1。然后遺傳算法會依據(jù)適應度函數(shù)對新一代種群進行評價，并判斷終止條件，若不滿足終止條件，則重復以上過程進行迭代計算，若滿足終止條件，則輸出最佳的任務執(zhí)行序列以及該序列下任務的執(zhí)行時間。

3.2 子集間設計任務時間計算模型的建立及求解

上述關(guān)于時間模型的建立及其求解僅解決了子集內(nèi)部設計任務的規(guī)劃和時間求解問題，通過第1章的分析可知，對耦合設計任務進行聚類分析時，各子集間的耦合關(guān)聯(lián)并沒有完全被消除，因此各子集的設計過程之間也必然產(chǎn)生迭代求解過程。故存在一個p×p維的反映子集間耦合設計關(guān)系和子集任務執(zhí)行周期的工作轉(zhuǎn)移矩陣Wp，同樣，Wp同樣包含返工量矩陣Rp和任務周期矩陣Zp兩部分的信息。其中，Rp中的元素可通過式(7)、式(8)計算得到；Zp對角元素(zp)ii即為上述分析計算得到的每個子集的最佳任務序列下的任務執(zhí)行時間。由于子集間設計任務耦合度低，因此，在項目開發(fā)過程中，應用并行執(zhí)行的方式。

各子集間在并行耦合設計任務執(zhí)行過程中，每一次返工產(chǎn)生的設計時間由一個p×1維的時間矩陣Ti表示：

(14)

由于各個子集任務之間是并行執(zhí)行的關(guān)系，所以每次迭代過程中，迭代時間最長的任務將決定本次返工最終的執(zhí)行時間，每次最長返工時間的累加即為子集間耦合設計任務的總執(zhí)行時間，即

(15)

式中，M為設計人員根據(jù)任務是否達到設計要求而確定的返工次數(shù)。

應用流行的MATLAB語言編制程序求解式(15)，得到各個子任務之間耦合設計時間。

3.3 整個設計任務執(zhí)行時間的確定

整個設計過程的執(zhí)行周期T包含子集任務執(zhí)行時間和子集間任務交互時間兩部分。根據(jù)第3.2節(jié)建立的時間計算模型(式(13)、式(15))，分別求出這兩部分時間，再進行求和，即

T=T1+T2

(16)

若不對耦合設計任務進行聚類分析，直接對整個耦合設計任務集按照串行方式執(zhí)行，則類比式(11)，項目的總時間為

T3=‖Z[I-KRK]-1(K-Kn-1)U0‖1

(17)

式中，R、Z分別為整個設計任務的返工量矩陣和執(zhí)行周期矩陣；K為n×n維任務分布矩陣。

該模型也采用遺傳算法求解，然而遺傳算法并不能很好地解決大規(guī)模計算量問題，它很容易陷入“早熟”[15]。也就是說，若直接對n個串行執(zhí)行的耦合設計任務的最佳執(zhí)行序列進行尋優(yōu)，則由于有效的執(zhí)行序列高達n!種，有可能還沒有得到最佳執(zhí)行序列，遺傳算法就已經(jīng)給出了結(jié)果。聚類分析是將耦合設計任務進行有效的分類，實際上是將大容量耦合設計任務集的規(guī)劃問題轉(zhuǎn)化為小容量耦合設計任務子集的規(guī)劃問題，

很大程度地減小了設計任務n的個數(shù)，因此，十分有利于在求解過程中利用遺傳算法確定設計任務的執(zhí)行順序。

4 實例分析

機械手屬于典型的多學科復雜產(chǎn)品，為滿足產(chǎn)品的各項功能和性能，通常采用模塊化研究技術(shù)按功能和需求對機械手的組成進行劃分，提高機械手的使用靈活性，簡化安裝和維護[16]，這是目前個性化機械手成本低、質(zhì)量高、交貨期短的主要原因之一。然而在研發(fā)階段，機械手的每一組成部分的設計都存在大量的耦合關(guān)系[17]，因此又制約著機械手的設計周期，從而影響其交貨期。

本文以某機械手的規(guī)劃和研發(fā)過程為例，對聚類分析解決大容量耦合設計任務規(guī)劃的可行性和有效性進行分析。該機械手的研發(fā)過程經(jīng)過簡化處理后得到一個15×15維的耦合設計任務系統(tǒng)。將這15個耦合設計任務分配給設計團隊，確定各個設計任務的開發(fā)時間，得到W矩陣如下：

ABCDEFGHIJKLMNOA30000．131000．185000．13100．050000B0．102450．1400．2120．16100000．06800．0810．20300C0．0300．137500．1250．1090000000．0940．22400D00．1860250．0340000．1850．12700．17300．2180．218E0．10100．0750．0801000．1720．1510000．080000F0．1070000200．1100．160000．1320．0800．06800．061G00．1210．17700．1130．164200．2160．0150．23200．1420．22200．200H0．1050．1000．1100．1110．1130．1050．095350．093000000I0．1020000．120000．182400．10300000J0．01500．39000000．1535500．13600．2530K0．033000．1500．1500．1120000．21930000．1730L0．1120．145000．19500．37000．2190045000M0．1200．1240000．2940．19100．090000．0325500．232N0．1010．1620000000．201000．0570100．154O0．02000．0500．11600．3010000000020

按照第2節(jié)給出的耦合設計任務集聚類分析的一般步驟，對該耦合任務集進行聚類分析，得到的聚類樹狀圖，見圖3。

圖3 機械手設計任務聚類圖Fig.3 Clustering diagram of manipulator design task

假設項目管理人員將設計任務劃分成3個子任務集，分別為p1={A，F(xiàn)，I，L，M，N}、p2={B，C，J，O}、p3={D，E，G，H，K}。各個子任務集的工作轉(zhuǎn)移矩陣Wpx(x=1,2,3)如下：

A F I L M N

B C J O

D E G H K

分別建立這三個子耦合設計任務集的時間求解模型，并分別利用遺傳算法求解，各子集的最佳設計任務規(guī)劃方案的遺傳算法的搜索空間分別為6！ =720、4! =24、5! =720。各子集的最佳執(zhí)行序列及對應的執(zhí)行時間如表1所示。

表1 子任務集最佳執(zhí)行順序及對應時間

由于子集p1的執(zhí)行時間最長，則在各個子集獨立并行執(zhí)行這一階段，項目開發(fā)時間T1=216.336。

接下來，需考慮3個子任務集之間耦合迭代產(chǎn)生的時間。根據(jù)第1章的分析可知，可通過一個3×3維的工作轉(zhuǎn)移矩陣Wp反映本實例中子集間的耦合設計關(guān)系和子集任務執(zhí)行周期，其中，Rp中的元素可通過式(7)、式(8)計算得到，Zp對角元素(zp)ij即為表1中各子任務集在最佳任務序列下的任務執(zhí)行時間。表征子集間的Wp為

p1p2p3

子集間的設計任務采用并行執(zhí)行的方式，根據(jù)式(15)，并取U0=[1 1 1]T，計算得到的子集間設計任務的耦合迭代階段設計任務的執(zhí)行時間為T2=29.124。則整個設計任務的執(zhí)行周期為這兩個階段設計任務執(zhí)行時間之和：T=216.336+29.124=245.46。

若不對耦合設計任務集進行聚類分析，直接對這15個設計任務在串行執(zhí)行條件下進行規(guī)劃，在任務分配方案確定的基礎(chǔ)上，有效規(guī)劃方式仍高達15!=1.377×1012種，利用遺傳算法進行尋優(yōu)，最佳任務規(guī)劃方案下對應的任務執(zhí)行周期T=1007.2，對應的任務序列為A-E-F-H-I-O-N-

D-M-B-C-G-L-J-K。然而，基于遺傳算法的局限性，這個任務規(guī)劃方案有可能不是最佳結(jié)果。

如表2所示，對兩種規(guī)劃方法的執(zhí)行效果進行比較，按照本文提供的基于聚類分析的耦合設計任務的規(guī)劃方法，開發(fā)項目的總設計時間大為縮短，最佳任務規(guī)劃方案的搜索空間大大縮小。相比之下，遺傳算法對聚類分析之后的子耦合設計任務集的執(zhí)行順序進行尋優(yōu)得到的結(jié)果更為有效。

表2 兩種規(guī)劃方法執(zhí)行效果比較

5 結(jié)語

本文針對串行耦合設計任務開發(fā)時間長，有效規(guī)劃方案數(shù)量龐大的問題，通過聚類分析將耦合設計任務集劃分成若干子集，并將串行耦合設計任務的規(guī)劃和執(zhí)行過程劃分為子任務集的規(guī)劃與執(zhí)行、子集間的規(guī)劃與執(zhí)行兩個階段。子集內(nèi)的任務由于耦合程度高故采用串行執(zhí)行方式，而子集間任務由于耦合程度低故采用并行執(zhí)行方式，從而有效地縮短了設計任務的執(zhí)行周期，縮小了設計任務規(guī)劃方案的搜索空間。對某機械手開發(fā)設計過程分析結(jié)果表明，聚類分析用以解決大容量耦合設計任務規(guī)劃問題是可行且有效的。

參考文獻：

[1] 王志亮,張友良. 復雜耦合系統(tǒng)設計過程動態(tài)規(guī)劃[J]. 計算機工程與應用,2005,41(13):117-120.

WANG Zhiliang, ZHANG Youliang. A Dynamic Decision Model for the Complex Coupled System’s Design Process[J].Computer Engineering and Applications, 2005,41(13):117-120.

[3] 宋小文,洪智化,王耘,等. 無強制解耦的并行設計過程規(guī)劃方法[J]. 計算機集成制造系統(tǒng),2010,16(4):696-702.

SONG Xiaowen, HONG Zhihua, WANG Yun,et al. Concurrent Design Process Planning Method with Unforced Decoupling[J]. Computer Integrated M anufacturing Systems,2010,16(4):696-702.

[4] 邢樂斌,李君. 基于設計迭代的耦合任務動態(tài)分配策略研究[J]. 計算機工程與應用, 2012, 48(23):219-223.

XING Lebin, LI Jun. Dynamic Assignment of Coupled Tasks Based on Design Iteration[J]. Computer Engineering and Applications, 2012, 48(23)：219-223.

[5] 胡從林,容芷君,陳奎生,等. 產(chǎn)品設計任務的聚類優(yōu)化研究[J]. 機械設計與制造,2014(7):259-261.

HU Conglin, RONG Zhijun, CHEN Kuisheng, et al. Research on Clustering Optimization of Product Design Task[J]. Machinery Design and Manufacture, 2014(7):259-261.

[6] 王志亮. 復雜產(chǎn)品敏捷化開發(fā)中若干關(guān)鍵決策技術(shù)的研究[D].南京：南京理工大學,2004.

WANG Zhiliang. Research on Decision-making Techniques for Agile Development of Complex Product[D]. Nanjing: Nanjing University of Technology, 2004.

[7] 李玉家,胡宗武,金燁. 并行產(chǎn)品開發(fā)過程中的任務分配問題研究[J]. 中國機械工程,2002,13(7):46-49.

LI Yujia， HU Zongwu， JIN Ye. Research on Task Distribution in Concurrent Product Development[J]. China Mechanical Engineering,2002,13(7):46-49.

[8] 閆華鋒,仲偉俊. 復雜產(chǎn)品系統(tǒng)模塊化分解模型及應用研究[J]. 北京航空航天大學學報，2016，43(4):654-659.

YAN Huafeng， ZHONG Weijun. Modular Decomposition Model of Complex Product System and Its Application [J]. Journal of Beijing University of Aeronautics and Astronautics， 2016，43(4):654-659.

[9] 蔡洪山. 大數(shù)據(jù)分析中的聚類算法研究[D].淮南：安徽理工大學,2016.

CAI Hongshan. Research of Clustering Algorithms in Big Data Analysis[D]. Huainan: Anhui University of Science and Technology,2016.

[10] 肖人彬, 陶振武, 劉勇. 智能設計原理與技術(shù)[M].北京: 科學出版社,2006:45-46.

XIAO Renbin, TAO Zhenwu, LIU Yong. Intelligent Design Theory and Technology[M]. Beijing: Science Press, 2006:45-46.

[11] SMITH R P, EPPINGER S D. Deciding Between Sequential and Concurrent Tasks in Engineering Design[J]. Concurrent Engineering Research and Applications,1998,3:15-25.

[12] 陳庭貴,肖人彬. 基于內(nèi)部迭代的耦合任務集求解方法[J].計算機集成制造系統(tǒng), 2008，14(12):2375-2383.

CHEN Tinggui, XIAO Renbin. Coupled Task Set Solving Method Based on Inner Iteration[J], Computer Integrated Manufacturing Systems, 2008,14(12):2375-2383.

[13] 汪鳴琦,陳榮秋,崔南方. 工程迭代設計中產(chǎn)品族開發(fā)過程的研究與建模[J]. 計算機集成制造系統(tǒng),2007,13(12):2373-2381.

WANG Mingqi, CHEN Rongqiu, CUI Nanfang. Modeling of Product Family Development Process in Engineering Iteration Design[J]. Computer Integrated Manufacturing Systems, 2007,13(12):2373-2381.

[14] 寧桂英,曹敦虔,周永權(quán). 一種求解約束優(yōu)化問題的改進差分進化算法[J]. 數(shù)學的實踐與認識,2017,47(2):155-165.

NING Guiying， CAO Dunqian， ZHOU Yongquan. An Improved Differential Evolution Algorithm for Solving Constraint Optimization Problem[J]. Mathematics in Practice and Theroy, 2017,47(2):155-165.

[15] 李中華,張?zhí)┥? 可拓聚類適應度共享小生境遺傳算法研究[J]. 哈爾濱工業(yè)大學學報,2016,48(5):178-183.

LI Zhonghua， ZHANG Taishan. Research of Fitness Sharing Niche Genetic Algorithms Based on Extension Clustering[J]. Journal of Harbin Institute of Technology, 2016,48(5): 178-183.

[16] 梁健文,林彩麟,李仕奇. 沖壓機械手的模塊化技術(shù)研究與應用[J]. 機電工程技術(shù),2016,45(12):58-61.

LIANG Jianwen, LIN Cailin, LI Shiqi. Research and Application of Modular Technology of Stamping Manipulator[J]. Mechanical & Electrical Engineering Technology, 2016,45(12):58-61.

[17] 李瀟波, 趙亮, 許正蓉. 基于改進的DSM耦合任務規(guī)劃方法的研究[J]. 中國機械工程, 2010，21(2):212-217.

LI Xiaobo， ZHAO Liang， XU Zhengrong. Research on Improved DSM Algorithm for Coupling Task Order Programming [J]. China Mechanical Engineering, 2010，21(2):212-217.