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

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

三峽大學(xué)機(jī)械與動(dòng)力學(xué)院，宜昌，443002

0 引言

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

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

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

1 聚類分析用于耦合設(shè)計(jì)任務(wù)分類的可行性分析

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

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

(1)

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

(2)

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

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

(3)

n個(gè)設(shè)計(jì)任務(wù)存在的信息依賴關(guān)系可用一個(gè)n×n維的耦合強(qiáng)度矩陣C表示：

(4)

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

(5)

其中，Aij滿足：

(6)

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

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

2 基于聚類分析的耦合設(shè)計(jì)任務(wù)分類

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

D=E-S

(7)

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

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

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

(8)

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

耦合設(shè)計(jì)任務(wù)的聚類過程可描述如下：

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

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

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

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

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

1 2 3 4 5

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

1 2 3 4 5

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

1 2 3 4 5

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

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

6 2 3 4

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

進(jìn)而得到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個(gè)設(shè)計(jì)任務(wù)。作出聚類樹狀圖，見圖1。

圖1 設(shè)計(jì)任務(wù)聚類樹狀圖Fig.1 Clustering diagram of design task

上述分析實(shí)例中的5個(gè)設(shè)計(jì)任務(wù)通過聚類分析后可以分為以下情況。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}。不同的分類方式下對(duì)應(yīng)的耦合設(shè)計(jì)任務(wù)規(guī)劃方案不同，項(xiàng)目管理人員可通過比較不同分類方式下的任務(wù)執(zhí)行周期長(zhǎng)短來決定最終的分類數(shù)量。

3 基于聚類分析的耦合設(shè)計(jì)任務(wù)的規(guī)劃方法

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

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

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

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

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

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

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

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

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

(9)

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

第二個(gè)設(shè)計(jì)任務(wù)的執(zhí)行周期

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

(10)

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

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

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

(11)

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

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

(12)

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

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

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

(13)

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

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

3.2 子集間設(shè)計(jì)任務(wù)時(shí)間計(jì)算模型的建立及求解

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

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

(14)

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

(15)

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

應(yīng)用流行的MATLAB語言編制程序求解式(15)，得到各個(gè)子任務(wù)之間耦合設(shè)計(jì)時(shí)間。

3.3 整個(gè)設(shè)計(jì)任務(wù)執(zhí)行時(shí)間的確定

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

T=T1+T2

(16)

若不對(duì)耦合設(shè)計(jì)任務(wù)進(jìn)行聚類分析，直接對(duì)整個(gè)耦合設(shè)計(jì)任務(wù)集按照串行方式執(zhí)行，則類比式(11)，項(xiàng)目的總時(shí)間為

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

(17)

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

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

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

4 實(shí)例分析

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

本文以某機(jī)械手的規(guī)劃和研發(fā)過程為例，對(duì)聚類分析解決大容量耦合設(shè)計(jì)任務(wù)規(guī)劃的可行性和有效性進(jìn)行分析。該機(jī)械手的研發(fā)過程經(jīng)過簡(jiǎn)化處理后得到一個(gè)15×15維的耦合設(shè)計(jì)任務(wù)系統(tǒng)。將這15個(gè)耦合設(shè)計(jì)任務(wù)分配給設(shè)計(jì)團(tuán)隊(duì)，確定各個(gè)設(shè)計(jì)任務(wù)的開發(fā)時(shí)間，得到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é)給出的耦合設(shè)計(jì)任務(wù)集聚類分析的一般步驟，對(duì)該耦合任務(wù)集進(jìn)行聚類分析，得到的聚類樹狀圖，見圖3。

圖3 機(jī)械手設(shè)計(jì)任務(wù)聚類圖Fig.3 Clustering diagram of manipulator design task

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

A F I L M N

B C J O

D E G H K

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

表1 子任務(wù)集最佳執(zhí)行順序及對(duì)應(yīng)時(shí)間

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

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

p1p2p3

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

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

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[1] 王志亮,張友良. 復(fù)雜耦合系統(tǒng)設(shè)計(jì)過程動(dòng)態(tài)規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用,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] 宋小文,洪智化,王耘,等. 無強(qiáng)制解耦的并行設(shè)計(jì)過程規(guī)劃方法[J]. 計(jì)算機(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] 邢樂斌,李君. 基于設(shè)計(jì)迭代的耦合任務(wù)動(dòng)態(tài)分配策略研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 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)品設(shè)計(jì)任務(wù)的聚類優(yōu)化研究[J]. 機(jī)械設(shè)計(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] 王志亮. 復(fù)雜產(chǎn)品敏捷化開發(fā)中若干關(guān)鍵決策技術(shù)的研究[D].南京：南京理工大學(xué),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ā)過程中的任務(wù)分配問題研究[J]. 中國(guó)機(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] 閆華鋒,仲偉俊. 復(fù)雜產(chǎn)品系統(tǒng)模塊化分解模型及應(yīng)用研究[J]. 北京航空航天大學(xué)學(xué)報(bào)，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].淮南：安徽理工大學(xué),2016.

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

[10] 肖人彬, 陶振武, 劉勇. 智能設(shè)計(jì)原理與技術(shù)[M].北京: 科學(xué)出版社,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)部迭代的耦合任務(wù)集求解方法[J].計(jì)算機(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] 汪鳴琦,陳榮秋,崔南方. 工程迭代設(shè)計(jì)中產(chǎn)品族開發(fā)過程的研究與建模[J]. 計(jì)算機(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ìn)差分進(jìn)化算法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(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í)┥? 可拓聚類適應(yīng)度共享小生境遺傳算法研究[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào),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] 梁健文,林彩麟,李仕奇. 沖壓機(jī)械手的模塊化技術(shù)研究與應(yīng)用[J]. 機(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] 李瀟波, 趙亮, 許正蓉. 基于改進(jìn)的DSM耦合任務(wù)規(guī)劃方法的研究[J]. 中國(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.