田啟華 汪汝學 張玉蓉 周祥曼 付君健

(1.三峽大學 機械與動力學院，湖北 宜昌 443002;2.聞泰科技股份有限公司BG2服務器事業(yè)部，上海 200030)

產品設計開發(fā)過程中，任務執(zhí)行時間常常受到各種外界因素的影響而變得不確定，由此將直接導致產品開發(fā)過程的總工期估算產生較大誤差，進而產生不合實際的任務執(zhí)行方案.

國內外學者針對任務執(zhí)行工期的不確定性問題進行了大量研究.例如，Elmaghraby[1]發(fā)現用平均值替換隨機變量來規(guī)避項目中各種參數的不確定性，可能會在成本估算和基于成本估算的投標中出現錯誤;陳衛(wèi)明等[2]應用統(tǒng)計學的三點估計法來解決產品開發(fā)中任務執(zhí)行工期的不確定性問題，建立了動態(tài)環(huán)境下基于混合迭代的耦合集求解模型;Lombardi等[3]通過利用優(yōu)先級約束發(fā)布(PCP)的離線/在線混合技術，解決了存在持續(xù)時間不確定性的多任務應用程序的可預測和有效的非搶占調度問題;施騫等[4]著重分析了兩種概率型調度方法的研究現狀;田啟華[5]等研究了動態(tài)環(huán)境下任務工期不確定性對產品開發(fā)過程的影響，利用反饋控制原理對并行耦合任務迭代過程進行動態(tài)調節(jié);耿蘇杰等[6]以任務工期和發(fā)布時間分別描述項目內部與外部環(huán)境不確定性對項目實施的影響，并采用模糊數進行參數表示，利用蟻群優(yōu)化算法證實該研究所得到的預防調度方案可以保證項目順利完工的概率高且完工時間更短;Liu等[7]針對具有初始環(huán)境信息不完全、并發(fā)執(zhí)行和執(zhí)行時間不確定等特點的應急任務規(guī)劃問題，提出了一種具有不確定持續(xù)時間的有條件時態(tài)HTN規(guī)劃的范例;Li等[8]研究了任務執(zhí)行時間不確定條件下霧隊列系統(tǒng)中實時任務的資源分配與任務卸載，利用機器學習方法對任務執(zhí)行時間的上限和下限進行預測;田啟華等[9]建立了工期不確定條件下區(qū)間型多目標優(yōu)化數學模型，采用改進的NSGA-Ⅱ求解，得到了任務調度方案的Pareto最優(yōu)解集，等等.

但目前大多數針對任務執(zhí)行時間不確定性的研究，沒有充分考慮不確定因素在迭代過程中的影響.因此，面對產品設計開發(fā)中的耦合問題和任務執(zhí)行時間不確定性問題，提出新的解決方法以及任務調度求解模型，以實現資源的合理分配和產品開發(fā)的工期和開發(fā)成本多目標優(yōu)化，是人們十分關注的.本文針對產品開發(fā)過程中存在任務執(zhí)行時間不確定性問題，采用六點模糊數來描述產品開發(fā)中任務的執(zhí)行時間，結合任務調度中的混合迭代模型，以開發(fā)時間和開發(fā)成本為目標，研究任務時間不確定下的優(yōu)化問題.

1 基于六點模糊數的不確定條件下任務完工時間的描述

在產品開發(fā)過程中處理任務執(zhí)行時間不確定問題時，項目管理者一般都是先用三點估計法[10]或區(qū)間數表示法[11]將其轉換為確定性的優(yōu)化問題，再進行求解.

三點估計法和區(qū)間數表示法得到的結果與實際產品開發(fā)的結果相比誤差較大.因此人們引入模糊數來表示任務的完工時間.模糊數的表示方法有多種，目前在實際工程項目上運用較多的有三角模糊數、梯形模糊數和六點模糊數.六點模糊數所包含的信息較多，隸屬度函數圖復雜，能精確地反映不確定信息，分析結果與實際情況往往差異較小.因此，本文采用六點模糊數來表示任務完工時間的不確定.

根據文獻[12]，設為一個模糊數，={(x，u(x))|x∈R}，其中u(x)為的隸屬度函數.給定任意一個數a∈[0，1]能得到M~={x|u(x)≥a}，稱為模糊集的a水平集.六點模糊數)是一個分階段性模糊數表示任務估計最小完工時間表示任務估計最大完工時間.區(qū)間內為任務完工工期最有可能的取值.區(qū)間為任務完工工期可能性較大的取值，λ表示可能性系數.可以由企業(yè)指定較好的水平集來代表不確定的數據.若u(x)=1，表示指定的變量x必然屬于集合.

現用變量x表示任務估計完工的時間，其完工工期的不確定性用六點模糊數表示;u(x)表示任務完工工期的各種可能性程度，其隸屬度函數圖和隸屬度函數分別如圖1和式(1)所示.

圖1 六點模糊數的隸屬函數圖

為了判斷工期長短及優(yōu)化過程的作用，需要比較相應的六點模糊數的大小.通過積分法推導出六點模糊數的清晰化函數，并將清晰化函數的值定義為六點模糊數的度量指標[13]，見式(2).通過比較相應六點模糊數的度量指標來比較其大小.

在產品開發(fā)過程中，每個任務都有一個完工時間的模糊工期，并且六點模糊數所對應的6個變量可以根據企業(yè)以往產品數據及工程師的開發(fā)經驗給出大概估計，集合6個可能的完工工期估計值即可構成一個模糊數來表示一個任務的執(zhí)行工期.

2 混合迭代下多目標優(yōu)化模型的建立

2.1 產品開發(fā)中任務調度混合迭代模型

產品開發(fā)過程中任務迭代的方式和執(zhí)行關系可分為并行迭代、串行迭代和混合迭代.在并行迭代中資源有限的條件下，不能同時完成執(zhí)行;而在串行迭代中，所有任務按順序執(zhí)行，產品總周期大大延長;混合迭代結合了并行迭代和串行迭代的優(yōu)缺點，根據任務間依賴強度關系將任務劃分為一個個任務集，即任務分布方案，然后根據任務分布方案來分階段地執(zhí)行任務，該迭代方式可減小不必要的迭代，減小總工作量和產品工期.

根據文獻[14]，定義一個工作列向量u，其n個子向量分別表示n個相應任務所需要完成的工作量;ui表示第i次迭代時相關任務所需要做的工作量，假設任務的迭代方式為并行迭代，則每個任務初始都需要完全執(zhí)行，因此初始工作向量u0的子向量全部為1.由此可推得每次迭代所有任務相應的工作量為:

式中:A為相應任務間的返工量矩陣.

則并行迭代條件下，設整個產品開發(fā)過程中每個任務的工作總量為列向量U，其為每次迭代相應任務的工作量求和，即:

式中:N為總的迭代次數，根據文獻[15]，當N→∞時，如果矩陣A的最大特征值小于1，則:

設完成每個任務所需要消耗的時間總量為列向量G，則:

式中:W為任務工期矩陣.

根據任務分布方案，將所有任務分成多個階段來執(zhí)行，引入任務分布矩陣Ki.Ki為主對角線矩陣，其對角線上的元素為1或0，用來控制任務是否執(zhí)行.首先執(zhí)行第1階段的任務，然后執(zhí)行第1階段的返工和第2階段的初始任務，以此類推直到所有階段的任務全部執(zhí)行.將任務分布矩陣代入式(6)得混合迭代條件下各個階段完成相應任務所需要消耗的時間總量列向量Gi:

式中:m為總的階段數，任務分布矩陣Km的定義為:

2.2 混合迭代下多目標優(yōu)化模型的建立

2.2.1 優(yōu)化目標的確定

對于產品的開發(fā)工期，每個迭代階段內任務集是并行執(zhí)行的，其耗費的時間是相應迭代階段內所用時間最長的任務所耗費的時間.用T表示產品的開發(fā)工期，并可以將計算得到的總工期T用六點模糊數表示為，則有:

對于產品開發(fā)成本，本文用整個產品設計開發(fā)過程中所需要做的總工作量來衡量產品的開發(fā)成本.而產品開發(fā)的工作總量是所有迭代階段中每個任務的工作量總和.根據2.1節(jié)可以得到產品的開發(fā)成本C，并且可以將計算得到的總成本用六點模糊數表示為，則有:

2.2.2 評價函數構造

為了獲得產品開發(fā)時間和開發(fā)成本的最優(yōu)調度方案，本文采用六點模糊數來表示任務的完工時間和成本，并引入權重系數ω.假設工期和成本的權重系數分別為ω1和ω2，ω1+ω2=1，ω1≥0、ω2≥0，其值可由企業(yè)決策者根據實際產品開發(fā)中的情況來選擇.優(yōu)化后的工期為，成本為，由于工期與成本單位不同，因此用對工期T和成本C做無量綱化處理.用Q來表示產品開發(fā)優(yōu)化后結果的可信度，則定義:

2.2.3 優(yōu)化模型的建立

對企業(yè)來說，要提高自身市場競爭力，就必須縮短產品開發(fā)工期和減少開發(fā)成本，但實際上一般很難存在兩個指標都同時達到最優(yōu)的任務調度方案.因此產品開發(fā)任務的調度問題屬于多目標優(yōu)化問題.

以任務分布方案即矩陣Km(m=1，2，3，…，n)為設計變量，假設不考慮資源約束的問題，在任務執(zhí)行工期不確定的條件下，基于模糊理論的混合迭代下多目標優(yōu)化模型可以描述為:

式中:n為總任務數;N為總迭代次數;m為劃分的階段數;g為1～n階段任務之和;qi為第i階段任務的個數，1≤qi＜n且qi∈Z.

3 多目標優(yōu)化模型的算法求解步驟

改進型非支配排序遺傳算法(NSGA-Ⅱ)[16]采用染色體交叉和變異操作，保留優(yōu)良個體的特性，淘汰適應度較低的染色體，從而可以對問題進行優(yōu)化求解.基于NSGA-Ⅱ的多目標優(yōu)化算法求解的流程如圖2所示.其中n為迭代步數;N為累計的迭代步數.

圖2 遺傳算法的實現過程

Step 1:隨機生成一定數量的目標染色體，并將染色體I的長度設為n，I=[λ1，λ2，…，λi].其中，i為總的任務數，λ的數值表示對應任務所在的執(zhí)行階段.例如一條染色體的編碼為[2，3，1，5，3，2]，編碼位上的數值最大為5，表示該過程一共分5個執(zhí)行階段，任務1和任務6在第2階段執(zhí)行.任務2和任務5在第3階段執(zhí)行.不同編碼的染色體聚集形成初始種群Pn，始種群構成一組混合迭代下的任務分布方案，其需要滿足兩個條件:

①每條染色體的編碼位上的數值需涵蓋1，2，…，S的所有數，保證不存在缺失階段造成任務分布方案失效的情況;

②每條染色體的編碼位上的數值排序不能相同，以保證不存在重復的染色體即相同的任務分布方案，導致增大計算工作量.

Step 2:種群中的每條染色體都有一個適應度，而適應度值是由非支配等級和擁擠度這兩部分來決定的[17].通過非支配排序和擁擠度計算后，可以定義其適應度并由此選擇較好的任務分布方案，本文定義算法的適應度函數為:

Step 3:從初始種群中選擇適應度大的個體，按照一定的概率將他們的部分染色體片段相互交換，即交換部分任務執(zhí)行階段數，形成新的個體.例如:隨機選取的交叉位置為第2位和第7位兩個交叉位置，操作方法如下:

得到新的任務執(zhí)行方案A和B:

初始種群或交叉后的種群中出現任務階段數空缺或形成單一階段，對單階段的個體進行剔除，并對階段數空缺的個體進行隨機變異以滿足要求.例如:變異位置為第2位、第4位、第9位和第12位，操作方法如下:

經過交叉變異操作后得到新的任務分布方案，還需要判斷是否滿足條件.

4 實例分析

4.1 問題描述

以某四連桿門座起重機的變幅機構的開發(fā)任務[18]為例，通過利用設計結構矩陣(DSM)對其耦合任務集進行劃分后，該變幅機構開發(fā)過程主要包括8個設計任務:A:象鼻梁設計;B:臂架設計;C:對中小杠桿設計;D:對重設計;E:變幅傳動布置設計;F:變幅電動機設計;G:變幅減速器設計;H:螺桿傳動設計.其相應耦合任務間的返工量如圖3所示.

圖3 變幅機構開發(fā)過程的任務返工量信息

由2.1節(jié)可知，其表示的是相應任務間因耦合關系而造成的不確定條件下各任務的返工量大小，例如表中1行2列的0.3表示的是任務A在任務B之前執(zhí)行，任務B對任務A的結果不滿意或不相容，任務A需要做30%的返工量;表中0表示對應兩任務間沒有耦合關系.則其任務返工量矩陣為:

基于第1節(jié)所描述的不確定條件下任務工期的六點模糊數表示法，根據以往開發(fā)過程的歷史數據及相關人員的設計經驗可初步確定各任務完工時間的六點模糊數，見表1.

表1 任務完工時間的六點模糊數

根據這些信息，以該變幅機構開發(fā)過程的任務分布執(zhí)行方案為變量，并以其開發(fā)成本、開發(fā)工期為優(yōu)化目標，利用NSGA-Ⅱ算法對該實例問題進行求解.

4.2 問題求解

本文以Matlab R2017b軟件為平臺，編寫NSGA-Ⅱ算法程序.算法的初始種群大小設為500，最大迭代步數為50，交叉率為0.8，變異率為0.5，問題的處理及分析過程如下.

4.2.1 任務執(zhí)行階段數的選取

取工期和成本的權重比為1∶1，即σ=0.5.由表1可提取6組模糊工期:

由于該變幅機構一共有8個設計任務，將任務的執(zhí)行階段數依次設置為1、2、3、4、5、6、7、8，分別代入遺傳算法進行運算，在相應的執(zhí)行階段數下分別取其最優(yōu)任務執(zhí)行方案，得到各個模糊工期和模糊成本，見表2.

表2 不同執(zhí)行階段數條件下的優(yōu)化結果

不同階段數的執(zhí)行條件下，算法的收斂曲線如圖4所示.從圖中可以看出該算法均在50代之前收斂，具有較好的收斂特性，求解效率高.

圖4 適應度收斂曲線圖

為了比較各個執(zhí)行階段數條件下優(yōu)化后的模糊工期和模糊成本的大小，采用第1節(jié)所述的積分值法，取λ=0.5，分別求出優(yōu)化后的每組模糊工期和模糊成本的度量指標見表3.

表3 不同執(zhí)行階段數條件下優(yōu)化結果的度量指標

表3中不同任務執(zhí)行階段數條件下，將其優(yōu)化后的模糊工期和模糊成本度量指標進行對比，如圖5所示.

圖5 不同執(zhí)行階段數下優(yōu)化后工期和成本的對比

由圖5可知，隨著任務執(zhí)行階段數的增加，優(yōu)化后的總工期也一直增加，其增加的速率先減小后增大，在階段4～5之間最小;而優(yōu)化后的成本逐漸減少，其減少的速率也是先減小后增大，在階段4～5之間最小.因此管理人員可根據對成本和工期的權重比要求的不同，選擇將所有任務劃分為4個階段執(zhí)行或者劃分為5個階段執(zhí)行.

4.2.2 任務執(zhí)行階段數確定的條件下最優(yōu)任務分布方案的選取

首先定義任務分布方案的執(zhí)行階段數為5，分別將6組模糊工期帶入算法中進行求解，可得6組Pareto解集，如圖6所示，其具體運算結果見表4.

圖6 執(zhí)行階段數為5時模糊工期下的Pareto解集

表4 運算結果

從表4的數據結果中可以看出，各任務的模糊執(zhí)行工期不同將會直接導致其Pareto解集的不同及相應任務分布方案的不同.因此，本文利用六點模糊數來描述每個任務的執(zhí)行工期和成本，將6個點的模糊工期和模糊成本分別代入優(yōu)化模型進行尋優(yōu).從表4的6個任務模糊工期組中各選出兩組任務方案，并從運算結果中提取出兩組任務執(zhí)行方案一致的Pareto解，見表5.

表5 優(yōu)化后的產品開發(fā)方案

表5中任務方案a為(4 4 1 2 5 3 4 5)，表示任務C在第1階段執(zhí)行，任務D在第2階段執(zhí)行，任務F在第3階段執(zhí)行，任務A、任務B和任務G在第4階段并行執(zhí)行，任務E和任務H在第5階段并行執(zhí)行;任務方案b為(4 5 1 2 4 3 4 5)，方案b與方案a的區(qū)別在于任務B和任務E的執(zhí)行階段數的不同，方案b中任務B在第5階段才開始執(zhí)行，而任務E在第4階段就開始執(zhí)行.

為了選取最優(yōu)任務執(zhí)行方案，利用優(yōu)化結果可信度來判斷，則由公式(12)可得優(yōu)化后工期的可信度，見表6.

表6 優(yōu)化后工期的可信度

由表6可得，對比a和b兩種優(yōu)化方案，方案a(4 4 1 2 5 3 4 5)的可信度更好，因此在任務執(zhí)行階段數為5的條件下，選取方案a作為產品開發(fā)的最優(yōu)執(zhí)行方案.

本文兩組任務方案的選取在其Pareto解中靠中間，工期和成本的權重接近1∶1，而在實際的產品設計開發(fā)中，企業(yè)管理人員可以根據對優(yōu)化工期和成本的著重點的不同來從表3的運算結果中選取對應的方案組，最終根據優(yōu)化方案的可信度來選取最優(yōu)任務執(zhí)行方案.

5 結 論

本文對產品設計開發(fā)過程中任務執(zhí)行時間不確定的問題進行了研究，研究表明:

1)通過引用六點模糊數，結合產品開發(fā)中任務調度混合迭代模型，能夠獲得基于模糊理論的混合迭代下多目標優(yōu)化模型，從而減少產品的開發(fā)時間，降低開發(fā)成本.

2)通過引入NSGA-II算法和積分值法，可以有效地解決任務時間不確定下產品開發(fā)多目標優(yōu)化求解問題.

3)為了最大限度減少產品的開發(fā)時間，降低開發(fā)成本，應合理調整工期和成本權重，選擇合適的權重.