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

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

(①河海大學機電工程學院，江蘇 常州 213000；②南通河海大學海洋與近海工程研究院，江蘇 南通 226300)

當今，個性化產(chǎn)品需求的不斷增長，制造企業(yè)必須探索改善生產(chǎn)方式，增強企業(yè)競爭力的新途徑[1]。云制造(CMfg)作為一種新型智能制造模式，它出現(xiàn)使許多位于不同地點、生產(chǎn)能力和規(guī)模的企業(yè)結成了企業(yè)聯(lián)盟[2]。企業(yè)聯(lián)盟基于CMfg服務平臺，建立了用于產(chǎn)品設計，制造和其他生產(chǎn)周期活動的分布式協(xié)作制造模式[3]。

在云制造服務平臺下，如何快速實現(xiàn)各生產(chǎn)單位間的訂單資源有效分配就具有重要的研究價值和意義。一些學者為云調度做出了貢獻，李帥等[4]提出了面向突發(fā)事件的分布式制造中的資源調配模型，并用粒子群算法進行求解。周龍飛等[5-6]研究了企業(yè)車間資源的調度情況，闡述了CMfg調度的原理和復雜性，提出了一種事件觸發(fā)的動態(tài)任務調度方法。邰麗君[7]等構建了資源服務目標調度模型，并針對服務組合時可能出現(xiàn)的突發(fā)問題，提出了一種動態(tài)調度技術。彭運芳等[8]基于模糊理論提出了一種改進的遺傳算法，解決在不確定條件下的車間調度問題。張國輝等[9]分析了車間實際生產(chǎn)中工件移動時間的情況，構建了柔性車間作業(yè)調度模型。劉波等[10]針對多任務時組合效果不佳的問題，提出了面向復雜任務請求的服務組合優(yōu)化框架。在云環(huán)境中，王旭亮等[11]使用分支剪切算法來解決跨企業(yè)、多約束、多品種和小批量生產(chǎn)和調度問題。一些學者還從服務優(yōu)化組合，分配模型的建立，任務分解[12-13]中總結了云調度。

上述文獻為云調度做出了貢獻，但是，云制造中的訂單資源分配仍然存在數(shù)學模型的完整性、約束條件的設置、解的有效性以及算法的復雜性等問題。因此，本文充分考慮了每個訂單的生產(chǎn)約束，構建了完整的訂單分配模型，并提出了一種改進的多層編碼遺傳算法進行求解。在實踐中，成本仍然是企業(yè)最重要的因素，因此，本文以制造成本、物流成本以及罰款成本為調度目標。最后，通過實例驗證了其可行性和有效性。

1 云制造訂單資源的調配問題描述

1.1 調配問題數(shù)學描述

多任務資源調配問題可描述為：

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為任務決策向量，y為目標向量，f(x)為任務決策向量x對應的目標函數(shù)，gj(x)為任務x的第j個約束條件，S為其要滿足的解域。

1.2 云制造訂單資源調配描述

云制造環(huán)境下，企業(yè)聯(lián)盟(EU)下屬有e個制造企業(yè)且分布在不同區(qū)域，各制造單位由聯(lián)盟統(tǒng)一調度部署生產(chǎn)p種產(chǎn)品。假設在給定的計劃期T內，EU獲得若干產(chǎn)品訂單，將訂單分配給e個制造企業(yè)生產(chǎn)，求調配模型的最優(yōu)目標值。

在訂單調配模型中作如下假設：

(1)各制造企業(yè)在接到產(chǎn)品訂單前，無在制品、產(chǎn)成品或缺貨累積情況。

(2)各制造企業(yè)按訂單量生產(chǎn)，計劃期內一旦開始，過程中不允許中斷，直至生產(chǎn)結束。

(3)各制造企業(yè)的生產(chǎn)線按計劃期最大生產(chǎn)量生產(chǎn)，其最大生產(chǎn)量是綜合考慮設備、員工、物料等約束確定的。

(4)生產(chǎn)過程中，不存在次品或偽劣品；每個制造企業(yè)在計劃期內對同一產(chǎn)品的制造成本都一樣。

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

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

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

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

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

每個訂單都按計劃期生產(chǎn)，違反計劃期約束的解將給予懲罰，將產(chǎn)生額外的懲罰成本。參數(shù)dr是產(chǎn)品訂單r的最后交貨期限，逾期將交付相應的懲罰成本。

bri為0-1變量，表示企業(yè)i生產(chǎn)訂單r的能力。其值為1，表示企業(yè)i具有生產(chǎn)訂單r的能力；bri為0時，表示不具有該能力。

xri(t)為0-1變量，表示企業(yè)i按期交貨的能力。當xri(t)=0，表示訂單r不在該企業(yè)i生產(chǎn)，不能按期交付；xri(t)=1，表示產(chǎn)品訂單r在企業(yè)i生產(chǎn)，并能在t計劃期按時交付。

zri為訂單r在企業(yè)i的開工期，則完工期為zri+Tri。例如：第t時段，開工期即為t時段起點，完工期即為t時段末點，同樣交貨期dr也為t時段末點。

2 訂單資源調配模型的建立

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

2.1 目標函數(shù)的建立

(1) 制造成本

計劃期[1,T]內，產(chǎn)品訂單r在企業(yè)i生產(chǎn)，單位制造成本為sri，則產(chǎn)品訂單總制造成本為：

(2)

(2)運輸成本

訂單r在企業(yè)i生產(chǎn)時，產(chǎn)生的運輸成本為cri，由于運輸方式固定，所以總運輸成本為：

(3)

(3)懲罰成本

在實際生產(chǎn)過程中，企業(yè)在訂單生產(chǎn)時，可能會出現(xiàn)提前或拖延完成生產(chǎn)任務的情況，與其產(chǎn)品的訂單價值vr相關聯(lián)。設提前/拖期情況的懲罰因子分別為α和β，則訂單r的提前/拖期懲罰成本為：

(4)

由于總懲罰成本包含提前和拖期兩種情況，則總懲罰成本為：

(5)

綜上所述，訂單調配模型的目標函數(shù)可定義為：

(6)

2.2 約束條件

(1) 訂單生產(chǎn)約束

一個訂單只能由一個企業(yè)生產(chǎn)，故有：

(7)

(8)

bri,xri(t) ∈{0,1}

(9)

式(7)保證每個訂單只能由一個企業(yè)生產(chǎn)加工；式(8)確保每個產(chǎn)品訂單r企業(yè)i能夠準時交貨；式(9)變量xri和bri是0-1變量。

(2)生產(chǎn)能力約束

企業(yè)聯(lián)盟下，各個企業(yè)制造能力不同，因此只有具備此種產(chǎn)品的生產(chǎn)能力才能進行生產(chǎn)，否則就不能生產(chǎn)。故有：

(bri-1)·xri(t)≥0

(10)

(3)開工期約束

開工期約束即表示某企業(yè)在訂單產(chǎn)品生產(chǎn)時，必須保證前一個訂單完成后才可以開始新的訂單。

為充分考慮各企業(yè)產(chǎn)品生產(chǎn)的可能性，本文從產(chǎn)品訂單r的最早開工期，最晚開工期，以及計劃期約束3個方面進行開工期進行約束。具體如下：

(11)

式(11)表示訂單r的最早開工期zri不能早于企業(yè)i生產(chǎn)其他訂單的最晚完工期的下一個計劃期[14]。

(12)

同時，針對訂單r、開工期、制造周期和運輸時長應滿足如下約束：

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

(13)

2.3 訂單資源調配模型

綜合上述分析可得，訂單資源調配模型為：

(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 改進多層編碼遺傳算法的設計與實現(xiàn)

上述的模型函數(shù)，是一類典型的非線性多約束優(yōu)化的復雜問題，涉及到的參數(shù)多，對應的數(shù)據(jù)量也龐大，針對這類問題一般采用智能算法來求解。為清楚的表達各訂單對應生產(chǎn)企業(yè)的有效配置，本研究采用改進的多層編碼遺傳算法來求解。首先，通過采用整數(shù)編碼的方式將訂單個體編碼并分為多層，每層編碼對應不同含義，一起完整表達問題的解，實現(xiàn)了一條染色體多層編碼表示復雜問題的解，同時引進個體濃度的概念，使其具有更強的適應性。

為更好地闡述改進多層編碼遺傳算法的求解過程，以5實例驗證部分，表3～6數(shù)據(jù)資料中計劃期在[1,10]內的1-8個子訂單為例進行詳細的說明。

3.1 整體模型

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

圖1對應的個體為：

[4736125831324214]

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

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

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

3.2 初始種群的生成

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

3.3 適應度函數(shù)的計算

適應度函數(shù)反應每條染色體的優(yōu)劣程度。本文的研究目標是求訂單生產(chǎn)總成本的最優(yōu)值，因此采用訂單模型函數(shù)為適應度函數(shù)。

(22)

以圖1中個體為例，根據(jù)解碼過程，計算適應度函數(shù)值。

(1)構建訂單生產(chǎn)順序矩陣A

將上述染色體解碼，得到生產(chǎn)順序矩陣A。矩陣A中第一列代表生產(chǎn)企業(yè)編號，每一行從第二位起表示在該企業(yè)生產(chǎn)的訂單編號。

(2)構建制造成本矩陣AM

根據(jù)矩陣A，表3和表4的數(shù)據(jù)資料，由制造成本函數(shù)(2)可得：

根據(jù)矩陣AM，可求得總制造成本為MC=520.9.

(3)構建運輸成本矩陣AT

根據(jù)矩陣A，表3和表5的數(shù)據(jù)資料，由運輸成本函數(shù)(3)可得：

根據(jù)矩陣AT，同理可求得總運輸成本TC=47。

(4)計算提前/拖期懲罰成本

根據(jù)矩陣A和表4的數(shù)據(jù)資料，構建訂單生產(chǎn)計劃期約束矩陣AR和訂單產(chǎn)品數(shù)量約束矩陣AA，得：

根據(jù)開工期約束，式(19)～(21)，表3～6的數(shù)據(jù)資料，計算可得訂單的生產(chǎn)調度矩陣為AS.

由矩陣A和矩陣AS可知在計劃期內1-8子訂單的生產(chǎn)調度方案。如表2所示：

表2 1-8子訂單生產(chǎn)調度方案

根據(jù)矩陣AS和表4的數(shù)據(jù)資料計算提前/拖期的懲罰成本，可得：5#訂單拖期3天，懲罰成本為60；7#訂單拖期3天，懲罰成本為69.6；6#訂單拖期1天，懲罰成本為12；8#訂單提前1天，懲罰成本為9。其他訂單準時交付。

所以，總懲罰成本為PC=150.6。

(5)計算總成本

根據(jù)目標模型函數(shù)，可得fTotal=Mc+Tc+Pc=718.5。

3.4 遺傳操作

(1) 親本選擇

為保證適應度好的染色體能夠被選擇，本文采用輪盤賭法對個體進行選擇操作。種群的規(guī)模大小為M，個體Chromi的適應度值為fitness(Chromi)，則其被選擇的概率為：

(23)

由于輪盤賭法常會出現(xiàn)適應度值優(yōu)的個體未被選入到下一更新群體的情況，同時會出現(xiàn)局部收斂的現(xiàn)象。為此，引入個體濃度對選擇算子進行了改進操作。

首先，從種群M中，找出個體屬性相同的個體，并將其歸為j類(j=1,2,…,n)。那么個體濃度為：

(24)

式中：rj表示第j類的數(shù)目。

(25)

則個體的選擇概率為：

(26)

式中：ζ∈(0,1)為選擇權重系數(shù)。

因此，目標值越小代表該染色體越出色，適應性越高，選擇概率就越大，算法的收斂速度也越快；同時，個體的濃度越大，相應的選擇概率就越小，從而避免了“早熟”的現(xiàn)象。

(2) 交叉操作

交叉算子是算法搜索求解的主要算子，交叉率的選值范圍一般為pc∈[0.2,0.9]。基于上文的編碼方式，選用整數(shù)PMX(partial-mapped crossover)交叉方式進行交叉操作，避免交叉過程中產(chǎn)生的非法染色體。具體操作如圖2所示。

(3) 變異操作

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

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

(4) 精英保留策略

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

4 實例驗證

為了檢驗所設計的改進多層編碼遺傳算法求解訂單調配問題的有效性和可行性，以某企業(yè)聯(lián)盟的生產(chǎn)訂單數(shù)據(jù)資料進行數(shù)值仿真分析與驗證。

EU下屬有某4家企業(yè)共可生產(chǎn)a、b、c和d這4大類型產(chǎn)品。假設在計劃期[1,20]內，EU接收到客戶的8大產(chǎn)品訂單生產(chǎn)需求，根據(jù)訂單的產(chǎn)品類型和各企業(yè)的制造能力對8大產(chǎn)品訂單進行重新拆分和編號，將其分成若干子訂單，并將這些子訂單分別定義為1, 2, 3, … , 16。在進行訂單生產(chǎn)時，企業(yè)生產(chǎn)能力如表3所示，對應的訂單信息如表4所示，企業(yè)計劃期內的最大生產(chǎn)量如表5所示，生產(chǎn)過程中產(chǎn)生的運輸時間和成本如表6所示。為保證各成本處于可接受的水平，設定提前，拖期交貨的懲罰因子為α=0.1,β=0.2。

算法仿真的參數(shù)設定：種群規(guī)模為50，交叉概率為0.8，變異概率為0.1，代溝為0.9，最大遺傳代數(shù)為50，算法終止。根據(jù)訂單的實際需求或專家評定，懲罰函數(shù)的權重系數(shù)為α=0.1，β=0.2。在編碼計算過程中，對應產(chǎn)品編號如表7所示。

通過仿真運算，得到改進多層編碼遺傳算法搜索過程如圖4所示。同時，最優(yōu)個體對應的產(chǎn)品訂單在1#企業(yè)-4#企業(yè)的調配方案如表8所示。產(chǎn)品訂單分配加工甘特圖如圖5所示，其中101表示1#企業(yè)生產(chǎn)1#訂單產(chǎn)品a類型，其他的依次類推。為直觀的表達本文設計算法的有效性，在參數(shù)設置相等的情況下，采用一般的遺傳算法(genetic algorithm, GA)與本文的改進的多層編碼算法(improved multi-level coding GA, I-MCGA)進行仿真試驗對比，得到的一般算法搜索過程如圖6所示，各目標結果值對比情況如表9所示。

表3 企業(yè)聯(lián)盟(EU)的bri和sri值

表4 訂單信息

表5 企業(yè)聯(lián)盟(EU)在[1,20]計劃期內的最大生產(chǎn)量qi(t)

表6 訂單在企業(yè)聯(lián)盟(EU)的運輸時間tri和運輸成本cri

表7 產(chǎn)品類型對應編碼

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

表9 不同算法的對比結果

表8列出了最優(yōu)個體中各訂單中各產(chǎn)品類型在各企業(yè)生產(chǎn)分配之間的關系，對應的加工甘特圖如圖5所示，此時最小目標值為1 285.1，其中制造成本為1 055.4，運輸成本為91，懲罰成本為138.7，末計劃期為18，滿足產(chǎn)品生產(chǎn)的最晚計劃期要求。從圖4和圖6對比可知，本文設計的I-MCGA比一般GA更早趨于收斂，尋優(yōu)能力有了較大提高。從表9不同算法對比的結果來看，本文的I-MCGA具有較高的搜尋最優(yōu)解性能，得到的各目標成本優(yōu)化結果都有較大提升。從而證明本文設計的算法具有更強的尋優(yōu)求解能力，同時也說明本文設計的產(chǎn)品訂單調配模型也是合理有效的。云制造企業(yè)聯(lián)盟可以將求解的最優(yōu)解應用到實際的生產(chǎn)分配中去，不僅可以提高產(chǎn)品的生產(chǎn)效率，也可以增加企業(yè)的經(jīng)濟效益。

5 結語

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