田啟華 明文豪 文小勇 杜義賢 周祥曼

1.三峽大學機械與動力學院，宜昌，443002 2.湖北江山重工有限責任公司民品事業(yè)部，襄陽，441100

0 引言

產品開發(fā)是一個求解實現產品功能、滿足各種技術和經濟指標，從可能存在的所有方案中確定綜合最優(yōu)方案的過程。隨著市場競爭的日益激烈和科學技術的發(fā)展，人們對產品開發(fā)的要求越來越高，產品開發(fā)變得日益復雜。設計任務間的耦合性使設計過程出現反復和迭代，延長開發(fā)時間，增加開發(fā)成本。耦合設計任務的開發(fā)時間和開發(fā)成本與任務調度有直接關系，子任務的執(zhí)行順序會引起后續(xù)子任務不同的返工量，故需合理安排每個子任務開始執(zhí)行的時間。任務調度研究的問題是確定項目的子任務、安排任務進度、編制完成任務所需的資源預算等，目的在于保證產品開發(fā)能夠在合理的工期內，以盡可能低的成本和盡可能高的質量完成[1]。

近年來，圍繞產品開發(fā)任務調度問題的研究逐漸受到重視，并取得了一些研究成果。CHEN等[2]將量化搜索算法用于解決多個虛擬企業(yè)協(xié)同下的設計任務調度問題；武照云等[3]采用加權系數法和極差變換法建立了產品開發(fā)任務分配多目標優(yōu)化的目標函數，采用基于時序邏輯關系的動態(tài)分配蟻群算法進行優(yōu)化計算；蔣增強等[4]提出了基于多目標優(yōu)化的產品協(xié)同開發(fā)任務調度理論，根據企業(yè)對產品開發(fā)的時間、成本及質量重視程度，確定三者各自的權重，以三者的加權指數和為多目標優(yōu)化函數，得出最優(yōu)的任務調度方案。加權系數法雖然可以在很大程度上降低求解問題的難度，但只能得到一個Pareto解，而且實際應用中的權重系數確定完全依賴于專家，主觀依賴性較強。陳庭貴等[5-6]將產品開發(fā)的成本和時間單獨考慮，獲得了最優(yōu)成本和最優(yōu)時間的任務分布方案，但沒有考慮成本與時間共同優(yōu)化的矛盾性和競爭性。田啟華等[7]采用約束法，將產品開發(fā)的成本作為一個主要的優(yōu)化目標，給產品的質量和開發(fā)時間設定一個上下界(當作約束條件)，對問題進行了優(yōu)化求解。這種處理可以降低求解問題的難度，但本質上相當于單目標優(yōu)化，且主要優(yōu)化目標取決于決策者的喜好。田啟華等[8]、楊利宏等[9]將傳統(tǒng)的遺傳算法引入到產品開發(fā)任務分配的優(yōu)化，以時間為優(yōu)化目標，但沒有考慮任務分配對開發(fā)成本的影響，優(yōu)化的目標函數不夠完善。

遺傳算法作為一種有別于傳統(tǒng)的搜索算法，在求解組合優(yōu)化領域的非確定性多項式(non-deterministic polynomial，NP)問題上顯示出強大的搜索優(yōu)勢[9]。非支配排序遺傳算法[10](non-dominated sorting genetic algorithm，NSGA)根據個體之間的支配和非支配關系分層實現，采用它求解得到的非劣最優(yōu)解分布均勻，但其計算復雜度高，無精英策略，并且對共享參數的依賴性較大，而改進的非支配排序遺傳算法(non-dominated sorting genetic algorithm-Ⅱ，NSGA-Ⅱ)[11-12]采用快速非支配排序方法，引入擁擠距離保證Pareto解集的均勻性和多樣性，降低了算法的時間復雜性，且?guī)в芯⒉呗裕谶M化過程中不會造成最優(yōu)解的丟失，NSGA-Ⅱ算法比NSGA算法更加優(yōu)越。多目標遺傳算法在許多工程優(yōu)化設計問題中都有運用[13]，但在產品開發(fā)任務調度方面應用較少。鑒于此，本文基于NSGA-Ⅱ對產品開發(fā)任務調度問題中的時間和成本進行多目標優(yōu)化，根據執(zhí)行時間和成本對個體進行非支配排序和擁擠距離的計算，以保證Pareto最優(yōu)解集的均勻性和多樣性，從而最終得到最優(yōu)的任務調度方案。

1 產品開發(fā)任務調度的多目標優(yōu)化模型建立

1.1 問題描述

產品開發(fā)任務的調度對開發(fā)的時間和成本有很大影響，因此需要對任務進行合理調度。一般來說，產品開發(fā)任務調度是一個混合迭代過程。一個有P個任務、n(n>2)個階段的混合迭代模型的工作過程描述如下[6]：將P個任務分成n個工作小組；首先，第一階段執(zhí)行第一個小組的任務；然后，第二階段執(zhí)行第二個小組的任務和第一小組任務的返工，此時只有第二個小組的任務有初始工作；第三階段執(zhí)行第三個小組的任務和第一、二小組任務的返工；以此類推，經過n個階段，直到第n個小組的任務全部執(zhí)行完畢，并完成前面n-1個小組的返工。完成當前階段的小組任務后，前面小組的返工都會在當前階段完成。第一階段任務執(zhí)行所需時間T1和成本E1分別為

(1)

E1=‖W(I-K1AM1K1)(I-K1AK1)-1K1u0‖1

(2)

(3)

第二階段任務執(zhí)行所需時間T2和成本E2：

(4)

E2=‖W(I-K2AM2K2)(I-K2AK2)-1(K2-K1)u0‖1

(5)

(6)

依此類推，第n階段任務執(zhí)行所需時間和成本：

(7)

En=

‖W(I-KnAMnKn)(I-KnAKn)-1(Kn-Kn-1)u0‖1

(8)

(9)

P個任務執(zhí)行完畢所需總時間T和總成本E分別為

(10)

(11)

從以上的模型可以看出，任務之間的耦合關系和每個任務的執(zhí)行周期確定后，影響產品開發(fā)過程的總時間T和總成本E的因素只有任務的調度方案。

1.2 以時間和成本為優(yōu)化目標的數學模型的建立

在任務工期確定和不考慮資源約束的條件下，產品開發(fā)任務調度問題多目標優(yōu)化的目標為總開發(fā)時間T最短、總開發(fā)成本E最低，約束條件如下：

(12)

式中，P為總的任務數；qi為小組i中任務的個數，P>qi≥1且qi∈Z；n為組數。

2 基于NSGA-Ⅱ的產品開發(fā)任務調度的多目標優(yōu)化求解

2.1 Pareto進化算法求解步驟

基于NSGA-Ⅱ算法的產品開發(fā)任務調度問題多目標優(yōu)化的一般步驟如下：首先，生成大量的不同任務調度方案，計算出它們所需的執(zhí)行時間和成本，淘汰其中時間和成本均較大的方案；其次，根據不同的執(zhí)行時間和成本，對保留下來的任務分布方案進行非支配排序和擁擠距離計算；再次，根據個體的序值和擁擠距離選出父本，進行交叉變異運算，得出新的任務分布方案，并計算出時間和成本；最后，將新生成的任務分布方案與之前保留的任務分布方案進行非支配排序和擁擠距離計算，以保證Pareto解的多樣性和均勻性。以此類推，直至達到最大的遺傳代數，輸出Pareto最優(yōu)前沿。

根據產品開發(fā)任務調度多目標優(yōu)化問題的特點，NSGA-Ⅱ算法的具體實施方法如圖1所示。

圖1 基于NSGA-Ⅱ算法的流程圖Fig.1 Flow chart based on NSGA-Ⅱ algorithm

2.1.1染色體的編碼

產品開發(fā)任務調度混合迭代模型中，任務劃分的階段數和任務的分布情況是影響時間和成本的重要因素，所以在選擇染色體的編碼方式時，個體的階段數和任務的分布情況是要突出表現的特征。本文采用整數編碼的方法，以問題解{x1,x2,…,xN}的編碼形式表示染色體(或稱個體)，各編碼位是整數，xN對應任務N，xN的值表示任務N所在的階段。假設當前任務劃分的階段數為n，用1到n之間的一個正整數來表示任務所在的階段，染色體中每個編碼位取值為1、2、...、n中的一個，不同的數字代表該任務處在不同階段，且染色體的編碼位上共有n個不同的取值，染色體的長度由耦合集中任務的個數N決定(n≤N)。染色體{1,1,3,2,2,1,3,4,2,1,3}表示由11個任務的耦合集所構成的四階段混合迭代模型的一種任務調度情況，其中，從左至右的第1、2、6、10個位置的數值為1，這表示任務1、2、6、10屬于第1階段，以此類推，任務4、5、9屬于第2階段，任務3、7、11屬于第3階段，任務8屬于第4階段。染色體編碼方式確定以后，不同的任務分配有唯一的染色體與之對應，每一個染色體都對應著一個產品開發(fā)任務調度方案。

2.1.2交叉和變異操作

運用二元錦標賽選擇的方法，從種群中選出適應性較高的個體加入交配池，為后續(xù)的交叉和變異做準備。根據以上的染色體編碼方式，設計與之對應的交叉變異操作。以2個個體的交叉為例，首先，從經過選擇操作得到的新種群中隨機選擇2個父本P1和P2，假設這2個父本的染色體有m個基因位，將交叉操作分兩步進行：①在染色體上隨機產生2個交叉的位置r1和r2(r1、r2∈{1，2，…，m})；②將P1和P2上兩個交叉位置r1、r2間的基因互換，生成2個子個體O1和O2。多階段模型中，每個任務所在的階段必須確定，且每個階段至少分配到一個任務，這些要求在染色體上的表現如下：對于一個染色體(染色體最大編碼數為n)，從1到n的每個數字都要出現在染色體中，即任務的階段數保持連續(xù)。對染色體交叉操作的過程中，可能出現某些階段的基因缺失。多階段模型出現某階段基因缺失，將導致迭代無法進行或出現錯誤。針對這個問題采用以下的方法予以修正：在子個體中用遺失的基因替換非交叉區(qū)的重復基因。例如，父本P1={1,3,1,3,1,2}、P2={1,2,2,1,1,3}交叉的位置點r1=4，r2=6，則生成子個體O1={1,3,1,1,1,3}、O2={1,2,2,3,1,2 }，由于子個體O1缺少階段數2，故O1修正為{2,3,1,1,1,3}，而O2不用修正。

多階段迭代模型可以在個體的染色體上隨機選擇2個基因的位置，然后互換這2個位置上的基因作為變異操作。具體過程是選擇一個父本P3，在P3的染色體上隨機產生2個不同位置點r3和r4，互換兩位置上的基因，生成子個體O3。

2.2 Pareto最優(yōu)解的選取

為了便于產品開發(fā)決策者從眾多任務方案中確定產品開發(fā)的最優(yōu)執(zhí)行方案，本文基于模糊優(yōu)選法[14]，對NSGA-Ⅱ求得的多目標優(yōu)化問題的Pareto最優(yōu)解集進行優(yōu)化，確定最優(yōu)折中解。建立Pareto集優(yōu)選的過程如下。

首先，計算出Pareto集合中個體i的第j個目標函數值所占比重δij：

(13)

式中，fjmax、fjmin分別為目標函數值集合中的第j個目標函數值的最大值和最小值；fij為個體i的第j個目標函數的取值。

其次，對Pareto集中的每一個個體進行標準化，得到個體i的滿意度：

(14)

式中，Ω為Pareto集中的個體數。

最后，取標準化后滿意度最大的個體的滿意度δimax作為Pareto集中的最優(yōu)解，其中，δmax=maxδi。

3 仿真測試與實例應用分析

3.1 算法仿真測試

為了說明該算法的優(yōu)越性，本文采用典型多目標測試函數中的2個測試函數ZDT1和ZDT2進行仿真[15]。

參數設置如下：種群數量p=100，遺傳迭代步數g=150，交叉概率pc=0.9，變異概率為0.1。

(1)ZDT1具有凸的Pareto最優(yōu)前沿：

使用NSGA-Ⅱ計算ZDT1，仿真結果如圖2所示。

圖2 使用NSGA-Ⅱ求解ZDT1Fig.2 Solving the ZDT1 with NSGA-Ⅱ

(2)ZDT2具有非凸的Pareto最優(yōu)前沿：

minf1(x)=x1

minf2(x)=g(x)*[1-(f1(x)/g(x))2]

使用NSGA-Ⅱ計算ZDT2，仿真結果如圖3所示。

圖3 使用NSGA-Ⅱ求解ZDT2圖Fig.3 Solving the ZDT2 with NSGA-Ⅱ

分別對比圖2和圖4、圖3和圖5可知，使用NSGA-Ⅱ得到的結果大致與ZDT1、ZDT2的理想Pareto前沿重合，且得到了分布均勻的最優(yōu)解集。因此，可以得出本算法對于求解兩目標優(yōu)化效率高、性能好的結論。

圖4 ZDT1理想Pareto前沿Fig.4 Ideal Pareto front of ZDT1

圖5 ZDT1理想Pareto前沿圖Fig.5 Ideal Pareto Front of ZDT2

3.2 實例描述

以某汽車引擎罩部件的設計開發(fā)過程為例說明上述模型在實際生產中的應用，并驗證該方法的有效性。文獻[16]使用設計結構矩陣對該開發(fā)過程進行建模，在劃分、割裂運算后，找出眾多子任務中的耦合集(包括由20個和14個子任務組成的大耦合塊、由3個任務組成的小耦合塊)，本文選擇由20個子任務組成的耦合塊進行分析。

由該20個任務間的耦合信息可得任務返工量矩陣A和任務執(zhí)行周期矩陣W；根據任務間的依賴強度確定任務的返工量，例如當任務D設計完成后，在隨后的迭代階段，任務J的26%(對應矩陣A中第四列數據0.26)需要額外的返工；矩陣A空白位置的元素取值均為0。

任務執(zhí)行周期矩陣W為

W=diag(15，60，40，40，15，2，1，5，30，1，1，5，5，10，20，5，2，2，15，5)

A B C D E F G H I J K L M N O P Q R S T

3.3 任務調度方案優(yōu)化

按照本文給出的多階段混合迭代模型，以執(zhí)行時間最短、成本最低為目標，以任務的分布方案為設計變量，在滿足階段劃分的約束條件的前提下，對汽車引擎罩開發(fā)任務調度的多目標優(yōu)化問題進行求解，得到該問題的Pareto前沿(最優(yōu)解)。按照前面提出的整數編碼的規(guī)則，由耦合集的任務個數20，確定染色體的長度為20，假設耦合集中的任務被劃分成n個階段，染色體上的每個編碼位用1～n的自然數表示。該自然數表示任務通過隨機組合的方式得到的初始種群，交叉和變異運算按照本文給出的方法操作。為了確定算法的具體參數并說明不同參數對優(yōu)化結果的影響，利用MATLAB進行了多次試算，確定了相關參數的大致范圍。將任務的階段數確定為13，采用控制變量法，每次改變種群數量、遺傳迭代步數和交叉概率三者中的一個，可得初始種群數量對優(yōu)化結果的影響，見圖6。圖中，d*p表示天*人。對比可知，初始種群較大時，獲得的Pareto解多，且分布相對均勻；遺傳迭代步數對優(yōu)化結果的影響見圖7，對比可知，迭代步數較小時，Pareto最優(yōu)解相對比較集中，容易造成最優(yōu)解的丟失；染色體交叉概率分別設置為0.5、0.7和0.9，求解結果見圖8，對比可知，染色體交叉概率對優(yōu)化結果影響很小，在0.5～0.9范圍內均可。分析圖6、圖7可知，當種群數量、遺傳迭代步數足夠大時，可得到穩(wěn)定且分布均勻的Pareto最優(yōu)前沿，但種群規(guī)模太大時，結果難以收斂且浪費資源，遺傳迭代步數太小，算法不易收斂；步數太大，算法已經熟練或種群過于早熟，繼續(xù)進化沒有意義，因此這兩個參數可以根據具體問題進行調整。

圖6 種群數量對優(yōu)化結果的影響(g=100,pc=0.9)Fig.6 Influences of population size on theoptimized result(g=100,pc=0.9)

圖7 遺傳迭代步數對優(yōu)化結果的影響(p=1 000,pc=0.9)Fig.7 Influences of Genetic iteration steps on the optimized result(p=1 000,pc=0.9)

NSGA-Ⅱ的參數經過反復試算，設置如下：初始種群P0中個體的數目p=1 000，遺傳迭代步數g=100，染色體交叉概率為0.9，染色體變異概率為0.1。圖9所示為利用MATLAB進行多目標優(yōu)化仿真的結果，由于事先不能確定任務劃分為多少階段，時間和成本才會出現綜合最優(yōu)，所以把1～20階段每次運行MATLAB得到的優(yōu)化結果保存下來，并對時間T(單位：天，用d表示)和成本E兩個優(yōu)化目標進行非支配排序，獲得的Pareto前沿結果。

圖8 染色體交叉概率對優(yōu)化結果的影響(p=1 000,g=100)Fig.8 Influences of chromosome crossover probability on the optimized result(p=1 000,g=100)

圖9 多目標優(yōu)化的Pareto前沿Fig.9 Pareto front of multi-objective optimization

由圖9以看出， NSGA-Ⅱ計算出的Pareto解分布均勻，大體上可以看出Pareto解的開發(fā)周期和成本成反比的關系。這說明了產品的開發(fā)時間、開發(fā)成本這兩個目標的矛盾性。圖9中的所有點構成了Pareto最優(yōu)集合，可以看出，AB段內，時間的變很小化就會引起成本的很大變化；CD段內，成本的很小變化就會引起時間的很大變化，它們都不是很好的選擇。因此決策者可以根據實際情況從BC段集合內進行權衡，獲得時間和成本都能接受的產品開發(fā)任務調度方案。

為了說明本文算法的優(yōu)越性，采用常規(guī)的多目標遺傳算法進行比較，選擇相同的初始參數，先分別求出時間和成本的最小值、最大值，使用MATLAB仿真求得Tmin=97.10 d，Tmax=297.84 d，Emin=315.44 d*p，Emax=473.10 d*p，量綱一化后的綜合目標函數為

(15)

其中，w1、w2分別為時間T和成本E的權重系數且w1+w2=1。調整w1、w2的結果如表1所示，表1中的方案下方的數字代表對應任務所在的執(zhí)行階段，從左至右，對應任務A到T(共20個任務)所在的階段，如第一個數字3表示任務A在第3階段執(zhí)行。

表1 多目標遺傳算法優(yōu)化的任務調度方案

使用常規(guī)的多目標遺傳算法求解該問題時，結果依賴于評價函數的選擇，每次只能得到一種任務調度方案，無非支配排序和精英保留制，進化過程可能會造成最優(yōu)解的丟失，可供選擇的方案較少；采用NSGA-Ⅱ算法，一次運行就能得到多種方案，有精英保留制，不會造成最優(yōu)解的丟失，該算法的收斂性和魯棒性好，產品開發(fā)決策者可以根據實際情況或偏好目標選擇最優(yōu)的任務調度方案。

現根據2.2節(jié)提出的模糊集合優(yōu)選的方法進行產品開發(fā)過程任務調度多目標優(yōu)化的Pareto選優(yōu)，得到最優(yōu)的任務調度方案見表2，表2分別給出了時間最短、成本最低、時間和成本綜合最優(yōu)的任務分布方案，以及所有解的平均時間T和平均成本E。由表2可以看出，最優(yōu)任務分布方案的時間和成本比Pareto解的平均時間149.47 d，成本358.09 d*p都小，說明了該算法的有效性。

表2 時間最短、成本最低、最優(yōu)任務調度方案階段號

由表2知，時間和成本綜合最優(yōu)的任務分布方案是將20個任務分成了6個階段，分別是：第1階段執(zhí)行的任務是內外觀的確定(R)；第2階段執(zhí)行的任務是進行概念設計(F)、系統(tǒng)尺寸估計(J)、成本估計(K)、工藝評估(T)；第3階段執(zhí)行的任務是CAD建模(G)；第4階段執(zhí)行的任務是確定傳動系統(tǒng)布置(A)、確定主截面(D)、檢驗功能性質(H)、檢查外部面板的接觸面(N)、設計鉸鏈(O)；第5階段執(zhí)行的任務是初始裝配方案設計(L)；第6階段執(zhí)行的任務是確定比例與受力性能(B)、確定連接點的受力性能(C)、產生結構要求(E)、CAD模型進行初始設計(I)、估計銷的載重(M)、初步估計加工和裝配成本(P)、成本分析(Q)、市場定位及分析(S)。最優(yōu)方案如圖10所示，圖中，對角線元素為對應任務的執(zhí)行周期，非對角線元素為對應任務的返工量，任務從左到右依次執(zhí)行，相同階段的任務用同一種顏色表示，可以清楚看到每個階段增加的新任務，以及新任務和之前執(zhí)行的任務的返工情況。

圖10 優(yōu)方案的任務分布圖Fig.10 Task distribution of the optimal solution

4 結語

本文在產品開發(fā)任務調度混合迭代模型的基礎上，構建出產品開發(fā)任務調度的多目標優(yōu)化數學模型，引入NSGA-Ⅱ，以產品的開發(fā)時間和產品的開發(fā)成本為目標函數，對產品開發(fā)任務調度問題進行了多目標優(yōu)化求解，得到多目標優(yōu)化的Pareto前沿(最優(yōu)解)。在此基礎上，結合模糊優(yōu)選法對多目標優(yōu)化得到的Pareto解集進行選優(yōu)，確定了產品開發(fā)任務調度的最優(yōu)執(zhí)行方案。