資源約束下產(chǎn)品開發(fā)任務(wù)調(diào)度的多目標(biāo)優(yōu)化

田啟華,黃佳康,明文豪,杜義賢,周祥曼+,付君健

(1.三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院，湖北 宜昌 443002； 2.湖北億緯動(dòng)力有限公司方形三元技術(shù)中心，湖北 荊門 448000)

0 引言

產(chǎn)品開發(fā)的任務(wù)調(diào)度由于受到來自企業(yè)內(nèi)部技術(shù)人員、設(shè)備工具和資金等資源約束，原來可以執(zhí)行的任務(wù)發(fā)生延遲執(zhí)行或不能執(zhí)行，例如技術(shù)人員調(diào)動(dòng)、設(shè)備工具損壞、資金鏈中斷等，都會使產(chǎn)品開發(fā)任務(wù)調(diào)度受到約束。針對資源約束下的任務(wù)調(diào)度問題，國內(nèi)外學(xué)者開展了一些研究，并取得了相應(yīng)的成果。KARA等[1]提出一種多項(xiàng)目調(diào)度啟發(fā)式算法，用于解決資源約束下的多項(xiàng)目調(diào)度問題；秦旋等[2]構(gòu)建了以生產(chǎn)完工時(shí)間和懲罰成本為目標(biāo)的生產(chǎn)調(diào)度數(shù)學(xué)模型，設(shè)計(jì)了一種新穎的多目標(biāo)混合共生生物搜索算法(Multi-Objective Hybrid Symbiotic Organisms Search Algorithm，MOHSOSA)對模型進(jìn)行求解，以合理安排構(gòu)件的生產(chǎn)順序和資源配置，達(dá)到降低成本、提高生產(chǎn)效率的目的；安曉亭等[3]提出一種帶局部搜索的改進(jìn)蟻群優(yōu)化算法，用于求解多目標(biāo)資源受限項(xiàng)目調(diào)度問題；徐賜軍等[4]提出運(yùn)用彈性資源特性進(jìn)行動(dòng)態(tài)調(diào)度決策的方法，以解決產(chǎn)品開發(fā)中的多個(gè)活動(dòng)沖突問題，其主要根據(jù)活動(dòng)間的時(shí)序約束和資源約束特點(diǎn)，分別建立了用以解決時(shí)序沖突、資源沖突的模型，并證明了彈性資源約束動(dòng)態(tài)調(diào)度決策方法的有效性和可行性；CHEN等[5]在EXCEL仿真計(jì)算的基礎(chǔ)上，建立了多維模型(MD模型)，用于評估項(xiàng)目的優(yōu)先級并進(jìn)行計(jì)算，當(dāng)多個(gè)項(xiàng)目的積極效應(yīng)達(dá)到最大，人員能力滿足任務(wù)要求時(shí)，獲得了最佳人力資源配置；徐賜軍等[6]根據(jù)不同的資源約束和強(qiáng)耦合的設(shè)計(jì)活動(dòng)特點(diǎn)，提出一種資源約束的產(chǎn)品開發(fā)過程集成模型；GAO等[7]對于資源受限的項(xiàng)目調(diào)度問題，提出一種改進(jìn)的關(guān)鍵路徑調(diào)度算法；肖人彬等[8]提出一種資源均衡策略的耦合集求解方法，以解決產(chǎn)品開發(fā)中資源約束下的資源分配問題，從而提高了資源的利用率，縮短了產(chǎn)品開發(fā)任務(wù)調(diào)度的迭代時(shí)間；項(xiàng)前等[9]提出一種改進(jìn)的動(dòng)態(tài)差分進(jìn)化參數(shù)控制方法和雙向優(yōu)化問題調(diào)度算法，以解決資源受限的項(xiàng)目調(diào)度問題；王靜等[10]建立了一種求解資源受限項(xiàng)目調(diào)度模型的差分進(jìn)化人工蜂群算法，獲得了約束資源的分布以及資源和項(xiàng)目時(shí)間的優(yōu)化方案；TAHOONEH等[11]采用人工蜂群算法解決隨機(jī)資源約束項(xiàng)目調(diào)度問題，仿真結(jié)果表明該算法能更有效地解決隨機(jī)資源約束項(xiàng)目調(diào)度問題；LIN等[12]構(gòu)建了多資源約束下多項(xiàng)目任務(wù)調(diào)度最短延遲時(shí)間的數(shù)學(xué)模型，根據(jù)資源調(diào)度任務(wù)和項(xiàng)目內(nèi)部時(shí)序關(guān)系，結(jié)合啟發(fā)式算法，解決了多資源約束下的多項(xiàng)目任務(wù)調(diào)度問題。上述文獻(xiàn)從不同方面對資源約束下的任務(wù)調(diào)度問題進(jìn)行了研究，有些針對非耦合設(shè)計(jì)任務(wù)調(diào)度建立的優(yōu)化模型，任務(wù)數(shù)量較少且任務(wù)間的關(guān)系較簡單，不適用于存在大量迭代和返工情況的耦合設(shè)計(jì)任務(wù)調(diào)度優(yōu)化，如文獻(xiàn)[1-6]；有些優(yōu)化目標(biāo)單一，或采用其他方法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為一個(gè)綜合的目標(biāo)，評價(jià)指標(biāo)較單一，如文獻(xiàn)[7-12]；文獻(xiàn)[13]雖然建立了以產(chǎn)品開發(fā)時(shí)間和開發(fā)成本為目標(biāo)的任務(wù)調(diào)度多目標(biāo)優(yōu)化模型，并采用帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ)求解，確定了任務(wù)調(diào)度方案的Pareto最優(yōu)解集，然后采用模糊優(yōu)選法得到最優(yōu)的任務(wù)調(diào)度方案，但是未考慮任務(wù)調(diào)度中存在的資源約束問題。另外，目前對耦合設(shè)計(jì)任務(wù)調(diào)度中客觀存在的學(xué)習(xí)與遺忘效應(yīng)問題的研究較少。

資源約束下的產(chǎn)品開發(fā)任務(wù)調(diào)度，要求在滿足資源約束的條件下合理調(diào)度各項(xiàng)任務(wù)，最大化利用資源，對開發(fā)時(shí)間、開發(fā)成本等多個(gè)目標(biāo)進(jìn)行優(yōu)化。產(chǎn)品開發(fā)中執(zhí)行每項(xiàng)任務(wù)都會占用相應(yīng)的資源(如設(shè)備、人力和資金等)，而且資源一般都是有限的，在執(zhí)行一個(gè)或多個(gè)任務(wù)的同時(shí)啟動(dòng)其他任務(wù)時(shí)，由于當(dāng)前執(zhí)行的任務(wù)占用了一定資源，可能出現(xiàn)某種或某些資源不足的情況，該任務(wù)只能等當(dāng)前任務(wù)執(zhí)行完畢，所需資源釋放后才能開始執(zhí)行，即任務(wù)在執(zhí)行過程中會受到相關(guān)資源約束的影響，導(dǎo)致任務(wù)延后執(zhí)行甚至不能執(zhí)行。因此，需要及時(shí)調(diào)整并優(yōu)化任務(wù)調(diào)度方案，以使任務(wù)在執(zhí)行時(shí)滿足資源約束的條件，盡可能縮短開發(fā)時(shí)間，減少開發(fā)成本[14]。

本文針對產(chǎn)品開發(fā)過程中存在的資源約束問題，結(jié)合多階段耦合集求解模型，考慮任務(wù)執(zhí)行過程中存在的學(xué)習(xí)遺忘效應(yīng)，以開發(fā)時(shí)間和開發(fā)成本為目標(biāo)，研究資源約束下的產(chǎn)品開發(fā)任務(wù)調(diào)度優(yōu)化問題。

1 學(xué)習(xí)遺忘矩陣的構(gòu)建

對于執(zhí)行任務(wù)的小組人員來說，一方面，隨著返工次數(shù)的增加，工作經(jīng)驗(yàn)不斷積累，小組人員的工作能力(或工作效率)逐漸提高，即減少了執(zhí)行同一任務(wù)的時(shí)間；另一方面，由于工作中斷和遺忘而導(dǎo)致經(jīng)驗(yàn)丟失，小組人員的工作能力相比之前會有所降低，即存在學(xué)習(xí)遺忘效應(yīng)[15]。為了研究學(xué)習(xí)遺忘效應(yīng)在迭代過程中對執(zhí)行時(shí)間和成本的影響，本文將學(xué)習(xí)曲線與遺忘曲線相結(jié)合進(jìn)行研究。

假設(shè)t(1)為某一任務(wù)小組第一次執(zhí)行任務(wù)所需的時(shí)間，t(p)為第p次返工執(zhí)行同一任務(wù)所需的時(shí)間，結(jié)合WRIGHT[16]提出的學(xué)習(xí)效率曲線，可得

t(p)=t(1)×p-l。

(1)

式中l(wèi)為學(xué)習(xí)效率指數(shù)，0≤l<1，l取值越大學(xué)習(xí)能力越強(qiáng)，特別是l=0時(shí)表示沒有學(xué)習(xí)效應(yīng)。學(xué)習(xí)效率指數(shù)可采用同類工作的經(jīng)驗(yàn)和歷史數(shù)據(jù)，通過學(xué)習(xí)效率曲線確定。由式(1)可知，隨著返工次數(shù)p的增加，完成同一任務(wù)所需的時(shí)間t(p)減小，但WRIGHT[16]指出學(xué)習(xí)效率曲線存在一個(gè)下界，即執(zhí)行時(shí)間不可能無限減小。

同時(shí)，遺忘效應(yīng)也是客觀存在的，由于經(jīng)驗(yàn)被遺忘丟失，完成單位工作量所需的時(shí)間會增加。假設(shè)在第b次返工時(shí)，學(xué)習(xí)發(fā)生了中斷(經(jīng)驗(yàn)遺忘丟失)，t′(a)為某一任務(wù)小組第a次執(zhí)行任務(wù)所需的時(shí)間，t′(b)為學(xué)習(xí)中斷時(shí)第b次返工執(zhí)行同一任務(wù)所需的時(shí)間，結(jié)合文獻(xiàn)[17]，可得遺忘效應(yīng)曲線

t′(b)=t′(a)×(b-a)f,b>a。

(2)

式中:f為遺忘效應(yīng)指數(shù)，0≤f<1，f取值越小遺忘能力越小，特別f=0時(shí)表示沒有遺忘效應(yīng)。遺忘效應(yīng)指數(shù)同樣可采用同類工作的經(jīng)驗(yàn)和歷史數(shù)據(jù)，并通過遺忘效率曲線確定。由式(2)可知，隨著返工次數(shù)b的增加，執(zhí)行同一任務(wù)的時(shí)間t'(b)在增加，但遺忘效率曲線同樣存在一個(gè)上界，即執(zhí)行時(shí)間不可能無限增加。

對于一個(gè)有m個(gè)任務(wù)的串行耦合集，m個(gè)任務(wù)對應(yīng)的每個(gè)小組第s次返工的學(xué)習(xí)效應(yīng)矩陣L(s)與遺忘效應(yīng)矩陣F(s)分別為:

式中s1,s2,…,sm分別為存在學(xué)習(xí)效應(yīng)和遺忘效應(yīng)時(shí)對應(yīng)任務(wù)的返工量。

一般而言，學(xué)習(xí)和遺忘是一個(gè)概率事件，在任務(wù)執(zhí)行過程中，人員的工作能力可能因?qū)W習(xí)效應(yīng)而提高，也可能因外部的擾動(dòng)、工作中斷等遺忘效應(yīng)而降低。在后續(xù)的返工迭代中，根據(jù)概率規(guī)則，每次隨機(jī)生成一個(gè)0～1之間的數(shù)pd，當(dāng)pd不大于某一λ值時(shí)會產(chǎn)生學(xué)習(xí)效應(yīng)，否則會產(chǎn)生遺忘效應(yīng)。綜合考慮學(xué)習(xí)效應(yīng)和遺忘效應(yīng)，第s次返工中的學(xué)習(xí)遺忘矩陣為：

(3)

2 多階段任務(wù)執(zhí)行時(shí)間與成本的計(jì)算模型

將產(chǎn)品開發(fā)過程中的m個(gè)任務(wù)劃分為n(n>2)個(gè)階段執(zhí)行，每個(gè)階段至少執(zhí)行一個(gè)任務(wù)，而且只有當(dāng)上個(gè)階段的所有任務(wù)執(zhí)行完后，下個(gè)階段的任務(wù)才能開始執(zhí)行。任務(wù)執(zhí)行中存在迭代返工，用工作轉(zhuǎn)移矩陣WTM(可簡寫為W)定量表示任務(wù)的返工量，W通常包括兩部分?jǐn)?shù)值信息，即由兩個(gè)獨(dú)立的數(shù)值矩陣(任務(wù)工期矩陣Z和任務(wù)返工量矩陣R)組成[18]，工作轉(zhuǎn)移矩陣W=Z+R。其中：Z為m維對角矩陣，其元素表示該項(xiàng)任務(wù)對應(yīng)的執(zhí)行時(shí)間，其值取決于產(chǎn)品開發(fā)前專家根據(jù)經(jīng)驗(yàn)對每個(gè)設(shè)計(jì)任務(wù)時(shí)間的估計(jì)值；R為m維非對角矩陣，元素rij表示任務(wù)j完成后引起任務(wù)i的返工量，描述迭代過程中任務(wù)之間的耦合關(guān)系。例如一個(gè)有關(guān)3個(gè)耦合設(shè)計(jì)任務(wù)A，B，C的執(zhí)行工期矩陣Z和任務(wù)返工量R分別為：

Z矩陣表示任務(wù)A，B，C獨(dú)立完成一次分別需要7，6，9個(gè)單位時(shí)間。R矩陣表示任務(wù)A執(zhí)行結(jié)束后，由于任務(wù)A，B，C之間存在耦合關(guān)系，導(dǎo)致任務(wù)B需要重做30%的工作(返工量)，任務(wù)C需要重做15%的工作；當(dāng)任務(wù)B完成后，任務(wù)A需要重做25%的工作，任務(wù)C需要重做50%的工作；當(dāng)任務(wù)C完成后，任務(wù)A需要重做40%的工作，任務(wù)B不用重做。

由文獻(xiàn)[19]并結(jié)合學(xué)習(xí)和遺忘矩陣可以得出，將m個(gè)任務(wù)分為n個(gè)階段，在執(zhí)行第1階段任務(wù)的過程中，完成時(shí)間最長的任務(wù)所需的時(shí)間T1和所有任務(wù)的開發(fā)成本D1分別為：

D1=Etc[QK1(Z(I-K1RdK1)(I-K1RK1)-1K1u0)]。

執(zhí)行第2階段任務(wù)所需的時(shí)間T2和成本D2分別為：

D2=Etc[QK2(Z(I-K2RdK2)

(I-K2RK2)-1(K2-K1)u0)]。

以此類推，執(zhí)行第n階段任務(wù)所需的時(shí)間Tn和成本Dn分別為：

(4)

Dn=Etc[QKn(Z(I-KnRdKn)
(I-KnRKn)-1(Kn-Kn-1)u0)]。

(5)

執(zhí)行完m個(gè)任務(wù)所需的總時(shí)間T和總成本D分別為：

(6)

3 多目標(biāo)優(yōu)化模型的建立

3.1 資源利用率的定義

機(jī)械產(chǎn)品開發(fā)涉及的工種較多，需要多部門協(xié)作和跨學(xué)科交流，隨著設(shè)計(jì)任務(wù)數(shù)量的增加，對資源的數(shù)量需求和種類需求更多，為了方便計(jì)算并進(jìn)行仿真，假設(shè)：①每個(gè)任務(wù)執(zhí)行時(shí)所需的資源為一個(gè)確定的值；②總的資源一定；③任務(wù)執(zhí)行完后，所占用的資源立即全部釋放。

當(dāng)任務(wù)的階段數(shù)確定后，每個(gè)階段由于執(zhí)行的任務(wù)不同，所需的資源數(shù)量也不一樣。有的階段并行執(zhí)行的任務(wù)數(shù)量較多，資源一般能夠被充分利用，甚至可能超過總的資源量，導(dǎo)致有些任務(wù)不能執(zhí)行或延遲執(zhí)行；有的階段并行執(zhí)行的任務(wù)數(shù)量較少，通常造成資源大量閑置。為了體現(xiàn)任務(wù)執(zhí)行過程中資源的利用率，假設(shè)任務(wù){(diào)A1，A2，…，Am}所需的資源不可分割(每個(gè)任務(wù)只有分配一定數(shù)量的資源才能執(zhí)行)，定義資源分配行向量Zy=(Zy1,Zy2, …,Zyn)，資源總量為Zyzl(確定值)，即每個(gè)任務(wù)執(zhí)行時(shí)需要的資源量為一定值，而且每個(gè)階段只有當(dāng)該階段的全部任務(wù)所需的資源總和小于或等于資源總量Zyzl時(shí)，任務(wù)才能并行執(zhí)行。定義資源的利用率：

第1階段資源的利用率

Z1=‖K1×Zy1‖/Zyzl×100%；

第2階段資源的利用率

Z2=‖(K2-K1)Zy2‖/Zyzl×100%；

以此類推，第n階段資源的利用率

Zn=‖(Kn-Kn-1)Zyn‖/Zyzl×100%。

(7)

由于每個(gè)階段執(zhí)行的任務(wù)不同，資源利用率的差異可能相差較大，設(shè)計(jì)人員或決策者往往對總資源利用率的期望值較高，而不是某一階段的資源利用率最高，對此提出資源平均利用率

(8)

3.2 評價(jià)函數(shù)的構(gòu)造

為了獲得產(chǎn)品開發(fā)時(shí)間和開發(fā)成本的最優(yōu)調(diào)度方案，本文采用多目標(biāo)理想點(diǎn)法[20]對求得的Pareto最優(yōu)解集進(jìn)行選優(yōu)，該方法在期望度量下，尋求離G*最近的G作為近似值(該優(yōu)化模型需先分別求出每個(gè)目標(biāo)的最小值)。如圖1所示，圖中：“*”為目標(biāo)g1和目標(biāo)g2的理想點(diǎn)，即兩個(gè)目標(biāo)同時(shí)達(dá)到最小值；“+”和“△”為目標(biāo)g1和目標(biāo)g2的實(shí)際分布點(diǎn)，顯然“△”代表的值比“+”代表的值都大，只需在“+”中尋找距離“*”最近的點(diǎn)，構(gòu)造評價(jià)函數(shù)G，

(9)

3.3 多目標(biāo)模型的建立

在產(chǎn)品開發(fā)設(shè)計(jì)過程中，一般總資源有限，設(shè)計(jì)人員或決策者會根據(jù)以往的設(shè)計(jì)經(jīng)驗(yàn)給每個(gè)任務(wù)分配固定的資源，只要每個(gè)階段所需的資源不超過總量，該階段的任務(wù)即可順利進(jìn)行，因此資源約束條件為

(10)

產(chǎn)品開發(fā)時(shí)間T和開發(fā)成本D均為評價(jià)任務(wù)調(diào)度方案優(yōu)劣的兩個(gè)重要指標(biāo)，一般很難有兩個(gè)指標(biāo)同時(shí)達(dá)到最優(yōu)的任務(wù)調(diào)度方案，因此資源約束下的產(chǎn)品開發(fā)任務(wù)調(diào)度問題屬于多目標(biāo)優(yōu)化問題。

由于時(shí)間和成本在單位、數(shù)量級的差別，本文通過(T-Tmin)/(Tmax-Tmin)和(D-Dmin)/(Dmax-Dmin)分別對T和D進(jìn)行無量綱化處理，其中：Tmin為時(shí)間最小值，Tmax為時(shí)間最大值；Dmin為成本最小值，Dmax為成本最大值。為了體現(xiàn)企業(yè)決策者對時(shí)間或成本的重視和偏好程度，本文在多目標(biāo)理想點(diǎn)法的基礎(chǔ)上引入權(quán)重系數(shù)w。假設(shè)時(shí)間和成本的權(quán)重系數(shù)分別為w1，w2，滿足w1≥0，w2≥0且w1+w2=1，其值可由企業(yè)決策者根據(jù)實(shí)際產(chǎn)品開發(fā)中的具體情況選擇。引入式(10)的約束條件后，資源約束下產(chǎn)品開發(fā)任務(wù)調(diào)度多目標(biāo)優(yōu)化的數(shù)學(xué)模型描述如下：

s.t.

(11)

其中：目標(biāo)函數(shù)的個(gè)數(shù)為2；m為總?cè)蝿?wù)數(shù)，n為劃分的階段數(shù)，qi為第i階段任務(wù)的個(gè)數(shù)，v為1～n階段任務(wù)數(shù)之和；1

4 多目標(biāo)優(yōu)化模型的求解

4.1 NSGA-II的改進(jìn)

有別于傳統(tǒng)的搜索算法，遺傳算法在求解組合優(yōu)化領(lǐng)域的非確定性多項(xiàng)式(Non-deterministic Polynomial，NP)問題上顯示出強(qiáng)大的搜索優(yōu)勢。其中非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm，NSGA)[21]能夠根據(jù)個(gè)體之間的支配和非支配關(guān)系分層實(shí)現(xiàn)優(yōu)化，雖然其求解得到的非劣最優(yōu)解分布均勻，但是計(jì)算復(fù)雜度高，無精英策略，而且對共享參數(shù)的依賴性較大；NSGA-II[22-23]采用快速非支配排序方法，引入擁擠距離保證Pareto解集的均勻性和多樣性，降低了算法的時(shí)間復(fù)雜性，而且?guī)в芯⒉呗?，在進(jìn)化過程中不會丟失最優(yōu)解，比NSGA算法更優(yōu)越，已應(yīng)用于許多工程優(yōu)化設(shè)計(jì)問題[24]，但在產(chǎn)品開發(fā)任務(wù)調(diào)度方面應(yīng)用較少。鑒于此，本文基于NSGA-II對產(chǎn)品開發(fā)任務(wù)調(diào)度問題中的時(shí)間和成本進(jìn)行多目標(biāo)優(yōu)化，根據(jù)執(zhí)行時(shí)間和成本計(jì)算個(gè)體的非支配排序和擁擠距離，以保證Pareto最優(yōu)解集的均勻性和多樣性。

NSGA-II雖然優(yōu)點(diǎn)較多，但是容易陷入“早熟”(即快速收斂到局部最優(yōu)解而不是全局最優(yōu)解)，而且在接近最優(yōu)解時(shí)收斂速度較慢。根據(jù)文獻(xiàn)[25]，交叉概率Pc和變異概率Pm是影響算法收斂性的主要原因。一方面，Pc越大，新個(gè)體的產(chǎn)生速度越快，但Pc太大時(shí)遺傳模式被破壞的可能性較大(適應(yīng)度較高的個(gè)體結(jié)構(gòu)很快就被破壞)，而當(dāng)Pc太小時(shí)，新個(gè)體產(chǎn)生的速度太慢，甚至停滯不前；另一方面，Pm越小，產(chǎn)生新個(gè)體的難度越大，當(dāng)其值過大時(shí)，遺傳算法就變成了純粹的隨機(jī)搜索算法。不同的優(yōu)化求解問題需多次反復(fù)實(shí)驗(yàn)確定Pc和Pm的值，這種操作既復(fù)雜，又難以獲得適應(yīng)每個(gè)問題的最佳數(shù)值，考慮到動(dòng)態(tài)自適應(yīng)技術(shù)的優(yōu)越性，本文采用自適應(yīng)遺傳算法，根據(jù)個(gè)體的適應(yīng)度值動(dòng)態(tài)調(diào)整Pc和Pm，當(dāng)種群適應(yīng)度值比較分散時(shí)適當(dāng)減小Pc和Pm，而當(dāng)種群個(gè)體適應(yīng)度值趨于一致時(shí)適當(dāng)增加Pc和Pm。同時(shí)，對適應(yīng)度值低于群體平均適應(yīng)度值的個(gè)體采用較高的Pc和Pm，對適應(yīng)度值高于群體平均適應(yīng)度值的個(gè)體采用較小的Pc和Pm。因此，采用自適應(yīng)的Pc與Pm可以提供相對某個(gè)解的最佳Pc和Pm，確保算法的收斂性和種群的多樣性，具體計(jì)算如下：

(12)

(13)

式中：fmax為種群中個(gè)體最大的適應(yīng)度值；favg為每代群體的平均適應(yīng)度值；f′為交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；f為變異個(gè)體的適應(yīng)度值。

利用改進(jìn)的NSGA-II求解時(shí)間、成本的最大值和最小值，并進(jìn)行多次計(jì)算，以減少算法的隨機(jī)性，盡可能找到全局最優(yōu)解。

4.2 算法的求解步驟

設(shè)開發(fā)某產(chǎn)品時(shí)共有m個(gè)任務(wù)，將所有任務(wù)劃分為n個(gè)階段執(zhí)行(m≥n)，則任務(wù)調(diào)度方案數(shù)約為nm。復(fù)雜的產(chǎn)品開發(fā)涉及的m，n一般較大，若采用傳統(tǒng)的枚舉法或啟發(fā)式算法，則搜索空間太大，時(shí)間消耗過大，且難得到全局最優(yōu)解。遺傳算法采用染色體交叉和變異操作，能夠保留優(yōu)良個(gè)體的特性，淘汰適應(yīng)度較低的染色體，從而對問題進(jìn)行優(yōu)化求解?；谧赃m應(yīng)交叉和變異概率的遺傳算法優(yōu)化流程如圖2所示。

步驟1隨機(jī)生成一定數(shù)量染色體(個(gè)體)，采用十進(jìn)制編碼，每個(gè)編碼位表示對應(yīng)任務(wù)所在的階段數(shù)，如染色體{3,2,1,2,2,1}，表示任務(wù)3，6處于第1階段，任務(wù)2，4，5處于第2階段，任務(wù)1處于第3階段。假設(shè)任務(wù)數(shù)為6，階段數(shù)劃分為3，初始種群數(shù)為100，則個(gè)體在MATLAB中生成的代碼為Chrom=3ceil(rand(100,6))。每個(gè)階段數(shù)都要出現(xiàn)在染色體的編碼位上，淘汰沒有出現(xiàn)所有階段數(shù)字的染色體(或稱個(gè)體)，調(diào)用相應(yīng)函數(shù)，判斷生成的染色體是否符合約束條件(對生成的染色體進(jìn)行判斷選擇)。

步驟2將符合約束條件的染色體計(jì)算轉(zhuǎn)換為開發(fā)時(shí)間和開發(fā)成本的綜合目標(biāo)評價(jià)函數(shù)G，并得出適應(yīng)度。最小化問題適應(yīng)度函數(shù)取目標(biāo)函數(shù)的倒數(shù)1/G，適應(yīng)度函數(shù)根據(jù)目標(biāo)函數(shù)值的大小區(qū)分群體中個(gè)體的優(yōu)劣(適應(yīng)度函數(shù)是算法演化過程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一依據(jù)(保留適應(yīng)度值較大的個(gè)體))。

步驟3選擇適應(yīng)度較大的兩個(gè)個(gè)體作為父本，將其進(jìn)行交叉變異操作得到新的染色體，判斷是否滿足約束條件，滿足則執(zhí)行步驟4，否則轉(zhuǎn)步驟1。

步驟4計(jì)算符合約束條件新染色體的適應(yīng)度大小。循環(huán)執(zhí)行，直到滿足終止條件，輸出最優(yōu)任務(wù)調(diào)度方案。

5 實(shí)例分析

5.1 問題描述

以某電動(dòng)小汽車產(chǎn)品的開發(fā)過程[26]為例，該設(shè)計(jì)項(xiàng)目包括多個(gè)設(shè)計(jì)任務(wù)，簡化處理后得到一個(gè)由8個(gè)設(shè)計(jì)任務(wù)組成的耦合集，如圖3所示，包括：任務(wù)0-1(大小與動(dòng)力特性)、任務(wù)0-2(馬達(dá)規(guī)格與重量)、任務(wù)0-3(整體重量)、任務(wù)0-4(存儲能量需求)、任務(wù)0-5(電池大小與重量)、任務(wù)0-6(速度與加速度比率)、任務(wù)0-7(速度與加速度規(guī)格)、任務(wù)0-8(結(jié)構(gòu)與支撐設(shè)計(jì))。圖中：對角線元素為對應(yīng)任務(wù)執(zhí)行工期的中點(diǎn)值，非對角線元素為任務(wù)的返工量，空白處均為0；0～1之間的數(shù)值元素值表示任務(wù)的返工量，其值越大表示耦合關(guān)系越強(qiáng)，返工量越多，例如第1列第2行數(shù)字0.15，表示完成任務(wù)0-1后，任務(wù)0-2的返工量為15%(相對上一次工作量)。根據(jù)以往經(jīng)驗(yàn)，從0-1～0-8每個(gè)任務(wù)對應(yīng)的資源為5，3，3，4，2，4，3，6個(gè)單位資源，即Zy=[5,3,3,4,2,4,3,6]，總資源Zyzl=15。

由圖3可得返工量矩R陣和任務(wù)工期矩陣Z:

Z=diag(8,6,4,3,3,6,3,5)。

5.2 任務(wù)調(diào)度方案優(yōu)化

在不考慮學(xué)習(xí)與遺忘效應(yīng)(即學(xué)習(xí)遺忘矩陣Q為單位矩陣)時(shí)，根據(jù)各階段的任務(wù)執(zhí)行時(shí)間和成本的計(jì)算模型(6)，在資源約束下對電動(dòng)汽車中的耦合設(shè)計(jì)任務(wù)調(diào)度進(jìn)行階段劃分，求解該耦合設(shè)計(jì)任務(wù)的調(diào)度問題。按照本文提出的整數(shù)編碼方式，耦合集中的任務(wù)個(gè)數(shù)為8，則個(gè)體的編碼長度為8。為了確定該耦合集的任務(wù)劃分為多少階段會出現(xiàn)最優(yōu)任務(wù)調(diào)度方案，將任務(wù)的階段數(shù)分別劃分為2，3，4，5，6，7，8，采用MATLAB進(jìn)行多次試算[25]，確定的相關(guān)參數(shù)如下：初始種群數(shù)量p=500，遺傳迭代步數(shù)g=50，初始染色體交叉概率Pc=0.8，變異概率Pm=0.1。采用改進(jìn)的NSGA-II尋找各階段的最優(yōu)解，用式(6)和(9)求解，分別得到各階段的時(shí)間最小值、成本最小值及其對應(yīng)的任務(wù)調(diào)度方案，如表1所示。

為了更加直觀地表示時(shí)間、成本隨著階段數(shù)增加的變化趨勢，采用MATLAB軟件，得到表1不同階段的最小時(shí)間優(yōu)化圖和最小成本優(yōu)化圖，分別如圖4和圖5所示。

表1 各階段任務(wù)調(diào)度方案

顯然，任務(wù)劃分的階段數(shù)越多，由每個(gè)階段執(zhí)行的任務(wù)數(shù)量相對越少，所需的資源也相對越少，此時(shí)資源充足，資源的利用率相對較低。若階段數(shù)劃分得太少，則開發(fā)成本較大；若階段數(shù)劃分得較多，則開發(fā)時(shí)間較長。由圖4和圖5可見，隨著階段數(shù)的增加，時(shí)間增加，成本下降，Pareto解的開發(fā)時(shí)間和成本大體成反比，不存在時(shí)間和成本同時(shí)最小的情況，說明同時(shí)優(yōu)化時(shí)間和成本兩個(gè)目標(biāo)存在矛盾，即減少開發(fā)時(shí)間會增加開發(fā)成本，減少開發(fā)成本會延長開發(fā)時(shí)間，設(shè)計(jì)人員或決策者可以根據(jù)要求確定時(shí)間或成本可接受的范圍，選擇合適的任務(wù)調(diào)度方案。

在不考慮學(xué)習(xí)與遺忘效應(yīng)的情況下，用改進(jìn)的NSGA-II求解資源約束下的多目標(biāo)優(yōu)化模型(11)，得到所有方案的時(shí)間、成本Pareto解集，并計(jì)算平均時(shí)間為43.93 d，平均成本為87.9(d·人)，平均資源利用率為40%；再對所有方案的時(shí)間和成本進(jìn)行非支配排序[13]，得到任務(wù)調(diào)度方案時(shí)間、成本的Pareto最優(yōu)解集(如表2)；取權(quán)重系數(shù)w1=w2=0.5，采用改進(jìn)的多目標(biāo)理想點(diǎn)法對該解集進(jìn)行選優(yōu)(如圖6)，計(jì)算獲得最優(yōu)任務(wù)調(diào)度方案對應(yīng)的編碼為{34211214}(企業(yè)決策者也可根據(jù)實(shí)際情況在Pareto解集中權(quán)衡選擇)，即任務(wù)0-4、任務(wù)0-5、任務(wù)0-7處于第1階段，任務(wù)0-3、任務(wù)0-6處于第2階段，任務(wù)0-1處于第3階段，任務(wù)0-2、任務(wù)0-8處于第4階段，此時(shí)所需的時(shí)間T=32.93 d，成本為76.51(d·人)，利用式(8)得到該方案資源的平均利用率為50%。

表2 改進(jìn)的NSGA-Ⅱ優(yōu)化任務(wù)調(diào)度方案的時(shí)間、成本Pareto最優(yōu)解集

針對只考慮學(xué)習(xí)效應(yīng)、同時(shí)考慮學(xué)習(xí)和遺忘效應(yīng)兩種情況，采用以上相同的初始參數(shù)，采用改進(jìn)的NSGA-Ⅱ和改進(jìn)的多目標(biāo)理想點(diǎn)法，分別得到相應(yīng)任務(wù)調(diào)度方案的時(shí)間、成本Pareto最優(yōu)解集和優(yōu)選解。表3所示為不考慮學(xué)習(xí)和遺忘效應(yīng)、只考慮學(xué)習(xí)效應(yīng)、同時(shí)考慮學(xué)習(xí)和遺忘效應(yīng)時(shí)的時(shí)間、成本優(yōu)化結(jié)果及其比較。

表3 只考慮學(xué)習(xí)效應(yīng)以及學(xué)習(xí)和遺忘效應(yīng)時(shí)的時(shí)間、成本優(yōu)化結(jié)果及其比較

為了比較不同學(xué)習(xí)指數(shù)l、遺忘指數(shù)f和學(xué)習(xí)概率λ對優(yōu)化結(jié)果的影響，將任務(wù)的階段數(shù)設(shè)置為8，采用控制變量法得到的結(jié)果和比較如表4所示。

表4 同時(shí)考慮學(xué)習(xí)與遺忘效應(yīng)時(shí)不同l，f，

5.3 結(jié)果分析

用改進(jìn)的NSGA-II求解本文建立的資源約束下的多目標(biāo)優(yōu)化模型，得到所有方案時(shí)間、成本的Pareto解集，再對所有方案的時(shí)間和成本進(jìn)行非支配排序，得到方案時(shí)間、成本的Pareto最優(yōu)解集，采用多目標(biāo)理想點(diǎn)法對該解集進(jìn)行選優(yōu)，得到最優(yōu)調(diào)度方案所需的時(shí)間T=32.93 d，成本為76.51 (d·人)，資源的平均利用率為50%，相比Pareto解集的平均時(shí)間43.93 d、成本87.09(d·人)和平均資源利用率40%，時(shí)間和成本分別縮短了25.04%，12.15%，資源利用率提高了25%。說明本文優(yōu)化方法是有效的。

從表3可見，相對于不考慮學(xué)習(xí)和遺忘效應(yīng)，只考慮學(xué)習(xí)效應(yīng)或同時(shí)考慮學(xué)習(xí)和遺忘效應(yīng)的產(chǎn)品開發(fā)時(shí)間分別減少6.2%，4.2%，成本分別降低7.2%，5.1%；相對同時(shí)考慮學(xué)習(xí)和遺忘效應(yīng)，只考慮學(xué)習(xí)效應(yīng)的產(chǎn)品開發(fā)時(shí)間減少2%，成本降低2.4%。說明只考慮學(xué)習(xí)效應(yīng)或同時(shí)考慮學(xué)習(xí)和遺忘效應(yīng)，均可減少產(chǎn)品開發(fā)時(shí)間并降低開發(fā)成本，但只考慮學(xué)習(xí)效應(yīng)時(shí)產(chǎn)品開發(fā)時(shí)間和成本的優(yōu)化效果更為顯著。

由表4可知，當(dāng)遺忘指數(shù)f和學(xué)習(xí)概率λ不變，學(xué)習(xí)指數(shù)l較大，或者l與λ不變，f較小，或者f和l不變，λ較大時(shí)，產(chǎn)品開發(fā)時(shí)間較少，開發(fā)成本較低；當(dāng)λ不變，f較小，l較大，或者f不變，l和λ均較大，或者l不變，f較小，λ較大時(shí)，產(chǎn)品開發(fā)時(shí)間較少，開發(fā)成本較低。說明l，f，λ均對資源約束下的產(chǎn)品開發(fā)時(shí)間和成本有直接影響，其中l(wèi)，λ較大或f較小，均可減少產(chǎn)品開發(fā)時(shí)間，降低開發(fā)成本。

6 結(jié)束語

在產(chǎn)品設(shè)計(jì)開發(fā)任務(wù)調(diào)度中同時(shí)考慮資源約束問題和學(xué)習(xí)與遺忘效應(yīng)更加科學(xué)，綜合考慮多個(gè)目標(biāo)的優(yōu)化更符合實(shí)際。本文對資源約束下考慮學(xué)習(xí)和遺忘效應(yīng)的產(chǎn)品開發(fā)任務(wù)調(diào)度的時(shí)間和成本優(yōu)化進(jìn)行研究，結(jié)果表明：

(1)通過定義資源利用率，構(gòu)建學(xué)習(xí)與遺忘效應(yīng)矩陣，結(jié)合產(chǎn)品開發(fā)任務(wù)調(diào)度的多階段迭代模型，建立資源約束下任務(wù)調(diào)度的多目標(biāo)優(yōu)化數(shù)學(xué)模型，能夠減少產(chǎn)品開發(fā)時(shí)間，降低開發(fā)成本，提高總資源利用率。

(2)通過引入自適應(yīng)交叉概率和變異概率而改進(jìn)的NSGA-Ⅱ和引入權(quán)重系數(shù)而改進(jìn)的多目標(biāo)理想點(diǎn)法，可以有效解決資源約束下的任務(wù)調(diào)度優(yōu)化求解問題。

(3)為最大限度地減少產(chǎn)品開發(fā)時(shí)間，降低開發(fā)成本，應(yīng)盡量提高工作人員的學(xué)習(xí)能力，減少遺忘效應(yīng)。另外，量化分析學(xué)習(xí)和遺忘效應(yīng)，建立考慮學(xué)習(xí)和遺忘效應(yīng)的優(yōu)化模型，有助于指導(dǎo)產(chǎn)品設(shè)計(jì)開發(fā)過程，對產(chǎn)品設(shè)計(jì)開發(fā)的時(shí)間和成本進(jìn)行預(yù)測。