基于分階段迭代模型的產(chǎn)品設計任務分布方案優(yōu)化

田啟華 鄢君哲 董群梅 張玉蓉 周祥曼

(1. 三峽大學 機械與動力學院， 湖北 宜昌 443002； 2. 國電大渡河檢修安裝有限公司， 四川 樂山 614000)

完全的并行迭代模型假設所有的耦合集任務同時并行執(zhí)行，而在實際的產(chǎn)品開發(fā)過程中，部分任務由于設計要求的改變或資源約束等原因總存在執(zhí)行順序先后問題，優(yōu)先完成的任務必須要等待后完成的任務，故完全并行迭代模型已經(jīng)不再適用，故需要采用分階段迭代模型處理．針對分階段迭代模型中任務分布方案優(yōu)化的問題，國內外學者進行了相關的研究，并取得了相應的成果．如：Smith等[1]將工作轉移矩陣(work transformation matrix, WTM)運用到二階段迭代模型中，得到了有利于減少項目開發(fā)時間成本的任務分配方案；陳衛(wèi)明等[2]通過啟發(fā)式算法對二階段迭代模型執(zhí)行時間進行求解，但是沒有給出尋求最優(yōu)的二階段迭代模型任務分布方案的可行方法；肖人彬等[3]針對分階段迭代模型中的資源分配問題，運用遺傳算法得到了較優(yōu)的資源分配方案；田啟華等[4]運用動態(tài)規(guī)劃法對二階段迭代模型的任務分布方案進行尋優(yōu)，并證明了該方法能在一定程度上彌補啟發(fā)式方法容易陷入局部最優(yōu)解的不足．上述文獻從不同角度研究了分階段迭代模型中任務分布方案優(yōu)化的問題．但是，不同算法對具體迭代模型的適用性較為有限，甚至需要對算法進行一定的改進才能成功獲取一個較優(yōu)解．

鑒于以上研究的不足，引入Markov Chain理論．假設在設計任務的迭代過程中，每次只有一個任務執(zhí)行，因此其過程轉化為串行設計迭代過程，而耦合設計任務集總的執(zhí)行時間等于那些任務所花時間的總和．針對此假設，耦合設計任務集可以描述成Markov Chain模型并用Markov Chain分析方法進行分析．由于Markov Chain分析方法是建立在隨機統(tǒng)計分析基礎之上，因此算法簡單，求解過程清晰明了，無需借助計算機編程就能得到結果．當耦合任務規(guī)模較小時，采用馬爾可夫鏈(Markov Chain)方法對串行迭代過程進行建模分析，可以通過計算純粹順序情況下的總迭代時間，來確定最優(yōu)的耦合集任務執(zhí)行順序．

目前Markov Chain在迭代建模中也已經(jīng)得到許多成功應用．例如：石坤等[5]運用Markov Chain理論，將量化的流程圖轉化為Markov概率轉移圖，根據(jù)概率轉移圖列出概率轉移矩陣，求解矩陣的平穩(wěn)分布，利用平穩(wěn)分布來解出駕駛人行為的可靠性；南愛強等[6]結合經(jīng)典灰色理論，構建了一種新型的灰色Markov Chain模型，相較傳統(tǒng)的經(jīng)典灰色理論具備較高的預測精度．設計結構矩陣能簡化并有效地描述、分析信息流和迭代循環(huán)等信息交互關系，具有較強的問題描述能力[7-8]，還能很好地適應矩陣運算，被廣泛地應用于產(chǎn)品開發(fā)領域的研究中．目前，DSM在耦合集迭代的求解問題上已經(jīng)得到不少應用，例如楊沁等[9]分析了需求節(jié)點之間的矛盾，提出了一種基于DSM的客戶需求表達方法；錢艷俊等[10]充分利用矩陣運算的特點，提出了基于DSM的耦合活動排程．

本文在分階段迭代模型的基礎上，以縮短產(chǎn)品開發(fā)過程的時間成本為目標，引入設計結構矩陣，運用Markov Chain方法對設計任務的迭代過程進行分析，得到不同任務分布方案下執(zhí)行時間、任務周期和返工概率的關系，提出一種基于分階段迭代模型的產(chǎn)品設計任務分布方案優(yōu)化．

1 分階段迭代模型的求解

分階段迭代模型是在完全并行迭代模型的基礎上發(fā)展而來的，是將部分任務延遲執(zhí)行的情況加以考慮，其求解方法是將整個耦合任務集分成若干個子集，并將這些任務子集分配到不同的階段中去執(zhí)行．在迭代過程中，整個耦合任務集通常包含有多個設計任務(假設任務個數(shù)為m)，可能的迭代方式包括一階迭代、二階迭代、……、m階迭代．為了便于研究說明，本文以m階迭代為研究對象，即假定每個階段均只有一個任務被執(zhí)行的情況．

為了描述分階段迭代模型中各任務的分布情況，定義對角線矩陣K為任務分布矩陣，表示為：

(1)

式中，矩陣K對角線上元素k11、k22、…，kij，…、kmm取值為0或者1(其中i=j，i=1，2，…，m)，當取值為0時，表示第i個任務不在當前指定的階段被執(zhí)行，當取值為1時，表示第i個任務在當前指定的階段被執(zhí)行．

根據(jù)文獻[11]，分階段迭代模型第1階段的執(zhí)行時間T1為：

T1=Z(I-K1RK1)-1K1u0

(2)

式中，Z是任務周期矩陣；R是返工概率矩陣；初始的工作向量u0是全1向量，表示在第一次迭代中所有任務都需要同時執(zhí)行；I為單位矩陣，矩陣K1是一個對角矩陣，描述了任務在第1階段迭代過程中的執(zhí)行情況，矩陣K1對角線上第i行第j列元素的取值定義如下：

第2階段需要的執(zhí)行時間T2為：

T2=Z(I-K2RK2)-1(K2-K1)u0

(3)

式中，矩陣K2為第2階段的任務分布矩陣，描述了任務在第2階段迭代過程中的執(zhí)行情況，矩陣K2對角線上第i行第j列元素的取值定義如下：

第S階段所需時間Ts為：

Ts=Z(I-KsRKs)-1(Ks-Ks-1)u0

(4)

式中，矩陣Ks為第s階段的任務分布矩陣，描述了任務在第s階段迭代過程中的執(zhí)行情況，矩陣Ks對角線上第i行第j列元素的取值定義如下：

將所有階段的執(zhí)行時間求和，并對其取模，可得到迭代過程的總時間成本值為T：

(5)

對于一個包含有多個任務的分階迭代過程，通過設計一個較優(yōu)的任務分布可以減少迭代過程的時間成本．因此，從迭代過程本身出發(fā)，通過研究DSM中任務周期矩陣Z、返工概率矩陣R與時間成本之間的關系，以得到有利于時間成本下降的任務布局方法．

2 任務分布方案的優(yōu)化策略

DSM是一個具有相同行列標志的矩陣，能夠以直觀、形象、最優(yōu)的分析形式顯示迭代過程中任務之間的耦合關系．本文采用DSM對耦合集中任務的執(zhí)行狀態(tài)進行描述．例如，對于一個包含有A、B、C、D4個任務的耦合集的四階迭代過程，若A、B、C、D任務分別在第1階段、第2階段、第3階段、第4階段被執(zhí)行，結合文獻[12-13]中DSM的設計方法，該迭代過程對應的設計結構矩陣如圖1所示．

圖1 設計結構矩陣

由圖1可知， DSM主要包括對角線和非對角線單元．其中，z1、z2、z3、z4為DSM對角線上的元素，描述了耦合集中各任務的執(zhí)行周期值；是DSM非對角線的元素，表示在迭代過程中任務的返工概率．圖1設計結構矩陣對應的任務周期矩陣Z和返工概率矩陣R分別為：

根據(jù)公式(1)～(5)可知，迭代過程的執(zhí)行時間不僅與任務的分布矩陣Ks有關，還與任務周期矩陣Z、返工概率矩陣R直接相關，而任務周期矩陣Z、返工概率矩陣R分別由DSM中對角線上的元素、非對角線上的元素組成，且各階段迭代的任務分布矩陣Ks也是由DSM中任務的執(zhí)行順序決定．

為了減小問題分析難度，取DSM中任務A、B進行分析，并簡化DSM中元素的記法，即：z1、z2分別是任務A和B的執(zhí)行周期值，取值為整數(shù)，表示任務A和B分別獨立執(zhí)行所需的時間；r1、r2分別是任務A、B的返工概率，其取值范圍均為0到1，r1表示每次任務A完成后，引起任務B要重做的概率，而r2表示每次任務B完成后，引起任務A要重做的概率，對應的DSM如下：

A B

(6)

對該迭代過程建立Markov Chain模型，如圖2所示．任務分布優(yōu)化相當于確定哪條虛箭線包括在鏈的模型中．

圖2 2×2階迭代的Markov Chain模型

圖2中虛線指向A，表示任務A在第1階段先執(zhí)行，任務B在第2階段被執(zhí)行，記為A-B方案；若虛線指向任務B，則為B-A方案．

定義TA和TB分別表示在同一迭代過程中任務A和任務B的執(zhí)行時間，根據(jù)圖2的迭代過程，參考文獻[14]中運用Markov Chain對串行迭代過程進行建模的方法，可得到如下矩陣線性方程組：

(7)

用TA-B和TB-A分別表示A-B、B-A方案的時間成本，分別求解兩種任務分布的TA-B和TB-A關于周期值z1、z2和返工概率值r1、r2的數(shù)學關系式．

(8)

(9)

通過上述分析，可知對于包含任務A和B的耦合集迭代過程，其可能的任務分布方案及對應的DSM和時間成本見表1．

表1 兩種方案下的DSM及時間成本T

為了便于分析任務分布方案的優(yōu)化策略，先假設A-B方案的時間成本小于B-A方案，即

(10)

由于00，將公式(10)中不等式的兩邊同乘以(1-r1r2)，整理后，可以得到z1r2(1-r1)

(11)

結合式(6)對應的DSM可知r1、r2對應為DSM中的非對角線元素，z1、z2對應為DSM中的對角線元素．分析式(11)可知，當任務A的執(zhí)行周期z1小于任務B的執(zhí)行周期z2、任務B的返工概率r2小于任務A的返工概率r1時，式(10)、式(11)恒成立，即TA-B

《浙江省海洋功能區(qū)劃（2011-2020 年）》（2018 年修訂版）正式發(fā)布（省廳辦公室） .........................11-13

為了獲得時間成本較低的任務分布，結合上述分析過程，執(zhí)行周期長的任務應優(yōu)先安排在DSM對角線的右下方，返工概率大的值應放置在DSM對角線的下方，這種任務布局是有利于時間成本減少的．

以上分析過程，是以迭代過程中的兩個任務為對象來分析的，將任務分布方案的優(yōu)化問題，轉化成具體的計算推理，進而抽象性地得出了有利于時間成本的布局方法．雖然理論過程存在一定的局限性，但是，該研究方法是從迭代過程的本身出發(fā)進行的計算推導，與目前已有的引入優(yōu)化算法來獲取較優(yōu)的任務布局相比，是解決分階段迭代過程方案優(yōu)化的另一種途徑．下面通過示例計算說明本文提出方法的有效性．

3 實例分析

以某型號照相機開發(fā)過程為例進行說明．該產(chǎn)品開發(fā)過程包括功能定義(任務A)、概念設計(任務B)、快門裝置設計(任務C)、取景裝置設計(任務D)、相機體設計(任務E)、卷片裝置設計(任務F)、光學鏡頭設計(任務G)、光圈設計(任務H)等8個任務，其中任務C、任務D、任務E以及任務F等4個任務構成帶循環(huán)信息流的耦合集[1，12]．假定照相機開發(fā)過程中C、D、E、F分別在第1、2、3、4階段被執(zhí)行，對應的任務分布形式表示為(C、D、E、F)，DSM對角線上的元素表示任務C、D、E、F各自獨立執(zhí)行的周期，非對角線上元素表示各任務的返工概率，該方案下的DSM如下．

C D E F

(12)

由周期矩陣Z、返工概率矩陣R的定義，可得到照相機開發(fā)的Z、R矩陣分別為：

在迭代初始階段，初始工作向量u0為全1列向量，即：u0=[1 1 1 1]T，任務C、D、E、F分別被分配到1、2、3、4階段去執(zhí)行執(zhí)行，根據(jù)第2節(jié)關于任務分布矩陣K的元素的定義，可得各階段的任務分布矩陣分別為：

(13)

將Z、R、K1、K2、K3、K4、u0、I分別帶入公式(13)，可以得到基于任務分布方案(C、D、E、F)的時間成本為200.361 4個時間單位．

下面應用本文提出任務分布優(yōu)化方法對DSM進行重新調整．為減少照相機開發(fā)的時間成本，在對DSM進行調整的過程中，盡可能讓周期較長的任務稍后執(zhí)行，高返工概率值置于DSM對角線的下方，分析公式(12)中DSM的數(shù)據(jù)結構，需要將返工概率較高的0.5和0.4調整到對角線的下方，周期最長的任務D盡可能安排在靠后階段被執(zhí)行，可將DSM第4行和第2行進行交換，再將第2列與第4列交換，調整過程如圖3所示．

圖3 DSM的結構調整過程

圖3得到的調整后的DSM的任務分布形式為表示任務C第1階段被執(zhí)行，任務F在第2階段被執(zhí)行，任務E在第3階段被執(zhí)行，任務D在第4階段被執(zhí)行，即調整后的DSM為：

C F E D

(14)

調整后的DSM的任務矩陣分別為：

照相機開發(fā)過程基于調整后的DSM的Z、R矩陣分別為：

將Z、R、K1、K2、K3、K4、u0、I分別代入公式(13)，可得到任務分布方案(C F E D)的時間成本值為154.470 1．對DSM進行調整前，周期最長的任務D在第2階段被執(zhí)行，返工概率較高的數(shù)值0.5和0.4在對角線的上方；調整后的DSM中，周期最長的任務D在最后段被執(zhí)行，返工概率較高的數(shù)值0.5和0.4均在對角線下方，時間成本為154.470 1個時間單位，見表2．

表2 基于DSM優(yōu)化策略前后的任務布局及時間成本

由表2可知，調整前照相機開發(fā)過程的時間成本為200.361 4個時間單位，調整后的時間成本為154.470 1個時間單位，調整后減少了45.891 3個時間單位，時間成本下降了22.904 2%．以上分析結果表明，對于分階段迭代模型任務分布優(yōu)化問題，采用本文提出的基于DSM優(yōu)化方法，即周期長的任務稍后執(zhí)行，返工概率高的值放在DSM對角線的下方，是有利于時間成本下降的任務布局．

4 結 語

本文研究的基于分階段迭代模型的產(chǎn)品設計任務分布方案優(yōu)化方法，通過運用Markov Chain方法來分析任務周期和返工概率對不同任務分布時間成本的影響，并通過構建任務分配衍生矩陣，簡化了分階段耦合集設計任務分配的數(shù)學模型．運用該方法對分階段迭代模型的任務分布進行優(yōu)化，以某型號照相機開發(fā)過程為例，驗證了該分析方法是可行且有效的，并能獲取一個能有效減少產(chǎn)品開發(fā)過程的時間成本的相對較優(yōu)解，對實際產(chǎn)品開發(fā)有一定的參考意義．