基于NSGA-Ⅱ的產(chǎn)品開發(fā)任務(wù)調(diào)度多目標(biāo)優(yōu)化

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

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

0 引言

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

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

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

1 產(chǎn)品開發(fā)任務(wù)調(diào)度的多目標(biāo)優(yōu)化模型建立

1.1 問(wèn)題描述

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

(1)

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

(2)

(3)

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

(4)

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

(5)

(6)

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

(7)

En=

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

(8)

(9)

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

(10)

(11)

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

1.2 以時(shí)間和成本為優(yōu)化目標(biāo)的數(shù)學(xué)模型的建立

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

(12)

式中，P為總的任務(wù)數(shù)；qi為小組i中任務(wù)的個(gè)數(shù)，P>qi≥1且qi∈Z；n為組數(shù)。

2 基于NSGA-Ⅱ的產(chǎn)品開發(fā)任務(wù)調(diào)度的多目標(biāo)優(yōu)化求解

2.1 Pareto進(jìn)化算法求解步驟

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

根據(jù)產(chǎn)品開發(fā)任務(wù)調(diào)度多目標(biāo)優(yōu)化問(wèn)題的特點(diǎn)，NSGA-Ⅱ算法的具體實(shí)施方法如圖1所示。

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

2.1.1染色體的編碼

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

2.1.2交叉和變異操作

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

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

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

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

首先，計(jì)算出Pareto集合中個(gè)體i的第j個(gè)目標(biāo)函數(shù)值所占比重δij：

(13)

式中，fjmax、fjmin分別為目標(biāo)函數(shù)值集合中的第j個(gè)目標(biāo)函數(shù)值的最大值和最小值；fij為個(gè)體i的第j個(gè)目標(biāo)函數(shù)的取值。

其次，對(duì)Pareto集中的每一個(gè)個(gè)體進(jìn)行標(biāo)準(zhǔn)化，得到個(gè)體i的滿意度：

(14)

式中，Ω為Pareto集中的個(gè)體數(shù)。

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

3 仿真測(cè)試與實(shí)例應(yīng)用分析

3.1 算法仿真測(cè)試

為了說(shuō)明該算法的優(yōu)越性，本文采用典型多目標(biāo)測(cè)試函數(shù)中的2個(gè)測(cè)試函數(shù)ZDT1和ZDT2進(jìn)行仿真[15]。

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

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

使用NSGA-Ⅱ計(jì)算ZDT1，仿真結(jié)果如圖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-Ⅱ計(jì)算ZDT2，仿真結(jié)果如圖3所示。

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

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

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

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

3.2 實(shí)例描述

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

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

任務(wù)執(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 任務(wù)調(diào)度方案優(yōu)化

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

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

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

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

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

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

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

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

(15)

其中，w1、w2分別為時(shí)間T和成本E的權(quán)重系數(shù)且w1+w2=1。調(diào)整w1、w2的結(jié)果如表1所示，表1中的方案下方的數(shù)字代表對(duì)應(yīng)任務(wù)所在的執(zhí)行階段，從左至右，對(duì)應(yīng)任務(wù)A到T(共20個(gè)任務(wù))所在的階段，如第一個(gè)數(shù)字3表示任務(wù)A在第3階段執(zhí)行。

表1 多目標(biāo)遺傳算法優(yōu)化的任務(wù)調(diào)度方案

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

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

表2 時(shí)間最短、成本最低、最優(yōu)任務(wù)調(diào)度方案階段號(hào)

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

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

4 結(jié)語(yǔ)

本文在產(chǎn)品開發(fā)任務(wù)調(diào)度混合迭代模型的基礎(chǔ)上，構(gòu)建出產(chǎn)品開發(fā)任務(wù)調(diào)度的多目標(biāo)優(yōu)化數(shù)學(xué)模型，引入NSGA-Ⅱ，以產(chǎn)品的開發(fā)時(shí)間和產(chǎn)品的開發(fā)成本為目標(biāo)函數(shù)，對(duì)產(chǎn)品開發(fā)任務(wù)調(diào)度問(wèn)題進(jìn)行了多目標(biāo)優(yōu)化求解，得到多目標(biāo)優(yōu)化的Pareto前沿(最優(yōu)解)。在此基礎(chǔ)上，結(jié)合模糊優(yōu)選法對(duì)多目標(biāo)優(yōu)化得到的Pareto解集進(jìn)行選優(yōu)，確定了產(chǎn)品開發(fā)任務(wù)調(diào)度的最優(yōu)執(zhí)行方案。