基于遺傳分層序列法的云制造資源優(yōu)化配置

汪勇,徐瓊,張凌,王靜

(武漢科技大學(xué)管理學(xué)院,武漢430081)

基于遺傳分層序列法的云制造資源優(yōu)化配置

汪勇,徐瓊,張凌,王靜

(武漢科技大學(xué)管理學(xué)院,武漢430081)

文章針對分層序列法和非支配排序遺傳算法在求解多目標(biāo)決策問題時(shí)的不足,結(jié)合遺傳算法和分層序列法的優(yōu)勢,提出一種遺傳分層序列多目標(biāo)決策方法。設(shè)計(jì)遺傳分層序列法的分層目標(biāo)、遺傳策略和原目標(biāo)無量綱化處理方法?？紤]運(yùn)輸時(shí)間因素,以制造完成時(shí)間最短和制造成本最低為目標(biāo),建立多制造任務(wù)資源分配模型,并設(shè)計(jì)一種基于時(shí)間矩陣的多制造任務(wù)完成時(shí)間計(jì)算方法。實(shí)驗(yàn)表明,應(yīng)用遺傳分層序列法進(jìn)行多制造任務(wù)資源優(yōu)化配置時(shí),效果優(yōu)于標(biāo)準(zhǔn)遺傳算法和非支配排序遺傳算法,可以滿足決策者的不同決策偏好。

云制造;資源分配;多目標(biāo)決策;遺傳分層序列法

0 引言

隨著互聯(lián)網(wǎng)、云計(jì)算和物聯(lián)網(wǎng)等技術(shù)的迅猛發(fā)展,云制造[1]已成為學(xué)界和業(yè)界關(guān)注的熱點(diǎn)。云制造資源分配是一個多目標(biāo)優(yōu)化問題,國內(nèi)外學(xué)者提出了不同的網(wǎng)絡(luò)化制造資源分配模型?？紤]交貨期和成本等因素,朱金達(dá)等提出了聯(lián)盟企業(yè)多目標(biāo)任務(wù)分配的數(shù)學(xué)模型[2]。彭建剛等以最小化最大完工時(shí)間、機(jī)器總負(fù)荷和最大機(jī)器負(fù)荷為目標(biāo),研究柔性作業(yè)車間調(diào)度問題[3]。面向多任務(wù)制造,為使生產(chǎn)計(jì)劃合理、高效和優(yōu)化,Manupati等構(gòu)建了多任務(wù)過程計(jì)劃選擇模型[4]和基于產(chǎn)品和企業(yè)重要性分級的生產(chǎn)計(jì)劃任務(wù)分解分配模型[5]。

多目標(biāo)問題通常采用指派法、分層序列法、貝葉斯矩陣[6]和智能優(yōu)化方法求解。由于云制造涉及的企業(yè)和資源種類不同,任務(wù)復(fù)雜,導(dǎo)致資源優(yōu)化配置方案巨大。面對云制造資源分配的實(shí)時(shí)性要求,本文結(jié)合分層序列法的優(yōu)勢,設(shè)計(jì)一種快速的多目標(biāo)遺傳算法,以滿足決策者的不同決策偏好。

1 遺傳分層序列法

1.1 目標(biāo)設(shè)計(jì)

分層序列法是多目標(biāo)決策的一種方法,其本質(zhì)是按一個原始目標(biāo)選擇若干可行解,再按另一目標(biāo)縮小可行解的范圍,直至所有目標(biāo)分析完成為止。分層序列法不適合求解具有巨型解空間的多目標(biāo)決策問題。在分層序列法和遺傳算法基礎(chǔ)上,本文設(shè)計(jì)另一種多目標(biāo)決策方法,即遺傳分層序列法(GLM)。該方法有兩個分層序列目標(biāo),第一層目標(biāo)是原始目標(biāo)值之和,第二層目標(biāo)是原始目標(biāo)的離差均值。設(shè)某多目標(biāo)決策問題有n個目標(biāo),且要求所有目標(biāo)最小化,則第一層目標(biāo)可表示為:

原始目標(biāo)量綱不同,直接相加缺乏語義,且目標(biāo)之和最小往往并非最優(yōu)解。假設(shè)決策者設(shè)置的原始目標(biāo)寬容值為Fi,i=1,2,…,n,采用基準(zhǔn)法對原始目標(biāo)進(jìn)行無量綱化處理得:

公式(2)計(jì)算遺傳分層序列法的第一層目標(biāo),同時(shí)也作為遺傳算法的適應(yīng)度函數(shù)。z1越小,表示該決策方案至少有一個目標(biāo)較優(yōu),但目標(biāo)整體性能不一定最優(yōu),需要進(jìn)一步考察原始目標(biāo)的離散程度。原始目標(biāo)的離差均值可以區(qū)分決策方案的優(yōu)劣,故采用離差均值作為遺傳分層序列法的第二層目標(biāo)計(jì)算方法。假設(shè)有m個可行方案,則各方案的離差均值為:

z2越小,表示決策方案的原始目標(biāo)值較為均衡,目標(biāo)整體性能較好。z2越大,表示該決策方案原始目標(biāo)中至少存在一個較優(yōu)目標(biāo)。根據(jù)決策者的偏好,選擇z2決策原則。

1.2 遺傳策略設(shè)計(jì)

假設(shè)每代的制造資源分配方案為N個,選擇、交叉和變異概率分別為ps,pc和pm。

(1)選擇策略

根據(jù)公式(2),將z1升序排列,從小到大間隔選擇N×ps個方案組成第t代的選擇方案集Xs(t),顯然,Xs(t)包含精英個體。

(2)交叉策略

隨機(jī)選擇N×pc個不相同的方案作為交叉?zhèn)€體,依次兩兩順序配對,采用多點(diǎn)等位交叉,得到交叉?zhèn)€體集Xc(t)。

(3)變異策略

隨機(jī)選擇N×pm個不相同的方案作為變異個體,多點(diǎn)變異,得到變異個體集Xm(t)。則第t+1代種群X(t+1)=Xs(t)∪Xc(t)∪Xm(t)。

選擇策略保證優(yōu)良基因得意延續(xù),交叉和變異策略確保種群個體多樣性,避免算法陷入局部最優(yōu)。

1.3 GLM算法流程

針對一組決策方案,按公式(2)計(jì)算第一層目標(biāo)值并保存本代最優(yōu)方案。通過遺傳操作獲得新的種群,重復(fù)上述步驟,直到滿足終止條件為止。按公式(3)比較各代最優(yōu)方案的離差均值,根據(jù)決策者偏好,選擇多目標(biāo)決策的最優(yōu)方案。算法流程見圖1。終止條件一般設(shè)定為最大進(jìn)化代數(shù)。

圖1 GLM算法流程

2 多制造任務(wù)資源分配模型

2.1 問題描述

多制造任務(wù)是指共享云制造平臺或企業(yè)專有云制造平臺接收不同產(chǎn)品的制造任務(wù),且這些任務(wù)的部分工序使用相同的制造資源,每個任務(wù)的批量進(jìn)行整體資源分配。設(shè)有m個處于不同地域的企業(yè),共有n類資源,每個企業(yè)擁有的資源數(shù)量、單位加工時(shí)間和單位加工成本分別為q,PT和PC。企業(yè)間的運(yùn)輸時(shí)間為DT?，F(xiàn)有k個訂單需要加工,批量分別為b1,b2,…,bk,任務(wù)i的工藝路線為Ri= [ri1,ri2,…,rip(i)],ria表示任務(wù)i第a道工序,工序數(shù)值與資源編號對應(yīng)。任務(wù)i的工藝路線共有p(i)道工序組成。PTia, PCia分別表示任務(wù)i第a道工序的單位加工時(shí)間和單位加工成本,DTia表示任務(wù)i從第a-1道工序運(yùn)輸?shù)降赼道工序的時(shí)間,WTia為任務(wù)i到達(dá)第a道工序時(shí)的等待加工時(shí)間。

若為任務(wù)i(1≤i≤k)的每道工序分配擁有相應(yīng)資源的生產(chǎn)企業(yè),按照工序順序構(gòu)成的企業(yè)集合就是任務(wù)i的資源分配方案Xi,Xi=[Xi1,Xi2,…,Xip(i)],則完成所有任務(wù)的資源分配方案X={X1,X2,…,Xk}。設(shè)每個任務(wù)的加工完成的時(shí)間分別為T1,T2,…,Tk,完成所有任務(wù)的加工成本為C。在滿足資源數(shù)量約束和資源不沖突的條件下,尋找一個最優(yōu)方案X,使得完成所有加工任務(wù)的時(shí)間T最短且加工成本C最低,見公式(4)和公式(5)。

公式(5)和公式(6)表示在每組方案的最大完成時(shí)間中的最小值。Ti(Xi)表示任務(wù)i完成所有工序加工的單位時(shí)間,p(i)表示任務(wù)i的工序數(shù)。SDi(a-1)表示第a-1道工序的完成時(shí)間,也就是第a道工序的開始運(yùn)輸時(shí)間。令SDi0=0,即從0時(shí)刻開始計(jì)時(shí)。

2.2 約束條件

(1)設(shè)任務(wù)i第a道工序需要資源ra,ra∈R,分配的企業(yè)為Xia,1≤Xia≤m,q(Xia,ra)表示企業(yè)Xia擁有資源ra的數(shù)量,則:

(2)任務(wù)i第a道工序只能分配給一個企業(yè)加工,即在同一工序,任務(wù)不再拆分。設(shè)任務(wù)i第a道工序分配的企業(yè)為Xia,Xia?E,E表示可分配的企業(yè),則:

(3)多任務(wù)一次性同時(shí)分配資源,即方案X的模為k。

(4)多個任務(wù)分配同一企業(yè)的同類資源,則按先到先加工原則進(jìn)行分配。設(shè)任務(wù)i第a道工序與任務(wù)j第c道工序分配到同一企業(yè)的相同資源,若任務(wù)j先到達(dá),且SDj(c-1)+ DTjc+PTjc≥SDi(a-1)+DTia,則任務(wù)i第a道工序的等待時(shí)間為:

(5)資源數(shù)量q和任務(wù)批量bi為正整數(shù),N表示正整數(shù)集合。

2.3 多制造任務(wù)完成時(shí)間計(jì)算

由于每個任務(wù)的每道工序可能存在資源沖突,可以按照任務(wù)優(yōu)先級、短工時(shí)優(yōu)先和先到先分配的原則處理資源沖突。先到先分配是通過比較任務(wù)的運(yùn)輸?shù)竭_(dá)時(shí)間判斷是否需要等待。k個任務(wù)的工藝路線可表示為集合R=

L(i)表示任務(wù)i之前所有任務(wù)的工藝路線長度之和。若Xia表示分配給任務(wù)i第a道工序的制造企業(yè),1≤Xia≤m, m為企業(yè)數(shù),則資源分配方案記為X=[X11,X12,…,X1p(1);X21, X22,…,X2p(2);…;Xk1,Xk2,…,Xkp(k)]。

按照先到先分配原則,各任務(wù)制造完成時(shí)間計(jì)算步驟如下:

(1)構(gòu)造進(jìn)度矩陣S

設(shè)v=MaX(p(1),p(2),…,p(k)),v表示所有任務(wù)中的最大工序數(shù)。則進(jìn)度矩陣為:

S的每行表示一個任務(wù)各工序的開始運(yùn)輸時(shí)間(SD)、到達(dá)時(shí)間(ED)、開始加工時(shí)間(SP)和加工完成時(shí)間(EP),S的每列表示各任務(wù)某個狀態(tài)的時(shí)間值。

(2)初始化S

設(shè)所有任務(wù)起始運(yùn)輸時(shí)間相同,即第一道工序的SD= 0。不考慮等待時(shí)間,對于方案X,按照各任務(wù)工序間的運(yùn)輸時(shí)間DT和加工時(shí)間PT,分別計(jì)算各任務(wù)的SD,ED,SP和EP。不足最大工序數(shù)的任務(wù),其余列設(shè)置為0。

(3)令FT=[EP11,EP12,…,EP1p(1),EP21,EP22,…,EP2p(2),…, EPk1,EPk2,…,EPkp(k)]。EPij表示各任務(wù)各工序的加工完成時(shí)間,j=1,2,…,p(i)。FT初值為0,表示該資源未被使用,非0數(shù)值表示資源已被分配,其值表示資源釋放時(shí)間。

(4)更新進(jìn)度矩陣

①從S的第j列開始(j初值為2),查找第j列[ED1j; ED2j;…;EDkj]中非0的最小EDij,EDij對應(yīng)的是任務(wù)i的第+1道工序的到達(dá)時(shí)間,EDij=S(i,j)。任務(wù)i的第+1道工序的資源,分配的企業(yè)

②查找R中與res相同的資源,若為空,表示不存在相同的資源,則任務(wù)i的第+1道工序的后續(xù)時(shí)間SP,EP,SD和ED無須更新,因該資源已釋放,但需要更新FT中任務(wù)i的第+1道工序的加工完成時(shí)間,即

③若存在與res相同的資源,則根據(jù)這些資源在R中的位置,查找X中相應(yīng)位置的企業(yè),若為空,表示分配的企業(yè)與ent不相同,則操作同步驟②。

④若這些企業(yè)與ent相同,則比較到達(dá)時(shí)間S(i,j)與相同資源相同企業(yè)的FT值,若S(i,j)≥相同資源相同企業(yè)的FT值,則操作同步驟②。

⑤若S(i,j)＜相同資源相同企業(yè)的FT最大值MFT,則任務(wù)i的第+1道工序的后續(xù)時(shí)間SP,EP,SD和 ED均加上等待時(shí)間WT,WT=MFT-S(i,j),即更新S的第i行第j+1至4X p(i)列,同時(shí)更新FT中任務(wù)i的第+1道工序的加工完成時(shí)間,FT(L(i)+

⑥重復(fù)步驟①至步驟⑤,查找第j列非0的次小EDij,直到所有任務(wù)的時(shí)間更新完畢。

(5)j=j+4,重復(fù)步驟(4),直到j(luò)=4v-2為止。

(6)確定資源分配方案X的最短完成時(shí)間,f1(X)=MaX(FT (p(1)),FT(p(2)),…,FT(p(k)))。

2.4 算法步驟

應(yīng)用遺傳分層序列法求解上述制造資源分配問題步驟如下:

(1)資源分配方案編碼采用符號編碼,Xia表示分配給任務(wù)i第a道工序的企業(yè)編號,Xia∈[1,m],編碼長度L=p (1)+p(2)+…+p(k)。

(2)初始化種群X(t)={X1,X2,…,XN},t=1,2,…,MaXGen, MaXGen表示最大進(jìn)化代數(shù),N是種群內(nèi)個體數(shù),即方案數(shù)。

(3)按公式(2)計(jì)算第一層目標(biāo)值,選擇目標(biāo)值最小的個體存入可行解集。寬容值設(shè)定為初始種群各目標(biāo)的最大值。

(4)按照設(shè)計(jì)的遺傳策略進(jìn)行遺傳操作,產(chǎn)生新一代種群X(t+1),重復(fù)步驟(2)至步驟(3),直到達(dá)到最大進(jìn)化代數(shù)MaXGen為止。

(5)按公式(4)計(jì)算可行解集中各方案的離差均值。

(6)若決策者要求多個目標(biāo)均衡,則選擇具有最小離差均值的方案作為最優(yōu)資源分配方案。

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)準(zhǔn)備

以湖北省8家制造企業(yè)為例(m=8),企業(yè)分布見表1所示。企業(yè)1接到兩個訂單的生產(chǎn)任務(wù),批量分別是b1= 200件,b2=100件。任務(wù)1工藝路線為R1=[r2,r4,r3,r6,r5, r1]。任務(wù)2的工藝路線為R2=[r3,r1,r2,r5,r6]。企業(yè)間的運(yùn)輸時(shí)間見表2所示。

表1 企業(yè)地理分布

表2 運(yùn)輸時(shí)間

企業(yè)共擁有6類資源,各企業(yè)擁有的資源信息如表3所示。

表3 企業(yè)資源

表3中的每一行代表該企業(yè)擁有的各類資源信息,單元格中第一個數(shù)據(jù)表示企業(yè)擁有某類資源的數(shù)量q,第二個數(shù)據(jù)表示單位加工時(shí)間PT(分鐘/件/臺),第三個數(shù)據(jù)表示單位加工成本PC(元/件)?？諉卧癖硎酒髽I(yè)沒有該類資源。

采用GLM、NSGA-II和GA進(jìn)行比較分析,GLM第二層目標(biāo)采取均衡選擇原則,GA采用原始目標(biāo)之和作為適應(yīng)度函數(shù)。三個算法的選擇、交叉和變異概率分別為ps= 0.4,pc=0.4,pm=0.2,種群N=20,最大進(jìn)化代數(shù)MaXGen= 1000。計(jì)算結(jié)果均為10次的平均值。

3.2 不同進(jìn)化階段的計(jì)算結(jié)果比較

三個算法在不同進(jìn)化階段的計(jì)算的制造完成時(shí)間和制造成本目標(biāo)值見表4所示。

表4 不同進(jìn)化階段的目標(biāo)值

表5 資源分配方案

由表4可知,三個算法分別在217代、339代和456代達(dá)到最優(yōu),分配方案見表5。GLM算法求解結(jié)果最好,NSGA-II的制造任務(wù)完成時(shí)間較GA短,但它的制造成本高于GA,目標(biāo)值之和小于GA算法。盡管NSGA-II找到最優(yōu)解的時(shí)間比GLM短,但在相同精度下,它的效率最低。GA收斂較早。算法的收斂特性如圖2所示。

圖2 不同目標(biāo)的收斂曲線

觀察圖2可知,三個算法的制造時(shí)間(左圖)、制造成本(中圖)和目標(biāo)之和(右圖)曲線均呈下降趨勢,算法均收斂。從任務(wù)完成時(shí)間來看,GLM時(shí)間最短,NSGA-II次之。從制造成本來看,NSGA-II低于GLM。綜合來看, GLM性能優(yōu)于NSGA-II和GA。

3.3 不同決策目標(biāo)的計(jì)算結(jié)果比較

分別采用均衡決策目標(biāo)、制造任務(wù)完成時(shí)間最短目標(biāo)和制造成本最低目標(biāo),三個算法得到的最優(yōu)資源分配方案及目標(biāo)值如表6所示。

表6單元格中第一行與第二行分別表示兩個任務(wù)的資源分配方案,第三行是目標(biāo)值。無論決策目標(biāo)如何, GLM計(jì)算的原目標(biāo)之和、制造任務(wù)完成時(shí)間和制造成本均最低,優(yōu)于NSGA-II和GA算法的計(jì)算結(jié)果。NSGA-II根據(jù)解的支配關(guān)系選擇非劣解,其時(shí)間復(fù)雜度為N2× MaXGen,相對于GLM,NSGA-II達(dá)到相同精度的解,需要更長的計(jì)算時(shí)間。

表6 不同決策目標(biāo)的資源分配方案

4 結(jié)論

計(jì)算實(shí)驗(yàn)表明,遺傳分層序列法是一個性能更優(yōu)的多目標(biāo)決策方法,不僅計(jì)算速度較快,解的質(zhì)量也最高,適合于多制造任務(wù)資源的優(yōu)化配置。盡管遺傳分層序列法在進(jìn)行多目標(biāo)決策時(shí)具有優(yōu)勢,但它的第一層采取的原目標(biāo)和最優(yōu)保存策略,這有可能丟失原目標(biāo)較為均衡的解,如何結(jié)合解的支配關(guān)系,設(shè)計(jì)更為合理的遺傳算法適應(yīng)度函數(shù)值得研究。此外,云制造是一項(xiàng)復(fù)雜的系統(tǒng)工程,資源優(yōu)化配置僅是其中的一項(xiàng)工作。關(guān)于云制造的復(fù)雜資源信息建模、可變工藝路線情形的算法編碼以及不同制造模式的資源分配模型值得進(jìn)一步探索。

[1]李伯虎,張霖,任磊等.再論云制造[J].計(jì)算機(jī)集成制造系統(tǒng), 2011,17(3).

[2]朱金達(dá),鄭艷萍,宋海生.網(wǎng)絡(luò)化制造環(huán)境下多目標(biāo)任務(wù)分配的研究[J].河北科技大學(xué)學(xué)報(bào),2010,31(5).

[3]彭建剛,劉明周,張銘鑫等.基于改進(jìn)非支配排序的云模型進(jìn)化多目標(biāo)柔性作業(yè)車間調(diào)度[J].機(jī)械工程學(xué)報(bào),2014,50(12).

[4]Manupati v K,Thakkar J J,w ong K y,etc.Near Optimal Process Plan Selection for Multiple Jobs in Networked Based Manufacturing Using Multi一objective Evolutionary Algorithms[J].Computers&IndustrialEngineering,2013,66(1).

[5]郭世偉,何霆,戰(zhàn)德臣.網(wǎng)絡(luò)化制造環(huán)境下的生產(chǎn)計(jì)劃策略[J].計(jì)算機(jī)工程,2010,36(7).

[6]Chu w w,Liy G,Liu CQ,etc.AMatrix一based Bayesian Approach for Manufacturing Resource Allocation Planning in Supply Chain Management[J].International Journal of Production Research,2014, 52(11).

(責(zé)任編輯/浩天)

TP301

A

1002-6487(2016)20-0080-04

國家社會科學(xué)基金資助項(xiàng)目(14BTQ058);湖北省科技廳軟科學(xué)研究類一般項(xiàng)目(2015BDF087)

汪勇(1967—),男,安徽廬江人,博士,教授,研究方向:多目標(biāo)決策方法,復(fù)雜系統(tǒng)建模。徐瓊(1989—),女,湖北紅安人,碩士研究生,研究方向:進(jìn)化計(jì)算,數(shù)據(jù)挖掘。