面向云制造的訂單資源分配方法

苑明海 張理志 朱雅萍 李亞東

(①河海大學(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ù)平臺，建立了用于產(chǎn)品設(shè)計(jì)，制造和其他生產(chǎn)周期活動(dòng)的分布式協(xié)作制造模式[3]。

在云制造服務(wù)平臺下，如何快速實(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)度模型，并針對服務(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]針對多任務(wù)時(shí)組合效果不佳的問題，提出了面向復(fù)雜任務(wù)請求的服務(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)證了其可行性和有效性。

1 云制造訂單資源的調(diào)配問題描述

1.1 調(diào)配問題數(shù)學(xué)描述

多任務(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對應(yīng)的目標(biāo)函數(shù)，gj(x)為任務(wù)x的第j個(gè)約束條件，S為其要滿足的解域。

1.2 云制造訂單資源調(diào)配描述

云制造環(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)對同一產(chǎn)品的制造成本都一樣。

(5)產(chǎn)品生產(chǎn)制造過程中，各制造單位運(yùn)輸方式固定，且時(shí)間成本已知。

為更好地對調(diào)配模型進(jìn)行后續(xù)的研究，從而對模型中涉及到的參數(shù)進(jìn)行統(tǒng)一說明，具體如表1所示。

表1 參數(shù)定義及說明

表1中，企業(yè)編號參數(shù)i= 1, 2,…，e。

每個(gè)訂單對應(yīng)一種產(chǎn)品類型，如果原始訂單包含若干個(gè)種類的產(chǎn)品，則對原始訂單重新拆分成若干個(gè)子訂單，訂單編號用參數(shù)r來表示。例如：產(chǎn)品訂單A，包含a和b兩種類型，則對應(yīng)的子訂單可編號為1和2。原始訂單中若沒特別指出，都按照拆分子訂單進(jìn)行編號。假設(shè)在計(jì)劃期[1,T]內(nèi)，拆分后重新編號的子訂單總數(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)。

2 訂單資源調(diào)配模型的建立

云制造環(huán)境下，企業(yè)聯(lián)盟基于各企業(yè)的制造能力和訂單約束條件，對訂單資源進(jìn)行合理調(diào)配，過程中需要充分考慮產(chǎn)品訂單的制造成本，運(yùn)輸成本，懲罰成本，使其目標(biāo)總成本最小。所以本研究主要從產(chǎn)品訂單制造成本、運(yùn)輸成本和懲罰成本3個(gè)方面建立目標(biāo)函數(shù)。

2.1 目標(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)

2.2 約束條件

(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í)，針對訂單r、開工期、制造周期和運(yùn)輸時(shí)長應(yīng)滿足如下約束：

(zri+Tri+tri-t)·xri(t)=0

(13)

2.3 訂單資源調(diào)配模型

綜合上述分析可得，訂單資源調(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)

3 改進(jìn)多層編碼遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)

上述的模型函數(shù)，是一類典型的非線性多約束優(yōu)化的復(fù)雜問題，涉及到的參數(shù)多，對應(yīng)的數(shù)據(jù)量也龐大，針對這類問題一般采用智能算法來求解。為清楚的表達(dá)各訂單對應(yīng)生產(chǎn)企業(yè)的有效配置，本研究采用改進(jìn)的多層編碼遺傳算法來求解。首先，通過采用整數(shù)編碼的方式將訂單個(gè)體編碼并分為多層，每層編碼對應(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ì)的說明。

3.1 整體模型

本文采用整數(shù)編碼的方式來進(jìn)行編碼，每個(gè)染色體表示產(chǎn)品訂單的調(diào)配生產(chǎn)順序?；诋a(chǎn)品訂單資源調(diào)配生產(chǎn)的特點(diǎn)，提出基于訂單編號和加工企業(yè)的兩段式非負(fù)整數(shù)編碼方法。如圖1所示。

圖1對應(yīng)的個(gè)體為：

[4736125831324214]

該個(gè)體表達(dá)了8個(gè)訂單在4個(gè)加工企業(yè)的生產(chǎn)順序。其中前8位表示訂單的編號，后8為表示4個(gè)加工企業(yè)的調(diào)配生產(chǎn)順序。

第一部分基因依據(jù)訂單的編號進(jìn)行編碼。其中基因長度對應(yīng)訂單的個(gè)數(shù)，編碼的先后順序表示訂單的先后加工順序。

第二部分基因依據(jù)企業(yè)編號進(jìn)行編碼，且編號與第一部分中訂單的生產(chǎn)企業(yè)對應(yīng)。

3.2 初始種群的生成

隨機(jī)生成初始種群M，定義為M={u1,u2,···,um}，其中um表示群體M中的個(gè)體，構(gòu)成問題的初始解。

3.3 適應(yīng)度函數(shù)的計(jì)算

適應(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è)編號，每一行從第二位起表示在該企業(yè)生產(chǎn)的訂單編號。

(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。

3.4 遺傳操作

(1) 親本選擇

為保證適應(yīng)度好的染色體能夠被選擇，本文采用輪盤賭法對個(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è)體濃度對選擇算子進(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]?；谏衔牡木幋a方式，選用整數(shù)PMX(partial-mapped crossover)交叉方式進(jìn)行交叉操作，避免交叉過程中產(chǎn)生的非法染色體。具體操作如圖2所示。

(3) 變異操作

變異操作能夠保證了均衡的全局和局部搜索能力。種群規(guī)模大小，編碼方式和長度等因素都會(huì)對變異率的選取產(chǎn)生一定的影響，一般取值比較小，范圍為pv∈[0.001,0.1]。

根據(jù)個(gè)體編碼特點(diǎn)，變異操作即從染色體第一部分隨機(jī)選擇兩個(gè)變異個(gè)體，對應(yīng)位置position1和position2，交換兩位置改變其調(diào)配的先后順序，第二部分則按照position1和position2對應(yīng)的position3和position4上的生產(chǎn)企業(yè)編碼做同樣的調(diào)換操作。具體如圖3所示。

(4) 精英保留策略

在交叉變異后，為了讓適應(yīng)度較好的父代染色體能夠保留下來，將其與子代進(jìn)行適應(yīng)度值的比較，保留適應(yīng)度較好的染色體。

4 實(shí)例驗(yàn)證

為了檢驗(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è)的制造能力對8大產(chǎn)品訂單進(jìn)行重新拆分和編號，將其分成若干子訂單，并將這些子訂單分別定義為1, 2, 3, … , 16。在進(jìn)行訂單生產(chǎn)時(shí)，企業(yè)生產(chǎn)能力如表3所示，對應(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定，懲罰函數(shù)的權(quán)重系數(shù)為α=0.1，β=0.2。在編碼計(jì)算過程中，對應(yīng)產(chǎn)品編號如表7所示。

通過仿真運(yùn)算，得到改進(jìn)多層編碼遺傳算法搜索過程如圖4所示。同時(shí)，最優(yōu)個(gè)體對應(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)對比，得到的一般算法搜索過程如圖6所示，各目標(biāo)結(jié)果值對比情況如表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)品類型對應(yīng)編碼

表8 產(chǎn)品訂單調(diào)最優(yōu)解

表9 不同算法的對比結(jié)果

表8列出了最優(yōu)個(gè)體中各訂單中各產(chǎn)品類型在各企業(yè)生產(chǎn)分配之間的關(guān)系，對應(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對比可知，本文設(shè)計(jì)的I-MCGA比一般GA更早趨于收斂，尋優(yōu)能力有了較大提高。從表9不同算法對比的結(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ì)效益。

5 結(jié)語

本文研究了CMfg環(huán)境下的訂單分配問題，根據(jù)制造特點(diǎn)和生產(chǎn)需求的多樣性建立了訂單分配模型。將包括制造成本，運(yùn)輸成本和罰款成本在內(nèi)的總成本用作計(jì)劃目標(biāo)。考慮訂單生產(chǎn)能力，從3個(gè)方面對模型進(jìn)行了進(jìn)一步測度：最早的開放時(shí)間，最近的開放時(shí)間和等式約束。然后，設(shè)計(jì)了一個(gè)I-GAMc來求解該模型，在該模型中建立約束矩陣，改進(jìn)選擇算子，并將整數(shù)PMX用于交叉運(yùn)算。最后，通過實(shí)例驗(yàn)證了該模型和算法的可行性和有效性。但是，本文僅從企業(yè)層面研究訂單分配。實(shí)際上，還需要考慮其他級別。將來，需要研究更高效，更穩(wěn)定的調(diào)度算法?；诖髷?shù)據(jù)，數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的云制造調(diào)度也將是未來的重點(diǎn)。