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

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

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

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

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

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

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

1 分階段迭代模型的求解

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

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

(1)

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

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

T1=Z(I-K1RK1)-1K1u0

(2)

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

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

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

(3)

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

第S階段所需時間Ts為：

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

(4)

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

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

(5)

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

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

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

圖1 設(shè)計結(jié)構(gòu)矩陣

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

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

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

A B

(6)

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

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

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

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

(7)

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

(8)

(9)

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

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

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

(10)

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

(11)

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

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

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

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

3 實例分析

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

C D E F

(12)

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

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

(13)

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

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

圖3 DSM的結(jié)構(gòu)調(diào)整過程

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

C F E D

(14)

調(diào)整后的DSM的任務(wù)矩陣分別為：

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

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

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

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

4 結(jié) 語

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