基于遺傳算法的模具制造網(wǎng)格服務配置研究

王 毅 王宗忠 陳慶新 毛 寧

1.仲愷農(nóng)業(yè)工程學院,廣州,510225 2.廣東工業(yè)大學,廣州,510090

基于遺傳算法的模具制造網(wǎng)格服務配置研究

王 毅1,2王宗忠2陳慶新2毛 寧2

1.仲愷農(nóng)業(yè)工程學院,廣州,510225 2.廣東工業(yè)大學,廣州,510090

從制造項目的實際需求出發(fā),在考慮制造網(wǎng)格中在制品物流的情況下,研究了制造網(wǎng)格環(huán)境中服務的優(yōu)化配置問題,并提出了一種兩階段服務配置方法。首先根據(jù)項目任務的時間窗進行了任務候選服務節(jié)點集合的搜索匹配,進而使用了遺傳算法進行服務的優(yōu)化配置。在遺傳算法中,采用了基于服務節(jié)點的染色體編碼方法,并設計了染色體生成、選擇、交叉、變異的操作算法。最后進行了實例驗證,得到了較為滿意的配置結果。

制造網(wǎng)格;服務配置;網(wǎng)格物流;遺傳算法

0 引言

作為制造網(wǎng)格的核心問題之一,制造服務的優(yōu)化配置在制造網(wǎng)格環(huán)境中起著非常重要的作用。目前,針對制造網(wǎng)格服務資源配置問題的研究主要集中在制造資源的發(fā)現(xiàn)、制造資源的服務能力匹配上[1-6]。資源發(fā)現(xiàn)主要研究制造資源的搜索技術以及搜索算法,以提高資源發(fā)現(xiàn)的速度與效率,研究方法主要包括面向對象、本體以及OW L-S技術等[1,7-10]。制造資源的能力匹配則主要集中在對制造資源服務能力的評估上。

筆者認為,在進行服務配置的過程中,除了必要的服務搜索技術與能力匹配方法之外,還需要綜合考慮到項目的信息(如項目總工期、總成本的約束,項目的任務分解粒度、任務的分解方式以及任務之間的網(wǎng)絡約束關系等),不能脫離項目具體的需求,需要從項目的角度來進行宏觀的、統(tǒng)一的服務調(diào)度與配置,從而避免產(chǎn)生局部配置優(yōu)化。

另一方面,制造網(wǎng)格具有一個不同于計算網(wǎng)格的典型特點,就是制造網(wǎng)格向客戶提供物質性的服務,而非計算網(wǎng)格通常所提供的信息性服務。也就是說,在制造網(wǎng)格的不同資源服務節(jié)點之間存在著在制品物流的問題(如坯料、半成品、成品等在不同資源服務節(jié)點之間的傳遞運輸)。因此,從狹義的視角來看,在一定的時間、區(qū)域和成本約束范圍之內(nèi),制造網(wǎng)格所能夠提供的服務能力還是要受到一定限制的,所以,制造網(wǎng)格的服務配置問題同時也不可避免地要受到制造網(wǎng)格在制品物流的約束。

綜上所述,我們認為在制造網(wǎng)格中進行服務配置還需要考慮如下兩點:①從項目的角度進行服務的最優(yōu)選擇與配置;②制造網(wǎng)格在制品物流的約束。在本文中,我們簡化了關于制造資源服務能力的描述,同時,假設在標準的制造網(wǎng)格環(huán)境中,資源服務節(jié)點所封裝的服務能力、服務質量、服務費用,以及制造網(wǎng)格的物流運輸時間與運輸費用都是標準的。因此,本文的研究內(nèi)容就是在考慮制造網(wǎng)格在制品物流的情況下,為項目分解后的每一個子任務選擇一個合適的資源服務節(jié)點,使其組合在一起后,能夠在滿足項目總工期的約束條件下,總成本最低。

1 問題描述

1.1 一般性描述

定義1 服務能力(service capability)指的是制造資源具有完成某種類型任務的能力。

定義2 服務容量(service capacity)指的是制造資源在某段時間內(nèi)所能夠提供的某種服務能力的最大負載。

問題的一般性描述如下:設一個項目的總工期為T,可分解為n個任務,并且已知任務的分解信息、每個任務的工期及其服務能力需求和服務容量需求。每個任務均有多個資源服務節(jié)點能夠滿足任務的能力需求與容量需求。目標是在滿足項目總工期的約束下,合理地對這些資源服務節(jié)點進行選擇與配置,使得完成該項目的總成本最低。在此需要注意的是,一個資源服務節(jié)點可能提供多種服務能力,意味著不同的任務可能由同一個資源服務節(jié)點完成。

1.2 數(shù)學描述

在進行問題描述之前首先作如下假設:

(1)一個資源服務節(jié)點至少能夠提供一種服務能力;

(2)各個資源服務節(jié)點所具有的相同類型的服務能力所提供服務的質量是相同的,即在本文中不考慮服務質量的問題;

(3)同一個任務在不同的資源服務節(jié)點上進行加工所需要的服務費用都是相同的;

(4)任務的工期是確定的,并且同一個任務在不同的資源服務節(jié)點上進行加工所需要的工期都是相同的;

(5)同一個任務只能放在一個資源服務節(jié)點上進行加工;

(6)一個任務一旦開始在一個服務節(jié)點上進行加工,則不可停止,即服務節(jié)點提供的服務能力是連續(xù)的;

(7)不同資源服務節(jié)點之間的運輸成本與該服務節(jié)點之間的距離成線性關系,不考慮運輸物料質量的問題;

(8)不同資源服務節(jié)點之間的運輸時間與該服務節(jié)點之間的距離成線性關系;

(9)設計單元的使用不存在路徑的問題,因為設計的過程完全可以通過網(wǎng)上的溝通來進行信息的傳遞,資源的傳遞時間與費用可以忽略不計;

(10)任務在同一個資源服務節(jié)點之內(nèi)轉移,運輸時間和費用設為零。

問題的數(shù)學描述模型如下:

一套模具的生產(chǎn)過程可以分解為n個任務,每個任務為wi,任務的類型為w i,t(其值枚舉為設計類型D和加工類型M),任務的工期為di,最早開工期為,最早完工期為,最晚開工期為,最晚完工期為dlfi,任務的時間窗定義為di=[desi,dlfi],計劃開工期為,計劃完工期為,模具的交貨期定義為 T。每個任務所需要的服務能力為,所需要的服務容量為,在某段時間t內(nèi)所需要的服務能力的容量為wvi(t),任務完成需要的費用為。假設有m個資源服務節(jié)點sg(g=1,2,…,m),每個資源服務節(jié)點所能夠提供的服務能力為,其中k(k≥1)表示該服務節(jié)點所提供服務能力的種類。資源服務節(jié)點在某段時間t內(nèi)能夠提供的第k種服務能力的容量為(t)。任意兩個資源服務節(jié)點之間的距離定義為Lg,h。

將目標函數(shù)定義為在滿足項目交貨期的前提下,項目完工總成本(包括任務的加工成本和任務在不同服務節(jié)點之間的運輸成本)最低。目標函數(shù):

其中,u為運輸時間常數(shù)。定義Pj表示任務w j的所有緊前任務的集合,g表示任務w i從資源服務節(jié)點候選集合si中所選擇出來的服務節(jié)點,g=r(si),h表示任務w j從資源服務節(jié)點候選集合sj中所選擇出來的服務節(jié)點,h=r(sj)。約束條件1表示任務w j的開始時間必須大于或等于其所有緊前任務完成并且運輸?shù)郊庸と蝿誻 j的服務節(jié)點上的最大時間。約束條件2保證了所選擇的服務節(jié)點能夠提供任務所需要的服務能力以及在相應的時間窗內(nèi)能夠提供任務所需要的服務容量。約束條件3確保了項目不能夠拖期。約束條件4保證了任務只能在一個服務節(jié)點上進行加工。約束條件5保證了一個任務(在同一個資源服務節(jié)點內(nèi)或不同的資源服務節(jié)點之間)只能運輸一次。

2 算法簡述

解決該問題的步驟分為如下兩個階段。

第一個階段為資源服務節(jié)點的搜索階段。首先根據(jù)項目的信息以及項目的分解信息(任務的工期、任務之間的緊前緊后約束關系),計算出每個任務的時間窗di=[desi,dlfi]。在進行任務時間窗計算的時候,不考慮在制品在不同資源服務節(jié)點之間的運輸問題,因此任務的時間窗是被放大的。其次,根據(jù)每個任務對服務能力的需求與服務容量的需求,結合任務的時間窗信息,進行資源服務節(jié)點的搜索與匹配。如果一個資源服務節(jié)點能夠滿足約束條件2(其中t=di)的要求,則添加到任務服務節(jié)點候選集合si中(si的容量為si,count,可以根據(jù)需要提前設定)。在這個階段中,針對項目中的每一個任務,為其搜索并返回一個滿足其能力需求的服務節(jié)點候選集合。

第二個階段為資源服務節(jié)點的選擇與配置階段?？紤]在制品在不同資源服務節(jié)點之間的運輸時間與費用,在滿足項目總工期約束的前提下,以項目完工總成本最低為優(yōu)化目標,從項目的角度來對每個任務的候選服務節(jié)點集合中的服務節(jié)點進行優(yōu)化選擇與配置。在這個優(yōu)化配置的過程中,本文采用了遺傳算法來求解問題。

2.1 資源服務節(jié)點搜索算法

第一個階段根據(jù)任務的時間窗尋找任務候選服務節(jié)點集合s的算法描述如下:

(1)對任務集W中的任務進行網(wǎng)絡計劃計算,得到每個任務的時間窗di;

通過這個過程,我們可以為每個任務找到一個滿足任務需求的資源服務節(jié)點集合si,其中 z表示任務候選集合的最大容量是提前設定的,也可以根據(jù)每個任務的要求而設定不同的值,如zi。

2.2 資源服務節(jié)點的選擇配置遺傳算法

2.2.1 編碼

在本文中,采用二進制編碼,用基因位置表示任務、基因值表示任務所選擇的滿足要求的服務節(jié)點,如圖1所示。

圖1 染色體編碼

第k條染色體可表示為Ck=[r(s1),r(s2),…,r(sn)],其中r(si)表示第i個任務wi從資源服務節(jié)點候選集合si中選取的一個服務節(jié)點。由于任務之間存在緊前緊后的約束關系,因此,為了避免任務在執(zhí)行順序上的沖突,本文使用了隨機產(chǎn)生任務優(yōu)先權的方法[11]來對任務進行拓撲排列,從而產(chǎn)生一個可順序執(zhí)行的任務序列集合W。另外,由于在第一階段進行任務時間窗計算以及資源服務節(jié)點查找、匹配的時候,并沒有考慮到在制品在不同資源服務節(jié)點之間的運輸問題,同時由于緊前緊后任務時間窗之間部分重疊,因此,并不是任務候選資源服務節(jié)點集合中所有的服務節(jié)點都能夠滿足任務的實際要求。所以,在進行染色體生成的時候,為了避免產(chǎn)生不可行的染色體,必須首先進行染色體可行性驗證。

2.2.2 遺傳算子的形式設計

(1)適應度函數(shù)。本問題的目標函數(shù) fc為項目完工總成本最低,因此染色體的適應度函數(shù)可以定義為

其中,C l為染色體集合;γ為常數(shù),數(shù)值為0～1。

每個染色體的適應度概率可以根據(jù)如下公式進行計算:

(2)選擇算子。遺傳算法的選擇運算是對群體中的個體進行優(yōu)勝劣汰的操作,是從舊種群中選擇生命力強的個體以產(chǎn)生新的種群的過程。選擇操作可用多種方法來實現(xiàn),最常用的選擇算子是基本遺傳算法的比例選擇算子(輪盤賭的方法)。同時,為了避免種群中最好的染色體在交叉、變異的過程中被破壞,經(jīng)常與最優(yōu)策略結合在一起使用,以加強對下一代中最好染色體的保護。本文中使用了這種輪盤賭與最優(yōu)策略結合的方式來進行染色體的選擇操作。

(3)交叉算子。遺傳算法的交叉操作用于組合出新的個體。在本文中,采用了基本的單點隨機雜交的方法,由計算機隨機產(chǎn)生一個雜交位置k,然后根據(jù)提前設定的交叉概率P c進行配對染色體的交叉。設參與運算的兩個個體分別為父親P0和母親P1,選擇的隨機正整數(shù)k滿足1≤k≤n。需要注意的是,在交叉的過程中同樣可能會產(chǎn)生不可行的染色體,因此,在交叉的過程中同樣要進行染色體的可行性驗證,保證交叉后的染色體為可行解,否則不能進行交叉。染色體交叉過程如圖2所示。

圖2 染色體交叉過程

(4)變異算子。遺傳算法的變異運算是產(chǎn)生新個體的輔助方法。通過使用變異算子來調(diào)整染色體中的部分基因,從局部的角度出發(fā)使得染色體更加逼近最優(yōu)解。本文采用隨機單點變異的方法。即隨機產(chǎn)生一個變異位置,然后對該位置上的基因根據(jù)變異概率Pm進行變異,如圖3所示。

圖3 染色體變異過程

3 算例論證

本文以一套模具的項目生產(chǎn)過程為例來進行實例驗證,設該套模具的項目工期為52天,模具的生產(chǎn)過程可分解為12個子任務。圖4表示了各個子任務之間的緊前緊后約束關系,表1表示了任務的詳細需求信息。其中,Pi(i=1,2,…,12)表示完成某種類型任務需要的制造資源。假設存在16個不同的服務節(jié)點,服務的詳細信息如表2所示,服務節(jié)點之間的距離如表3所示,服務的能力費率如表4所示,服務節(jié)點之間單位距離的運輸費率為25元。在滿足項目總工期的約束下,求解使得成本最低的解決方案。遺傳算法的初始化參數(shù)設定如表5所示。

圖4 項目網(wǎng)絡圖

系統(tǒng)采用的CPU為Inter(R)Core(TM)Duo T2350 1.86G,內(nèi)存為2GB,計算時間為3.2s。采用本算法計算后得到了較滿意的結果([任務編號服務節(jié)點時間窗編號任務開始時間任務結束時間]):[1 s31 2 5;2 s51 5 10;3 s41 10 14;4 s62 14 17;5 s8 1 10 15;6 s9 1 16 19;7 s7 2 19.8 23.8;8 s10 2 24.9 27.9;9 s10 1 27.9 31.9;10 s13 1 34 40;11 s14 1 42 47;12 s16 1 48.96 50.96],總成本為6188元。

表1 項目任務

表2 服務節(jié)點服務能力

表3 服務節(jié)點距離

表4 能力費率

表5 初始化參數(shù)

4 結束語

本文在考慮制造網(wǎng)格中在制品物流的情況下,從項目的角度研究了制造網(wǎng)格環(huán)境下制造服務資源的優(yōu)化配置問題。提出了一種兩階段服務配置方法。在第一個階段中,首先在不考慮在制品物流的情況下進行了任務時間窗的計算,進而通過任務的搜索與匹配得到了任務的候選資源服務節(jié)點集合。在第二個階段中,采用了遺傳算法從項目的宏觀角度對候選資源服務節(jié)點進行了優(yōu)化選擇與配置。在文中設計了基于服務的染色體方式,并設計了染色體的選擇、交叉、變異的算法,以及染色體的可行性驗證方法。最后進行了實例的演算,表明該算法是一種切實可行的、有效的制造網(wǎng)格服務配置方法。

[1] 溫浩宇,任小龍,徐國華,等.制造網(wǎng)格的搜索算法研究[J].中國機械工程,2004,15(22):2014-2017.

[2] 蔡銘,林蘭芬,陳剛,等.網(wǎng)絡化制造環(huán)境中制造資源的智能發(fā)現(xiàn)技術研究[J].計算機集成制造系統(tǒng)—CIMS,2003,9(7):589-594.

[3] 劉麗蘭,俞濤,施戰(zhàn)備,等.自組織制造網(wǎng)格及其任務調(diào)度算法[J].計算機集成制造系統(tǒng)—CIMS,2003,9(6):449-455.

[4] 李浩,羅國富,謝慶生.基于應用服務提供商的動態(tài)聯(lián)盟制造資源評估模型研究[J].計算機集成制造系統(tǒng),2007,13(5):862-868.

[5] 陶飛,胡業(yè)發(fā),丁毓峰,等.基于Agent的制造網(wǎng)格資源優(yōu)選評估模型研究[J].中國機械工程,2005,16(24):2192-2197.

[6] 劉麗蘭,俞濤,施戰(zhàn)備.制造網(wǎng)格中基于服務質量的資源調(diào)度研究[J].計算機集成制造系統(tǒng)—CIMS,2005,11(4):475-480.

[7] 路松峰,龔四平.基于語義的Web服務發(fā)現(xiàn)算法優(yōu)化[J].計算機工程與設計,2007,28(12):2854-2857.

[8] 葉蕾,張斌.基于功能語義的W eb服務發(fā)現(xiàn)方法[J].計算機研究與發(fā)展,2007,44(8):1357-1364.

[9] 潘云峰,蔡明.基于OW L-S的W eb服務匹配模型設計[J].計算機工程與設計,2007,28(9):2145-2147.

[10] 馬雪芬,戴旭東,孫樹棟.面向網(wǎng)絡化制造的制造資源優(yōu)化配置研究[J].計算機集成制造系統(tǒng)—CIMS,2004,10(5):523-527.

[11] 玄光男,程潤偉.遺傳算法與工程優(yōu)化[M].北京:清華大學出版社,2004.

Study on Service Scheduling in Mould Manufacturing Grid Based on Genetic Algorithm

W ang Yi1,2Wang Zongzhong2Chen Qingxin2Mao Ning2
1.Zhongkai University o f Agriculture and Engineering,Guangzhou,510225 2.Guangdong University o f Technology,Guangzhou,510090

In accordancewith the actual demandsof amanufacturing project,taking into accountof the material flow s,the service scheduling problem under the manufacturing grid environment was studied,and a two-stage service schedulingmethod was put forward.First,the search for candidate service node sets for each task in the projectwas carried out based on the task time window s.Then,given the obtained candidate service node sets,a genetic algorithm was used to schedu le the services.In the genetic algorithm,the chrom osome coding method was based on the service node.And the algorithms for the operations of creating,selecting,crossing,and mutating of chrom osomes were designed carefully.In the end,the effectiveness of the algorithm was verified with an examp le of a simplem ould project.

manu facturing grid;service schedu ling;grid material flow;genetic algorithm

TH 166

1004—132X(2011)11—1307—05

2010—07—30

國家自然科學基金資助項目(50675039);國家高技術研究發(fā)展計劃(863計劃)資助項目(2006AA 04Z132);廣東省自然科學基金資助項目(05200197);廣東省科技攻關項目(2004B10201030)

book=1317,ebook=249

(編輯 王艷麗)

王 毅,男,1974年生。仲愷農(nóng)業(yè)工程學院機電工程系副教授,廣東工業(yè)大學機電工程學院博士研究生。主要研究方向為知識管理、數(shù)據(jù)挖掘。發(fā)表論文10余篇。王宗忠,男,1977年生。廣東工業(yè)大學機電工程學院博士。陳慶新,男,1963年生。廣東工業(yè)大學機電工程學院教授、博士研究生導師。毛 寧,女,1962年生。廣東工業(yè)大學機電工程學院教授。