苑明海 張理志 朱雅萍 李亞東
(①河海大學(xué)機(jī)電工程學(xué)院,江蘇 常州 213000;②南通河海大學(xué)海洋與近海工程研究院,江蘇 南通 226300)
當(dāng)今,個(gè)性化產(chǎn)品需求的不斷增長,制造企業(yè)必須探索改善生產(chǎn)方式,增強(qiáng)企業(yè)競爭力的新途徑[1]。云制造(CMfg)作為一種新型智能制造模式,它出現(xiàn)使許多位于不同地點(diǎn)、生產(chǎn)能力和規(guī)模的企業(yè)結(jié)成了企業(yè)聯(lián)盟[2]。企業(yè)聯(lián)盟基于CMfg服務(wù)平臺(tái),建立了用于產(chǎn)品設(shè)計(jì),制造和其他生產(chǎn)周期活動(dòng)的分布式協(xié)作制造模式[3]。
在云制造服務(wù)平臺(tái)下,如何快速實(shí)現(xiàn)各生產(chǎn)單位間的訂單資源有效分配就具有重要的研究價(jià)值和意義。一些學(xué)者為云調(diào)度做出了貢獻(xiàn),李帥等[4]提出了面向突發(fā)事件的分布式制造中的資源調(diào)配模型,并用粒子群算法進(jìn)行求解。周龍飛等[5-6]研究了企業(yè)車間資源的調(diào)度情況,闡述了CMfg調(diào)度的原理和復(fù)雜性,提出了一種事件觸發(fā)的動(dòng)態(tài)任務(wù)調(diào)度方法。邰麗君[7]等構(gòu)建了資源服務(wù)目標(biāo)調(diào)度模型,并針對(duì)服務(wù)組合時(shí)可能出現(xiàn)的突發(fā)問題,提出了一種動(dòng)態(tài)調(diào)度技術(shù)。彭運(yùn)芳等[8]基于模糊理論提出了一種改進(jìn)的遺傳算法,解決在不確定條件下的車間調(diào)度問題。張國輝等[9]分析了車間實(shí)際生產(chǎn)中工件移動(dòng)時(shí)間的情況,構(gòu)建了柔性車間作業(yè)調(diào)度模型。劉波等[10]針對(duì)多任務(wù)時(shí)組合效果不佳的問題,提出了面向復(fù)雜任務(wù)請(qǐng)求的服務(wù)組合優(yōu)化框架。在云環(huán)境中,王旭亮等[11]使用分支剪切算法來解決跨企業(yè)、多約束、多品種和小批量生產(chǎn)和調(diào)度問題。一些學(xué)者還從服務(wù)優(yōu)化組合,分配模型的建立,任務(wù)分解[12-13]中總結(jié)了云調(diào)度。
上述文獻(xiàn)為云調(diào)度做出了貢獻(xiàn),但是,云制造中的訂單資源分配仍然存在數(shù)學(xué)模型的完整性、約束條件的設(shè)置、解的有效性以及算法的復(fù)雜性等問題。因此,本文充分考慮了每個(gè)訂單的生產(chǎn)約束,構(gòu)建了完整的訂單分配模型,并提出了一種改進(jìn)的多層編碼遺傳算法進(jìn)行求解。在實(shí)踐中,成本仍然是企業(yè)最重要的因素,因此,本文以制造成本、物流成本以及罰款成本為調(diào)度目標(biāo)。最后,通過實(shí)例驗(yàn)證了其可行性和有效性。
多任務(wù)資源調(diào)配問題可描述為:
x=[x1,x2,x3,...,xn]T
Miny=f(x)={f1(x),f2(x),f3(x),...,fm(x)}(1)
y=f(x)={f1(x),f2(x),f3(x),...,fm(x)}
式中:x為任務(wù)決策向量,y為目標(biāo)向量,f(x)為任務(wù)決策向量x對(duì)應(yīng)的目標(biāo)函數(shù),gj(x)為任務(wù)x的第j個(gè)約束條件,S為其要滿足的解域。
云制造環(huán)境下,企業(yè)聯(lián)盟(EU)下屬有e個(gè)制造企業(yè)且分布在不同區(qū)域,各制造單位由聯(lián)盟統(tǒng)一調(diào)度部署生產(chǎn)p種產(chǎn)品。假設(shè)在給定的計(jì)劃期T內(nèi),EU獲得若干產(chǎn)品訂單,將訂單分配給e個(gè)制造企業(yè)生產(chǎn),求調(diào)配模型的最優(yōu)目標(biāo)值。
在訂單調(diào)配模型中作如下假設(shè):
(1)各制造企業(yè)在接到產(chǎn)品訂單前,無在制品、產(chǎn)成品或缺貨累積情況。
(2)各制造企業(yè)按訂單量生產(chǎn),計(jì)劃期內(nèi)一旦開始,過程中不允許中斷,直至生產(chǎn)結(jié)束。
(3)各制造企業(yè)的生產(chǎn)線按計(jì)劃期最大生產(chǎn)量生產(chǎn),其最大生產(chǎn)量是綜合考慮設(shè)備、員工、物料等約束確定的。
(4)生產(chǎn)過程中,不存在次品或偽劣品;每個(gè)制造企業(yè)在計(jì)劃期內(nèi)對(duì)同一產(chǎn)品的制造成本都一樣。
(5)產(chǎn)品生產(chǎn)制造過程中,各制造單位運(yùn)輸方式固定,且時(shí)間成本已知。
為更好地對(duì)調(diào)配模型進(jìn)行后續(xù)的研究,從而對(duì)模型中涉及到的參數(shù)進(jìn)行統(tǒng)一說明,具體如表1所示。
表1 參數(shù)定義及說明
表1中,企業(yè)編號(hào)參數(shù)i= 1, 2,…,e。
每個(gè)訂單對(duì)應(yīng)一種產(chǎn)品類型,如果原始訂單包含若干個(gè)種類的產(chǎn)品,則對(duì)原始訂單重新拆分成若干個(gè)子訂單,訂單編號(hào)用參數(shù)r來表示。例如:產(chǎn)品訂單A,包含a和b兩種類型,則對(duì)應(yīng)的子訂單可編號(hào)為1和2。原始訂單中若沒特別指出,都按照拆分子訂單進(jìn)行編號(hào)。假設(shè)在計(jì)劃期[1,T]內(nèi),拆分后重新編號(hào)的子訂單總數(shù)為N,r= 1, 2, … ,N。
每個(gè)訂單都按計(jì)劃期生產(chǎn),違反計(jì)劃期約束的解將給予懲罰,將產(chǎn)生額外的懲罰成本。參數(shù)dr是產(chǎn)品訂單r的最后交貨期限,逾期將交付相應(yīng)的懲罰成本。
bri為0-1變量,表示企業(yè)i生產(chǎn)訂單r的能力。其值為1,表示企業(yè)i具有生產(chǎn)訂單r的能力;bri為0時(shí),表示不具有該能力。
xri(t)為0-1變量,表示企業(yè)i按期交貨的能力。當(dāng)xri(t)=0,表示訂單r不在該企業(yè)i生產(chǎn),不能按期交付;xri(t)=1,表示產(chǎn)品訂單r在企業(yè)i生產(chǎn),并能在t計(jì)劃期按時(shí)交付。
zri為訂單r在企業(yè)i的開工期,則完工期為zri+Tri。例如:第t時(shí)段,開工期即為t時(shí)段起點(diǎn),完工期即為t時(shí)段末點(diǎn),同樣交貨期dr也為t時(shí)段末點(diǎn)。
云制造環(huán)境下,企業(yè)聯(lián)盟基于各企業(yè)的制造能力和訂單約束條件,對(duì)訂單資源進(jìn)行合理調(diào)配,過程中需要充分考慮產(chǎn)品訂單的制造成本,運(yùn)輸成本,懲罰成本,使其目標(biāo)總成本最小。所以本研究主要從產(chǎn)品訂單制造成本、運(yùn)輸成本和懲罰成本3個(gè)方面建立目標(biāo)函數(shù)。
(1) 制造成本
計(jì)劃期[1,T]內(nèi),產(chǎn)品訂單r在企業(yè)i生產(chǎn),單位制造成本為sri,則產(chǎn)品訂單總制造成本為:
(2)
(2)運(yùn)輸成本
訂單r在企業(yè)i生產(chǎn)時(shí),產(chǎn)生的運(yùn)輸成本為cri,由于運(yùn)輸方式固定,所以總運(yùn)輸成本為:
(3)
(3)懲罰成本
在實(shí)際生產(chǎn)過程中,企業(yè)在訂單生產(chǎn)時(shí),可能會(huì)出現(xiàn)提前或拖延完成生產(chǎn)任務(wù)的情況,與其產(chǎn)品的訂單價(jià)值vr相關(guān)聯(lián)。設(shè)提前/拖期情況的懲罰因子分別為α和β,則訂單r的提前/拖期懲罰成本為:
(4)
由于總懲罰成本包含提前和拖期兩種情況,則總懲罰成本為:
(5)
綜上所述,訂單調(diào)配模型的目標(biāo)函數(shù)可定義為:
(6)
(1) 訂單生產(chǎn)約束
一個(gè)訂單只能由一個(gè)企業(yè)生產(chǎn),故有:
(7)
(8)
bri,xri(t) ∈{0,1}
(9)
式(7)保證每個(gè)訂單只能由一個(gè)企業(yè)生產(chǎn)加工;式(8)確保每個(gè)產(chǎn)品訂單r企業(yè)i能夠準(zhǔn)時(shí)交貨;式(9)變量xri和bri是0-1變量。
(2)生產(chǎn)能力約束
企業(yè)聯(lián)盟下,各個(gè)企業(yè)制造能力不同,因此只有具備此種產(chǎn)品的生產(chǎn)能力才能進(jìn)行生產(chǎn),否則就不能生產(chǎn)。故有:
(bri-1)·xri(t)≥0
(10)
(3)開工期約束
開工期約束即表示某企業(yè)在訂單產(chǎn)品生產(chǎn)時(shí),必須保證前一個(gè)訂單完成后才可以開始新的訂單。
為充分考慮各企業(yè)產(chǎn)品生產(chǎn)的可能性,本文從產(chǎn)品訂單r的最早開工期,最晚開工期,以及計(jì)劃期約束3個(gè)方面進(jìn)行開工期進(jìn)行約束。具體如下:
(11)
式(11)表示訂單r的最早開工期zri不能早于企業(yè)i生產(chǎn)其他訂單的最晚完工期的下一個(gè)計(jì)劃期[14]。
(12)
同時(shí),針對(duì)訂單r、開工期、制造周期和運(yùn)輸時(shí)長應(yīng)滿足如下約束:
(zri+Tri+tri-t)·xri(t)=0
(13)
綜合上述分析可得,訂單資源調(diào)配模型為:
(14)
s.t.
(15)
(16)
bri,xri(t) ∈{0,1}r∈N,i∈e,t∈[1,T]
(17)
(bri-1)·xri(t)≥0r∈N,i∈e,t∈[1,T]
(18)
r∈[1,N],i∈[1,e],t∈[1,T]
(19)
(20)
(zri+Tri+tri-t)·xri(t)=0r∈[1,N],i∈[1,e],t∈[1,T]
(21)
上述的模型函數(shù),是一類典型的非線性多約束優(yōu)化的復(fù)雜問題,涉及到的參數(shù)多,對(duì)應(yīng)的數(shù)據(jù)量也龐大,針對(duì)這類問題一般采用智能算法來求解。為清楚的表達(dá)各訂單對(duì)應(yīng)生產(chǎn)企業(yè)的有效配置,本研究采用改進(jìn)的多層編碼遺傳算法來求解。首先,通過采用整數(shù)編碼的方式將訂單個(gè)體編碼并分為多層,每層編碼對(duì)應(yīng)不同含義,一起完整表達(dá)問題的解,實(shí)現(xiàn)了一條染色體多層編碼表示復(fù)雜問題的解,同時(shí)引進(jìn)個(gè)體濃度的概念,使其具有更強(qiáng)的適應(yīng)性。
為更好地闡述改進(jìn)多層編碼遺傳算法的求解過程,以5實(shí)例驗(yàn)證部分,表3~6數(shù)據(jù)資料中計(jì)劃期在[1,10]內(nèi)的1-8個(gè)子訂單為例進(jìn)行詳細(xì)的說明。
本文采用整數(shù)編碼的方式來進(jìn)行編碼,每個(gè)染色體表示產(chǎn)品訂單的調(diào)配生產(chǎn)順序?;诋a(chǎn)品訂單資源調(diào)配生產(chǎn)的特點(diǎn),提出基于訂單編號(hào)和加工企業(yè)的兩段式非負(fù)整數(shù)編碼方法。如圖1所示。
圖1對(duì)應(yīng)的個(gè)體為:
[4736125831324214]
該個(gè)體表達(dá)了8個(gè)訂單在4個(gè)加工企業(yè)的生產(chǎn)順序。其中前8位表示訂單的編號(hào),后8為表示4個(gè)加工企業(yè)的調(diào)配生產(chǎn)順序。
第一部分基因依據(jù)訂單的編號(hào)進(jìn)行編碼。其中基因長度對(duì)應(yīng)訂單的個(gè)數(shù),編碼的先后順序表示訂單的先后加工順序。
第二部分基因依據(jù)企業(yè)編號(hào)進(jìn)行編碼,且編號(hào)與第一部分中訂單的生產(chǎn)企業(yè)對(duì)應(yīng)。
隨機(jī)生成初始種群M,定義為M={u1,u2,···,um},其中um表示群體M中的個(gè)體,構(gòu)成問題的初始解。
適應(yīng)度函數(shù)反應(yīng)每條染色體的優(yōu)劣程度。本文的研究目標(biāo)是求訂單生產(chǎn)總成本的最優(yōu)值,因此采用訂單模型函數(shù)為適應(yīng)度函數(shù)。
(22)
以圖1中個(gè)體為例,根據(jù)解碼過程,計(jì)算適應(yīng)度函數(shù)值。
(1)構(gòu)建訂單生產(chǎn)順序矩陣A
將上述染色體解碼,得到生產(chǎn)順序矩陣A。矩陣A中第一列代表生產(chǎn)企業(yè)編號(hào),每一行從第二位起表示在該企業(yè)生產(chǎn)的訂單編號(hào)。
(2)構(gòu)建制造成本矩陣AM
根據(jù)矩陣A,表3和表4的數(shù)據(jù)資料,由制造成本函數(shù)(2)可得:
根據(jù)矩陣AM,可求得總制造成本為MC=520.9.
(3)構(gòu)建運(yùn)輸成本矩陣AT
根據(jù)矩陣A,表3和表5的數(shù)據(jù)資料,由運(yùn)輸成本函數(shù)(3)可得:
根據(jù)矩陣AT,同理可求得總運(yùn)輸成本TC=47。
(4)計(jì)算提前/拖期懲罰成本
根據(jù)矩陣A和表4的數(shù)據(jù)資料,構(gòu)建訂單生產(chǎn)計(jì)劃期約束矩陣AR和訂單產(chǎn)品數(shù)量約束矩陣AA,得:
根據(jù)開工期約束,式(19)~(21),表3~6的數(shù)據(jù)資料,計(jì)算可得訂單的生產(chǎn)調(diào)度矩陣為AS.
由矩陣A和矩陣AS可知在計(jì)劃期內(nèi)1-8子訂單的生產(chǎn)調(diào)度方案。如表2所示:
表2 1-8子訂單生產(chǎn)調(diào)度方案
根據(jù)矩陣AS和表4的數(shù)據(jù)資料計(jì)算提前/拖期的懲罰成本,可得:5#訂單拖期3天,懲罰成本為60;7#訂單拖期3天,懲罰成本為69.6;6#訂單拖期1天,懲罰成本為12;8#訂單提前1天,懲罰成本為9。其他訂單準(zhǔn)時(shí)交付。
所以,總懲罰成本為PC=150.6。
(5)計(jì)算總成本
根據(jù)目標(biāo)模型函數(shù),可得fTotal=Mc+Tc+Pc=718.5。
(1) 親本選擇
為保證適應(yīng)度好的染色體能夠被選擇,本文采用輪盤賭法對(duì)個(gè)體進(jìn)行選擇操作。種群的規(guī)模大小為M,個(gè)體Chromi的適應(yīng)度值為fitness(Chromi),則其被選擇的概率為:
(23)
由于輪盤賭法常會(huì)出現(xiàn)適應(yīng)度值優(yōu)的個(gè)體未被選入到下一更新群體的情況,同時(shí)會(huì)出現(xiàn)局部收斂的現(xiàn)象。為此,引入個(gè)體濃度對(duì)選擇算子進(jìn)行了改進(jìn)操作。
首先,從種群M中,找出個(gè)體屬性相同的個(gè)體,并將其歸為j類(j=1,2,…,n)。那么個(gè)體濃度為:
(24)
式中:rj表示第j類的數(shù)目。
(25)
則個(gè)體的選擇概率為:
(26)
式中:ζ∈(0,1)為選擇權(quán)重系數(shù)。
因此,目標(biāo)值越小代表該染色體越出色,適應(yīng)性越高,選擇概率就越大,算法的收斂速度也越快;同時(shí),個(gè)體的濃度越大,相應(yīng)的選擇概率就越小,從而避免了“早熟”的現(xiàn)象。
(2) 交叉操作
交叉算子是算法搜索求解的主要算子,交叉率的選值范圍一般為pc∈[0.2,0.9]。基于上文的編碼方式,選用整數(shù)PMX(partial-mapped crossover)交叉方式進(jìn)行交叉操作,避免交叉過程中產(chǎn)生的非法染色體。具體操作如圖2所示。
(3) 變異操作
變異操作能夠保證了均衡的全局和局部搜索能力。種群規(guī)模大小,編碼方式和長度等因素都會(huì)對(duì)變異率的選取產(chǎn)生一定的影響,一般取值比較小,范圍為pv∈[0.001,0.1]。
根據(jù)個(gè)體編碼特點(diǎn),變異操作即從染色體第一部分隨機(jī)選擇兩個(gè)變異個(gè)體,對(duì)應(yīng)位置position1和position2,交換兩位置改變其調(diào)配的先后順序,第二部分則按照position1和position2對(duì)應(yīng)的position3和position4上的生產(chǎn)企業(yè)編碼做同樣的調(diào)換操作。具體如圖3所示。
(4) 精英保留策略
在交叉變異后,為了讓適應(yīng)度較好的父代染色體能夠保留下來,將其與子代進(jìn)行適應(yīng)度值的比較,保留適應(yīng)度較好的染色體。
為了檢驗(yàn)所設(shè)計(jì)的改進(jìn)多層編碼遺傳算法求解訂單調(diào)配問題的有效性和可行性,以某企業(yè)聯(lián)盟的生產(chǎn)訂單數(shù)據(jù)資料進(jìn)行數(shù)值仿真分析與驗(yàn)證。
EU下屬有某4家企業(yè)共可生產(chǎn)a、b、c和d這4大類型產(chǎn)品。假設(shè)在計(jì)劃期[1,20]內(nèi),EU接收到客戶的8大產(chǎn)品訂單生產(chǎn)需求,根據(jù)訂單的產(chǎn)品類型和各企業(yè)的制造能力對(duì)8大產(chǎn)品訂單進(jìn)行重新拆分和編號(hào),將其分成若干子訂單,并將這些子訂單分別定義為1, 2, 3, … , 16。在進(jìn)行訂單生產(chǎn)時(shí),企業(yè)生產(chǎn)能力如表3所示,對(duì)應(yīng)的訂單信息如表4所示,企業(yè)計(jì)劃期內(nèi)的最大生產(chǎn)量如表5所示,生產(chǎn)過程中產(chǎn)生的運(yùn)輸時(shí)間和成本如表6所示。為保證各成本處于可接受的水平,設(shè)定提前,拖期交貨的懲罰因子為α=0.1,β=0.2。
算法仿真的參數(shù)設(shè)定:種群規(guī)模為50,交叉概率為0.8,變異概率為0.1,代溝為0.9,最大遺傳代數(shù)為50,算法終止。根據(jù)訂單的實(shí)際需求或?qū)<以u(píng)定,懲罰函數(shù)的權(quán)重系數(shù)為α=0.1,β=0.2。在編碼計(jì)算過程中,對(duì)應(yīng)產(chǎn)品編號(hào)如表7所示。
通過仿真運(yùn)算,得到改進(jìn)多層編碼遺傳算法搜索過程如圖4所示。同時(shí),最優(yōu)個(gè)體對(duì)應(yīng)的產(chǎn)品訂單在1#企業(yè)-4#企業(yè)的調(diào)配方案如表8所示。產(chǎn)品訂單分配加工甘特圖如圖5所示,其中101表示1#企業(yè)生產(chǎn)1#訂單產(chǎn)品a類型,其他的依次類推。為直觀的表達(dá)本文設(shè)計(jì)算法的有效性,在參數(shù)設(shè)置相等的情況下,采用一般的遺傳算法(genetic algorithm, GA)與本文的改進(jìn)的多層編碼算法(improved multi-level coding GA, I-MCGA)進(jìn)行仿真試驗(yàn)對(duì)比,得到的一般算法搜索過程如圖6所示,各目標(biāo)結(jié)果值對(duì)比情況如表9所示。
表3 企業(yè)聯(lián)盟(EU)的bri和sri值
表4 訂單信息
表5 企業(yè)聯(lián)盟(EU)在[1,20]計(jì)劃期內(nèi)的最大生產(chǎn)量qi(t)
表6 訂單在企業(yè)聯(lián)盟(EU)的運(yùn)輸時(shí)間tri和運(yùn)輸成本cri
表7 產(chǎn)品類型對(duì)應(yīng)編碼
表8 產(chǎn)品訂單調(diào)最優(yōu)解
表9 不同算法的對(duì)比結(jié)果
表8列出了最優(yōu)個(gè)體中各訂單中各產(chǎn)品類型在各企業(yè)生產(chǎn)分配之間的關(guān)系,對(duì)應(yīng)的加工甘特圖如圖5所示,此時(shí)最小目標(biāo)值為1 285.1,其中制造成本為1 055.4,運(yùn)輸成本為91,懲罰成本為138.7,末計(jì)劃期為18,滿足產(chǎn)品生產(chǎn)的最晚計(jì)劃期要求。從圖4和圖6對(duì)比可知,本文設(shè)計(jì)的I-MCGA比一般GA更早趨于收斂,尋優(yōu)能力有了較大提高。從表9不同算法對(duì)比的結(jié)果來看,本文的I-MCGA具有較高的搜尋最優(yōu)解性能,得到的各目標(biāo)成本優(yōu)化結(jié)果都有較大提升。從而證明本文設(shè)計(jì)的算法具有更強(qiáng)的尋優(yōu)求解能力,同時(shí)也說明本文設(shè)計(jì)的產(chǎn)品訂單調(diào)配模型也是合理有效的。云制造企業(yè)聯(lián)盟可以將求解的最優(yōu)解應(yīng)用到實(shí)際的生產(chǎn)分配中去,不僅可以提高產(chǎn)品的生產(chǎn)效率,也可以增加企業(yè)的經(jīng)濟(jì)效益。
本文研究了CMfg環(huán)境下的訂單分配問題,根據(jù)制造特點(diǎn)和生產(chǎn)需求的多樣性建立了訂單分配模型。將包括制造成本,運(yùn)輸成本和罰款成本在內(nèi)的總成本用作計(jì)劃目標(biāo)??紤]訂單生產(chǎn)能力,從3個(gè)方面對(duì)模型進(jìn)行了進(jìn)一步測度:最早的開放時(shí)間,最近的開放時(shí)間和等式約束。然后,設(shè)計(jì)了一個(gè)I-GAMc來求解該模型,在該模型中建立約束矩陣,改進(jìn)選擇算子,并將整數(shù)PMX用于交叉運(yùn)算。最后,通過實(shí)例驗(yàn)證了該模型和算法的可行性和有效性。但是,本文僅從企業(yè)層面研究訂單分配。實(shí)際上,還需要考慮其他級(jí)別。將來,需要研究更高效,更穩(wěn)定的調(diào)度算法。基于大數(shù)據(jù),數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的云制造調(diào)度也將是未來的重點(diǎn)。