云制造模式下多零件的制造資源優化配置方法研究

黃 劍，劉建勝，夏芳臣

HUANG Jian，LIU Jian-sheng，XIA Fang-chen

(南昌大學 機電工程學院，南昌 330031)

0 引言

云制造是一種利用網絡和制造服務平臺，按用戶需求組織網上制造資源（制造云），為用戶提供各類按需制造服務的一種網絡化制造新模式[1]。不同的地域的制造資源進行優化組合，實現短時間、低成本以及高質量的零件的加工，正是云制造資源優化配置目標。云制造資源的優化配置是實現云制造技術的關鍵之一[2]。目前，已有采用啟發式算法研究云制造資源優化配置[2～7]。馬雪芬等提出了兩種可行的制造資源優化配置，以遺傳算法求解制造資源優化配置模型[3]；王正成等提出了利用蟻群算法求解網絡化制造跨企業資源服務鏈的構建問題[4]；尹勝等提出了多任務和多目標的外協加工資源優化配置模型，采用了遺傳算法求解了該配置模型，并以實例驗證[5]。以上已經建立了單個和多個零件的加工優化配置模型，但未對多個零件的工序選擇的候選資源存在關聯進行研究，這樣會形成是單個零件配置的累加。針對存在的問題，本文對多個零件的工序選擇候選資源存在關聯情況下，提出以時間(T)和成本(C)為多目標的多零件云制造資源優化配置模型，并利用遺傳算法(Genetic A1gorithm，GA)對該模型進行了求解。

1 問題描述

當企業同時存在多個零件需要同時加工，由于自身的生產能力或技術水平無法滿足要求，需要求助于外部制造資源來完成零件幾個或者多個工序加工。在云制造環境下，包括M個協同加工企業(包含本企業在內)，需要同時加工n個零件，每個零件j包含p道協同工序。

根據協同加工企業和零件工序情況，多個零件工序會出現選擇同一候選制造資源組，因此，多個零件選擇資源會存在制約關系。如圖1所示，在同一工序層中，不同零件工序選擇的候選資源組會出現不同或者相同。當工序選擇的候選資源組不同時，不同零件工序選擇的候選資源是相互獨立，多個零件工序與單個零件工序選擇候選加工資源是一樣；當工序選擇的候選資源組相同時，會出現加工等待的情況，即一個零件的一道工序加工完成后，才能加工另一個零件。這樣，完成零件加工的時間包含加工時間和運輸時間，還需要包含等待加工時間。

圖1 多個零件工序選擇候選資源存在關聯示意圖

云制造服務平臺提供給用戶的資源一定是有限的范圍下，而不是無限數目。如圖2所示，多個零件進行優化配置時，若同一工序層工序同時選擇資源，則出現等待加工時間的情況可以分成兩大類：1)n＞m時，一定要考慮等待加工時間；2)n≤m時，有兩個及以上的工序選擇同一資源，需要考慮等待加工時間。

圖2 工序與相同候選資源組的數量關系

2 數學模型

2.1 目標函數

云制造資源的優化配置時，需要考慮包括時間、成本、質量、企業信譽及可靠性等要素。從市場需求的角度出發，本文以時間（T）和成本（C）為優化目標，并建立如下目標函數。

2.1.1 時間目標函數

當多個零件進行外協加工時，出現同一工序層的工序選擇相同的制造資源組的情況下，需要考慮加工零件的等待時間。等待加工時間計算公式：

式中：tp、tq為零件p、q前m?1道工序的總加工時間(未含有等待加工時間)；tp,i,u、tq,i,v

零件i的外協工序j在候選資源u處所耗費的總時間為：

因此，其時間目標函數：

式中：n為外協加工的零件數量；mi為零件i外協加工工段數量；ri、j為零件i的工序j所對應的候選加工資源數數量；ji,j,k為決策因子，若零件i的工序j選擇候選資源k，則決策變量為1，否則為0。

2.1.2 加工成本目標函數

式中： 為零件i的外協工序j在候選資源u處的加工成本；為零件i外協工序j在候選資源u與下一道工序i+1在候選資源v之間的運輸成本。

2.1.3 加權求和

在云制造服務平臺下，不同用戶對產品的最長交貨期、總成本等方面要求的側重點不同。同時，目標函數之間既相互關聯，又相互制約。通過采用最通常的權重法，將多目標轉化為單目標。

式中：w1、w2為時間、成本的權重系數，w1+w2=1；Tmax、Cmax為用戶要求的最長交貨期、可以支付的最高成本。

2.2 約束條件

面向多零件的云制造資源優化配置模型主要存在時間約束、成本約束和決策因子約束。

1）目標值約束

2）決策因子約束

云制造環境下，一道工序下的相同零件只能分配給一個候選資源加工，即：

3 遺傳算法求解

遺傳算法是一種全局性的概率搜索算法，具有對函數的性態無要求、并行性很高和搜索效率高,以及全局最優解求解能力較好等獨特的性能[3]。但是，采用遺傳算法對面向多零件的云制造資源優化配置模型求解，需要解決以下問題。

1）編碼。 在遺傳算法中，設計合適的編碼方法，對于問題的表達至關重要。整數編碼對于組合優化問題最為有效[8]。因此，本文采用整數編碼求解。

2）最小化問題的適應度函數。 標定是將目標函數映射成適值度函數，根據不同問題，采取不同的標定方法，線性標定中的參數隨著迭代次數的增加而變化時就得到了動態線性標定。動態線性標定是最常用的一種適值標定方法，計算公式是：

圖3 選擇壓力的調節

3)群體規模。一般來說，遺傳算法中種群規模越大越好，但是種群規模的增大也將導致運算時間的增大。假設種群規模為NP，染色體長度為1，通常情況下，1.5l ≤NP＜2l/2。

4)選擇策略。Ho11and提出的輪盤賭選擇是最知名的選擇方式[9]。根據每個染色體的適應值的比例來確定該個體的選擇概率或生存概率。若個體為i，適應值為 Fi，種群規模為NP，則該個體的選擇概率為：

5)交叉概率(pc)和變異概率(pm)。 由于交叉和變異概率跟隨問題的不同，可能有不的取值。對整數編碼而言，交叉概率 pc=0.90～1.00，變異概率 pm=0.005～0.05，Pm＜0.05,否則，遺傳算法的進化過程近似于隨機搜索行為。

6)遺傳算子操作。 單切點交叉是由Ho11and提出的最基礎的一種交叉方式，但由于存在信息量小、末尾基因總是被交換等缺陷。在實際中大量采用兩點交叉算子，本文采用雙切點交叉算子。

7)修復。交叉操作和變異操作后，分別需要根據公式(7)～(9)修復個體滿足約束條件。

8)終止準則。最大迭代次數作為終止準則。

4 實例

某生產企業有3個零件需要同時協同加工，其相關信息如表1、表2所示。本實例是在Visua1 Studio 2010 +SQL server2008環境下進行。 程序開始運行后，設置遺傳參數：種群規模為14，最大迭代次數為100，。進行優化時，權重系數分別為w1=0.6，w2=0.4，目標值的約束為：TAmax=90、TBmax=275、TCmax=140、CAmax=850、CBmax=800、CCmax=1270。圖4、圖5分別是零件加工時間的讀取界面和運行結果界面，其中最后獲得了最優的加工路線為：0-0-0-1-0-0-1-0。對應的外協加工資源優化配置結果如表3所示。

圖4 零件數據讀取界面

圖5 程序結果界面

表1 候選資源的加工時間T、加工成本C數據

表2 候選資源之間的運輸時間 t'(h)、運輸成本 c'(元)

表3 最終優化配置結果

5 結論

本文探討了多個零件的工序選擇相同的候選資源時，云制造資源的優化配置問題，建立了基于時間(T)和成本(C)為目標云制造多零件制造優化配置數學模型。通過本文設計的遺傳算法求解模型，并采用算例驗證了模型及算法的有效性。但云制造平臺環境下，用戶要求的目標的優化配置不僅局限于時間和成本，因此，還需要進一步研究在云制造環境下的優化目標體系，以及多目標的優化配置模型及優化方法。

[1] 李伯虎,張霖,王時龍,等.云制造—面向服務的網絡化制造新模式[J].計算機集成制造系統,2010,16(01)∶1-7+16.

[2] 王時龍,宋文艷,康玲,等.云制造環境下的制造資源優化配置研究[J].計算機集成制造系統,2012,18(7)∶1396-1405.

[3] 馬雪芬,戴旭東,孫樹棟.面向網絡化制造的制造資源優化配置研究[J].計算機集成制造系統,2004,10(5)∶179-193.

[4] 王正成,潘曉弘,潘旭偉.基于蟻群算法的網絡化制造資源服務鏈構建[J].計算機集成制造系統,2010,16(01)∶174-181.

[5] 尹勝,尹超,劉飛,等.多任務外協加工資源優化配置模型及遺傳算法求解[J].重慶大學學報,2010,33(03)∶49-55.

[6] 劉衛寧,劉波,孫棣華.面向多任務的制造云服務組合[J].計算機集成制造系統,2013,19(01)∶199-209.

[7] 韋韞,李東波,童一飛.面向服務的網絡化協同制造資源多目標重組優化調度[J].農業機械學報,2012,43(03)∶193-199.

[8] 玄光男,于歆杰.遺傳算法與工程優化[M].北京∶清華大學出版社,2004.

[9] Ho11and J.Adapatation in Natura1 and Artificia1 Systems[A].Kos,Greece∶ECCOMAS,2007∶50(55)∶94-101.