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

设计出来的一种群体智能优化算法，该算法在作业车间调度问题[3-5]、任务分配问题[6-7]、机器人合作问题[8]等领域得到了广泛的研究与应用。笔者受蚂蚁觅食行为模型与零件的生产加工工艺选择的相似性的启发，提出了基于信息素的任务分配协调机制，以信息素为介质，给出了制造系统生产加工工艺选择的静态和动态协调算法。

1 基于信息素的协调机制

基于信息素的协调机制源于蚂蚁的觅食活动，尽管单个蚂蚁的行为比较简单，但整个蚂蚁群体表现为高度机构化的社会组织，在许多情况下能够完成远远超过单个蚂蚁能力的复杂的任务[9]。这种能力来源于蚂蚁群体中的依靠信息素作为通信物质的个体协作行为。蚂蚁在觅食过程中能过通过相互协作找到食物源与巢穴之间的最短路径[10-12]。

如图1所示，蚂蚁群体不但能够协调完成复杂的任务，而且还能够自适应外部环境的变化，如图1a）所示，无论路径长短，各只蚂蚁一开始的分布是均匀的，蚂蚁总是先按照相同的概率选择可行路径。蚂蚁在途经的过程中，能够在其经过的路径上留下信息素，而且能够感知这种化学物质的存在及其强弱，并以此指导自己的行为，蚂蚁更倾向于向信息素量大的路径上移动。相等时间内较短路径上的信息素的遗留量就比较多，则选择较短路径上的蚂蚁也随之增多，如图1c）所示。不难发现，由于大量蚂蚁组成的蚁群集体行为表现出了一种信息正反馈现象，即某一路径上走过的蚂蚁越多，则随后的蚂蚁选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息交流机制来进行觅食，并最终沿着最短路径进行，如图1d）所示。

通过对蚂蚁觅食行为的深入研究表明，可以用式（1）表示蚂蚁选择路径的行为模型[13]：

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

2.1 基于信息素的静态协调分配算法

对某一任务的加工可以有多条加工工艺路线完成，而由于设备性能的不同导致任何一条生产加工工艺路线所需要的总生产成本也是有所不同的，所以，可以理解每条加工工艺路线就分别拥有不同量值的信息素，与这些加工工艺路线对每一种加工任务的吸引强度分别相对应。如果在某条工艺路线上不具备加工某类生产任务的话，则设置该条工艺路线上的信息素值为0，以防止该条工艺路线再吸引此类加工任务而使完工时间等性能指标受到一定程度的影响。

然而，由于只能有某一条或某几条加工工艺路线可以完成即有的任务的加工。所以，为了模仿蚂蚁觅食的探路过程，并与加工过程中的真实情况相吻合，首先设置所有能够加工某类生产任务的工艺路线上的信息素初始值c0，即

当有生产任务需要选择工艺路线进行加工时，该任务首先感知每条加工工艺路线对此任务下一个需要加工的工件信息素量值，按每条加工工艺路线所需要的总生产成本大小所对应的信息素值来对加工工艺路线进行选择。h为路径选择非线性因子，在此设置为1，则对任何一个加工任务，加工工艺路线j被加工工件i选择的概率p（i）大小根据式（3）计算得：

当某条加工工艺路线被某一生产任务的一个工件选择后，要对该条加工工艺路线进行一定的奖励，该路线对对应任务的信息素的吸引力用信息素奖励函数A（c）来增强。与此同时，由于加工工艺路线被生产任务的选择原因，在被选择的加工工艺路线中所涉及到机床的可利用有效加工时间也会越来越少，为此减少该工艺路线

式中：某一条加工工艺路线加工某类工件所需要的总加工成本用c表示；增加的信息素量值用A（c）表示，它是总加工成本的减函数。这样才能保证较优的加工工艺路线上的信息素得到加强的机会增多，被选择的概率加大。

当某条加工工艺路线中所拥有的某设备的可利用时间小于该设备能够加工的某种工件的对应某一加工工序所需工时的时候，自动置该条加工工艺路线的信息素为零。另外，当某个设备的可利用时间为零时，置该资源涉及到的所有加工工艺路线的信息素为零[14-15]。图2是基于信息素的静态协调分配算法流程图。[WT]

然而，在实际生产中存在大量随机事件，如新任务插入、订单的取消、交货期变动、机器故障等。为此，针对这些随机事件需要动态的协调来合理的进行任务的分配。由于篇幅问题，本文主要从新任务加入这种情况来具体研究基于信息素的动态协调算法。有关设备故障、交货期变更等动态协调问题将在后续的工作中展开研究。

2.2 新任务到达时的动态协调

新任务所涉及的范围较大，可以指种类不同的加工工件的集合，这里为了简单描述基于信息素的任务分配的动态协调过程，假设新任务中仅包含一种类型工件的加工任务（多种类型的任务也可依此类推）。这里只有新任务的加工工艺特征信息（如j1→j2→…→ji（ji代表刨、磨、车、铣等加工工艺特征信息））是已知的。图3是新任务到达时的[WT]动态协调过程。

具体动态协调算法步骤如下。

1） 首先为新任务每道加工工序选择具有匹配工艺能力的机床。因为在一个制造单元或者车间内部具有某种加工工艺能力的机床往往不止一台，也就是在机床设备之间具有可选择性或者可替代性，所以新任务的每一道加工工序通常可对应多个机床可供选择。

2） 将之前生产任务选择工艺路线时在每台可替代机床上遗留的信息素量各自相加，可由式（5）计算所得。

由式（5）所计算出的信息素值大小的差异正体现各个加工机床在加工某种加工工艺特征时所表现出来的能力的强弱。在此条件下运行基于信息素的工艺路径选择算法，将新任务中每个工件的第j道加工工序特征分配给步骤1）中所涉及到的机床，选中每个设备的概率可由式（6）计算所得。

（6）

3） 更新机床所拥有的信息素的值。

[WTBX] 4） 为新任务中所有工件的第（j+1）道加工工序特征选择机床，直至新任务的所有加工工艺特征都选择所对应能力的机床为止。

5） 对新任务的每道加工工艺特征在各可用机床上的加工数量进行统计，将承担工件任务较多的机床自组织成一个主虚拟制造单元，将承担工件任务数量较少的机床自组织成多个或一个副虚拟制造单元。

6） 主、副虚拟制造单元在完成新任务加工后自动解散并恢复到之前所属的单元状态。

3 应用算例

可以使用的制造[WT]资源集合包括M1，M2，M3，M4，M5，M6，M7，M8和M9等9台加工机床。表1所示的是每一加工任务的加工工艺流程。假设所有任务的交货时间为D=1 500（时间单位）。

在基于信息素的动态协调算法与机制的作用下，一方面所形成的虚拟的主协调单元具有加工能力较强，加工成本低等特点，因此，由此主制造单元来承担新任务的主要加工工作以保证新任务在加工成本较少的情况下完成。另一方面，由动态协调所形成的次制造单元来辅助主制造单元，既承担了一部分加工任务，又兼顾了机床的负荷率，实现了制造系统中各机床的均衡化。

4 结 语

受蚂蚁群体觅食行为研究成果的启发，本文提出了基于信息素的制造系统静态和动态协调算法。在该算法中，利用信息素量的大小来反映机床对加工任务的吸引力，通过奖惩机制，使其表征加工路线（资源）的优劣。实例结果表明，通过该算法既实现了加工成本的相对较优化，又实现了制造系统中各设备的均衡利用，并对制造系统内外部环境变化具有良好的自适应性，为解决实际生产任务分配问题提供了一种实际可行的新思路。

参考文献/References：

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