基于信息素的制造系统动态协调研究

王 雷，李 震，刘志虎，袁伟东

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