基于信息素的制造系統動態協調研究

王 雷，李 震，劉志虎，袁偉東

(1.安徽工程大學先進數控和伺服驅動技術安徽省重點實驗室，安徽蕪湖 241000；2. 安徽工程大學機械與汽車工程學院，安徽蕪湖 241000；3.中國船舶科學研究中心，江蘇無錫 214082)

基于信息素的制造系統動態協調研究

王 雷1,2，李 震1，劉志虎1,2，袁偉東3

(1.安徽工程大學先進數控和伺服驅動技術安徽省重點實驗室，安徽蕪湖 241000；2. 安徽工程大學機械與汽車工程學院，安徽蕪湖 241000；3.中國船舶科學研究中心，江蘇無錫 214082)

受螞蟻覓食行為模型與零件的生產加工工藝選擇的相似性的啟發，提出了基于信息素的任務分配協調機制。以信息素為介質，給出了制造系統生產加工工藝選擇的靜態和動態協調算法。仿真結果表明，通過此方法既實現了加工成本的相對優化，又實現了制造系統中各設備的均衡利用，并對制造系統內、外部環境變化具有良好的自適應性，為解決制造系統中的生產加工工藝選擇問題提供了一種切實有效的方法。

信息素；任務分配；協調機制；動態協調

當今制造業面臨著非常嚴峻的挑戰，其原因在于市場競爭越來越多地表現為動態化、全球化和用戶驅動的特點。所以，制造系統所面臨的內外環境越來越充滿了隨機性與不確定性，例如：緊急加工工件的到來，生產設備的故障與修復，不可預知工件數量的增加變化、交貨期時間的變更等。如此諸多的隨機性和不確定因素，對制造系統的協調機制提出了更高的要求，以動態地響應諸多的變化，從而在滿足生產環境約束(如交貨期、設備負荷率、加工先后次序等)的前提下，使得生產加工工藝與加工設備得到合理的匹配，使得制造系統全局的運行效果達到較優或者近優。

蜜蜂、螞蟻等低等動物盡管具備極低的智能，但是卻能通過彼此之間的交互產生全局行為來提高對環境的自適應性。螞蟻的探路覓食方法就是一個典型的群居動物行為實例[1]。DORIGO等在觀察螞蟻從巢穴到食物源的尋找路徑的過程中發現，螞蟻盡管不能從外部環境中得到任何關于路徑的全局信息，但是總能找到巢穴與食物源之間的最短路徑。經研究發現，螞蟻的這種群體協作功能是通過一種遺留在其往返路徑上的叫做信息素(Pheromone)的一種揮發性化學物質來進行協調和通信的。通過這種信息素物質，使得螞蟻群體表現出極其強大的優化能力[2]。蟻群算法原理就是根據螞蟻群體覓食的思想而設計出來的一種群體智能優化算法，該算法在作業車間調度問題[3-5]、任務分配問題[6-7]、機器人合作問題[8]等領域得到了廣泛的研究與應用。筆者受螞蟻覓食行為模型與零件的生產加工工藝選擇的相似性的啟發，提出了基于信息素的任務分配協調機制，以信息素為介質，給出了制造系統生產加工工藝選擇的靜態和動態協調算法。

1 基于信息素的協調機制

基于信息素的協調機制源于螞蟻的覓食活動，盡管單個螞蟻的行為比較簡單，但整個螞蟻群體表現為高度機構化的社會組織，在許多情況下能夠完成遠遠超過單個螞蟻能力的復雜的任務[9]。這種能力來源于螞蟻群體中的依靠信息素作為通信物質的個體協作行為。螞蟻在覓食過程中能過通過相互協作找到食物源與巢穴之間的最短路徑[10-12]。

圖1 基于信息素的協調原理Fig.1 Coordination principle based on pheromone

如圖1所示，螞蟻群體不但能夠協調完成復雜的任務，而且還能夠自適應外部環境的變化，如圖1a)所示，無論路徑長短，各只螞蟻一開始的分布是均勻的，螞蟻總是先按照相同的概率選擇可行路徑。螞蟻在途經的過程中，能夠在其經過的路徑上留下信息素，而且能夠感知這種化學物質的存在及其強弱，并以此指導自己的行為，螞蟻更傾向于向信息素量大的路徑上移動。相等時間內較短路徑上的信息素的遺留量就比較多，則選擇較短路徑上的螞蟻也隨之增多，如圖1c)所示。不難發現，由于大量螞蟻組成的蟻群集體行為表現出了一種信息正反饋現象，即某一路徑上走過的螞蟻越多，則隨后的螞蟻選擇該路徑的概率就越大，螞蟻個體之間就是通過這種信息交流機制來進行覓食，并最終沿著最短路徑進行，如圖1d)所示。

通過對螞蟻覓食行為的深入研究表明，可以用式(1)表示螞蟻選擇路徑的行為模型[13]：

(1)

式中：pi表示選擇路徑i的概率；ki，kj分別表示螞蟻在路徑i，j上留下的信息素強度；J為通路數目；φ是路徑上無信息素遺留時對螞蟻的吸引程度。

2 基于信息素的制造系統動態協調

2.1基于信息素的靜態協調分配算法

對某一任務的加工可以有多條加工工藝路線完成，而由于設備性能的不同導致任何一條生產加工工藝路線所需要的總生產成本也是有所不同的，所以，可以理解每條加工工藝路線就分別擁有不同量值的信息素，與這些加工工藝路線對每一種加工任務的吸引強度分別相對應。如果在某條工藝路線上不具備加工某類生產任務的話，則設置該條工藝路線上的信息素值為0，以防止該條工藝路線再吸引此類加工任務而使完工時間等性能指標受到一定程度的影響。

然而，由于只能有某一條或某幾條加工工藝路線可以完成即有的任務的加工。所以，為了模仿螞蟻覓食的探路過程，并與加工過程中的真實情況相吻合，首先設置所有能夠加工某類生產任務的工藝路線上的信息素初始值c0，即

(2)

當有生產任務需要選擇工藝路線進行加工時，該任務首先感知每條加工工藝路線對此任務下一個需要加工的工件信息素量值，按每條加工工藝路線所需要的總生產成本大小所對應的信息素值來對加工工藝路線進行選擇。h為路徑選擇非線性因子，在此設置為1，則對任何一個加工任務，加工工藝路線j被加工工件i選擇的概率p(i)大小根據式(3)計算得：

(3)

式中，每個工件可以選擇的最大可替代加工工藝路線的數量為Rp。

圖2 基于信息素的工藝路徑選擇算法流程Fig.2 Process path selection algorithm based on pheromone

當某條加工工藝路線被某一生產任務的一個工件選擇后，要對該條加工工藝路線進行一定的獎勵，該路線對對應任務的信息素的吸引力用信息素獎勵函數A(c)來增強。與此同時，由于加工工藝路線被生產任務的選擇原因，在被選擇的加工工藝路線中所涉及到機床的可利用有效加工時間也會越來越少，為此減少該工藝路線的信息素強度，本文用信息素懲罰函數P(t)(0

ρ[i][j]=
ρ[i][j]+A(c)-P(t)。

(4)

式中：某一條加工工藝路線加工某類工件所需要的總加工成本用c表示；增加的信息素量值用A(c)表示，它是總加工成本的減函數。這樣才能保證較優的加工工藝路線上的信息素得到加強的機會增多，被選擇的概率加大。

當某條加工工藝路線中所擁有的某設備的可利用時間小于該設備能夠加工的某種工件的對應某一加工工序所需工時的時候，自動置該條加工工藝路線的信息素為零。另外，當某個設備的可利用時間為零時，置該資源涉及到的所有加工工藝路線的信息素為零[14-15]。圖2是基于信息素的靜態協調分配算法流程圖。

然而，在實際生產中存在大量隨機事件，如新任務插入、訂單的取消、交貨期變動、機器故障等。為此，針對這些隨機事件需要動態的協調來合理的進行任務的分配。由于篇幅問題，本文主要從新任務加入這種情況來具體研究基于信息素的動態協調算法。有關設備故障、交貨期變更等動態協調問題將在后續的工作中展開研究。

2.2新任務到達時的動態協調

新任務所涉及的范圍較大，可以指種類不同的加工工件的集合，這里為了簡單描述基于信息素的任務分配的動態協調過程，假設新任務中僅包含一種類型工件的加工任務(多種類型的任務也可依此類推)。這里只有新任務的加工工藝特征信息(如j1→j2→…→ji(ji代表刨、磨、車、銑等加工工藝特征信息))是已知的。圖3是新任務到達時的動態協調過程。

圖3 新任務達到時的動態協調流程Fig.3 Dynamic coordination mechanism for new tasks

具體動態協調算法步驟如下。

1) 首先為新任務每道加工工序選擇具有匹配工藝能力的機床。因為在一個制造單元或者車間內部具有某種加工工藝能力的機床往往不止一臺，也就是在機床設備之間具有可選擇性或者可替代性，所以新任務的每一道加工工序通?？蓪鄠€機床可供選擇。

2) 將之前生產任務選擇工藝路線時在每臺可替代機床上遺留的信息素量各自相加，可由式(5)計算所得。

(5)

由式(5)所計算出的信息素值大小的差異正體現各個加工機床在加工某種加工工藝特征時所表現出來的能力的強弱。在此條件下運行基于信息素的工藝路徑選擇算法，將新任務中每個工件的第j道加工工序特征分配給步驟1)中所涉及到的機床，選中每個設備的概率可由式(6)計算所得。

(6)

3) 更新機床所擁有的信息素的值。

4) 為新任務中所有工件的第(j+1)道加工工序特征選擇機床，直至新任務的所有加工工藝特征都選擇所對應能力的機床為止。

5) 對新任務的每道加工工藝特征在各可用機床上的加工數量進行統計，將承擔工件任務較多的機床自組織成一個主虛擬制造單元，將承擔工件任務數量較少的機床自組織成多個或一個副虛擬制造單元。

6) 主、副虛擬制造單元在完成新任務加工后自動解散并恢復到之前所屬的單元狀態。

3 應用算例

現有P1，P2和P3等3個任務需要加工，第1個加工任務的加工數量是N1=80，第2個加工任務的加工數量是N2=90，第3個加工任務的加工數量是N3=70。可以使用的制造資源集合包括M1，M2，M3，M4，M5，M6，M7，M8和M9等9臺加工機床。表1所示的是每一加工任務的加工工藝流程。假設所有任務的交貨時間為D=1 500(時間單位)。參數選擇如下：c0=100，α(c)=1 000/c，β(c)=80/c，p(φ(tmin)，α(c))=φ*α(c),其中φ(tmin)=D/(D+9tmin)。

表1 不同加工任務的加工工藝路線情況Tab.1 Processing routes for different tasks

注：單位加工成本單位為元。

利用基于信息素的工藝選擇的靜態協調算法，任務協調分配的結果如下：N11=25，N12=28，N13=27，N21=19，N22=30，N23=41，N31=26，N32=22，N33=22。其中，Nij表示路線j所分配加工任務i的數量。假如某一時刻有一新的加工任務需要加工，其數量為60，該任務要分別經過車→銑→鉆等加工工序，而制造車間現有機床所遺留的信息素的量如表2所示。

表2 設備所遺留的信息素的量Tab.2 Pheromone values on each machine

表3所示的是根據新任務到達后的動態協調算法得到的動態協調結果。其中，作為加工新工件的主制造單元為機床M1，M2和M3，而作為加工新工件的次制造單元的是機床M3，M5和M9。

表3 新任務到達后的動態協調結果Tab.3 Dynamic coordination results for new tasks

在基于信息素的動態協調算法與機制的作用下，一方面所形成的虛擬的主協調單元具有加工能力較強，加工成本低等特點，因此，由此主制造單元來承擔新任務的主要加工工作以保證新任務在加工成本較少的情況下完成。另一方面，由動態協調所形成的次制造單元來輔助主制造單元，既承擔了一部分加工任務，又兼顧了機床的負荷率，實現了制造系統中各機床的均衡化。

4 結 語

受螞蟻群體覓食行為研究成果的啟發，本文提出了基于信息素的制造系統靜態和動態協調算法。在該算法中，利用信息素量的大小來反映機床對加工任務的吸引力，通過獎懲機制，使其表征加工路線(資源)的優劣。實例結果表明，通過該算法既實現了加工成本的相對較優化，又實現了制造系統中各設備的均衡利用，并對制造系統內外部環境變化具有良好的自適應性，為解決實際生產任務分配問題提供了一種實際可行的新思路。

/

[1] CAMAZINE S, DENEUBOURG J L, FRANKS N R, et al. Self-organization in Biological Systems [M]. Princeton: Princeton University Press, 2001.

[3] 李 言,劉 永,李淑娟,等.面向多訂單的JSP建模及其蟻群算法實現[J].中國機械工程,2009,20(18): 2198-2202. LI Yan, LIU Yong, LI Shujuan, et al. Modeling and ant colony algorithm implementation of multi-order oriented job-shop scheduling problem [J]. China Mechanical Engineering, 2009,20(18): 2198-2202.

[3] GAO Qinglu, LUO Xin, YANG Shuzi. Stigmergic cooperation mechanism for shop floor control system[J]. International Journal of Advanced Manufacturing Technology, 2005, 25:743-753.

[4] 董 蓉,何衛平.求解FJSP的混合遺傳-蟻群算法[J].計算機集成制造系統,2012,18(11):2492-2501. DONG Rong, HE Weiping. Hybrid genetic algorithm-ant colony optimization for FJSP solution [J]. Computer Integrated Manufacturing System, 2012，18(11)：2492-2501.

[5] 宋代立,張 潔.蟻群算法求解混合流水車間分批調度問題[J]. 計算機集成制造系統,2013,19(7): 1640-1647. SONG Daili, ZHANG Jie. Batch scheduling problem of hybrid flow shop based on ant colony algorithm [J]. Computer Integrated Manufacturing System, 2013, 19(7):1640-1647.

[6] 王靈霞,張遠平,吳佩莉.蟻群算法求解分布式系統任務分配問題[J].計算機工程與設計,2008, 29(6):1472-1474. WANG Lingxia, ZHANG Yuanping, WU Peili. Ant colony algorithm for task allocation problem in distributed system [J].Computer Engineering and Design, 2008, 29(6):1472-1474.

[7] 張春艷，劉清林，孟 珂. 基于蟻群優化算法的云計算任務分配[J]. 計算機應用，2012，32(5) ：1418-1420. ZHANG Chunyan，LIU Qinglin，MENG Ke. Task allocation based on ant colony optimization in cloud computing [J].Journal of Computer Applications, 2012, 32(5):1418 -1420.

[8] KRIEGER M J B, BILLETER J B, KELLER L. Ant-like task allocation and recruitment in cooperative robots [J]. Nature, 2000, 406:39-42.

[9] DORIGO M, BONABEAU E, THERAULAZ G. Ant algorithms and stigmergy [J]. Future Generation Computer Systems, 2000 (16): 851-871.

[10] DORIGO M, DI CARO G, GAMBARDELLA L M. Ant algorithms for discrete optimization [J]. Artificial Life, 1999,5(2): 137-172.

[11] DICARO G, DORIGO M. Ant net: Distributed stigmergetic control for communications networks [J]. A Quarterly in Artificial Intelligence, 1999,12 (3/4):2-37.

[12] 段海濱.蟻群算法原理及其應用[M].北京:科學出版社,2005. DUAN Haibin. Ant Colony Algorithm Theory and Its Applications [M]. Beijing: Science Press, 2005.

[13] 郜慶路.分布式自治制造系統中協調機制的研究與仿真[D].武漢:華中科技大學,2006. GAO Qinglu. Research and Simulation on Coordination Mechanism for Distributed Autonomous Manufacturing System [D]. Wuhan: Huazhong University of Science and Technology,2006.

[14] 袁偉東,岳亞霖,韋朋余,等.基于信息素的任務分配研究[A].中國鋼結構協會海洋鋼結構[C]. 洛陽:[s.n.],2010:423-430. YUAN Weidong, YUE Yalin, WEI Pengyu, et al. Research on pheronone-based task allocation [A]. The Conference of China Offshore Steel Structure[C]. Luoyang:[s.n.], 2010.423-430.

[15] 王 雷. 類生物化制造系統協調機制及關鍵技術研究[D].南京:南京航空航天大學,2010. WANG Lei. Research on Coordination Mechanism and Key Technique of Bio-inspired Manufacturing System[D].Nanjing: Nanjing University of Aeronautics and Astronautics, 2010.

Research on pheromone-based dynamic coordination for manufacturing system

WANG Lei1,2, LI Zhen1, LIU Zhihu1,2, YUAN Weidong3

(1.Anhui Key Laboratory of Advanced Numerical Control and Servo Technology, Anhui Polytechnic University, Wuhu Anhui 241000, China; 2.School of Mechanical and Automotive Engineering, Anhui Polytechnic University, Wuhu Anhui 241000, China; 3. China Ship Scientific Research Center, Wuxi Jiangsu 214082, China)

Inspired by the similarity between ant foraging behavior model and task allocation production process selection in manufacturing system, a pheromone-based coordination mechanism for task allocation is proposed. The pheromone-based static and dynamic coordination algorithms for production process selection in manufacturing system are given. The simulation results demonstrate that relatively lower processing costs as well as the balanced utilization of machines can be achieved by using the proposed algorithm, which has high adaptability to the disturbance from inside or outside of the manufacturing system. It provides a new feasible idea for dealing with an actual allocation problem of production tasks.

pheromone; task allocation; coordination mechanism; dynamic coordination

2014-04-14；

2014-05-20；責任編輯：張 軍

國家自然科學基金(51305001，51175262)；安徽省自然科學基金(1208085QE94, 1308085ME78)

王 雷(1982-)，男，安徽亳州人，副教授，博士，碩士生導師，主要從事智能制造系統調度控制、優化與仿真方面的研究。

E-mail：wangdalei2000@126.com

1008-1542(2014)04-0318-06

10.7535/hbkd.2014yx04002

TH166

A

王 雷，李 震，劉志虎，等.基于信息素的制造系統動態協調研究[J].河北科技大學學報,2014,35(4):318-323.

WANG Lei,LI Zhen,LIU Zhihu,et al.Research on pheromone-based dynamic coordination for manufacturing system[J].Journal of Hebei University of Science and Technology,2014,35(4):318-323.