汪勇,徐瓊,張凌,王靜

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

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

汪勇,徐瓊,張凌,王靜

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

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

云制造;資源分配;多目標決策;遺傳分層序列法

0 引言

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

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

1 遺傳分層序列法

1.1 目標設(shè)計

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

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

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

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

1.2 遺傳策略設(shè)計

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

(1)選擇策略

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

(2)交叉策略

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

(3)變異策略

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

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

1.3 GLM算法流程

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

圖1 GLM算法流程

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

2.1 問題描述

多制造任務(wù)是指共享云制造平臺或企業(yè)專有云制造平臺接收不同產(chǎn)品的制造任務(wù),且這些任務(wù)的部分工序使用相同的制造資源,每個任務(wù)的批量進行整體資源分配。設(shè)有m個處于不同地域的企業(yè),共有n類資源,每個企業(yè)擁有的資源數(shù)量、單位加工時間和單位加工成本分別為q,PT和PC。企業(yè)間的運輸時間為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道工序的單位加工時間和單位加工成本,DTia表示任務(wù)i從第a-1道工序運輸?shù)降赼道工序的時間,WTia為任務(wù)i到達第a道工序時的等待加工時間。

若為任務(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ù)的加工完成的時間分別為T1,T2,…,Tk,完成所有任務(wù)的加工成本為C。在滿足資源數(shù)量約束和資源不沖突的條件下,尋找一個最優(yōu)方案X,使得完成所有加工任務(wù)的時間T最短且加工成本C最低,見公式(4)和公式(5)。

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

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ù)一次性同時分配資源,即方案X的模為k。

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

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

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

由于每個任務(wù)的每道工序可能存在資源沖突,可以按照任務(wù)優(yōu)先級、短工時優(yōu)先和先到先分配的原則處理資源沖突。先到先分配是通過比較任務(wù)的運輸?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ù)制造完成時間計算步驟如下:

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

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

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

(2)初始化S

設(shè)所有任務(wù)起始運輸時間相同,即第一道工序的SD= 0。不考慮等待時間,對于方案X,按照各任務(wù)工序間的運輸時間DT和加工時間PT,分別計算各任務(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ù)各工序的加工完成時間,j=1,2,…,p(i)。FT初值為0,表示該資源未被使用,非0數(shù)值表示資源已被分配,其值表示資源釋放時間。

(4)更新進度矩陣

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

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

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

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

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

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

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

(6)確定資源分配方案X的最短完成時間,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表示最大進化代數(shù),N是種群內(nèi)個體數(shù),即方案數(shù)。

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

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

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

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

3 實驗分析

3.1 數(shù)據(jù)準備

以湖北省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è)間的運輸時間見表2所示。

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

表2 運輸時間

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

表3 企業(yè)資源

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

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

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

三個算法在不同進化階段的計算的制造完成時間和制造成本目標值見表4所示。

表4 不同進化階段的目標值

表5 資源分配方案

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

圖2 不同目標的收斂曲線

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

3.3 不同決策目標的計算結(jié)果比較

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

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

表6 不同決策目標的資源分配方案

4 結(jié)論

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

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

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

[3]彭建剛,劉明周,張銘鑫等.基于改進非支配排序的云模型進化多目標柔性作業(yè)車間調(diào)度[J].機械工程學(xué)報,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].計算機工程,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é)基金資助項目(14BTQ058);湖北省科技廳軟科學(xué)研究類一般項目(2015BDF087)

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