基于混流生产的优化调度及实现

刘建国　王廷梅　李爱菊

摘要：混流生产在产品生产过程中有多个加工和装配操作，优化过程是如何在多个加工设备和装配设备上进行调度，使产品加工时间最短。本文建立了混流生产合作博弈调度优化方法，通过对问题的分解和agent间的合作博弈调度，采用实验对算法进行验证，得到了满意的效果。

关键词：agent；混合流水生产；调度；合作博弈

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）13-0221-02

1 研究背景

混合流水生产包括零部件加工和产品装配过程。一件产品通常都由多个零部件装配完成，而零件可以在多套生产设备上加工完成，装配过程也是在多套装配设备上完成。对于拥有多个无差别的生产和装配设备的工厂，如何缩短产品的生产时间一直是重要的研究方向。

2 问题原型

如图1所示的产品及结构，需要经过多个加工与装配机器进行生产，研究的目标是怎样把零件分配到不同机器上加工和装配，可以边加工边装配，达到产品的makespan时间最短。

3 复杂结构的分解和简单结构图的调度

对于结构复杂的产品，都可对其结构图进行分解，获得多个简单图。简单图满足每个度大于1的节点不超过一个度大于1的子节点，也就是每层不超过一个装配节点。对图1中A3节点分解，得到根节点为A1，A2和p5的三个简单图。如图3所示。

每个简单图的调度都使用一个agent代表。对简单图可以通过合理的调度算法得到最优结果。对于一个制造系统，假设有m台加工机器和q台装配机器，可以采用底层优先算法，获得makespan最小的最优结果。算法顺序如下：

1）加工过程工序安排：按照树的层数从底层开始，由下往上，同一层的加工工序按照时间由大到小顺序优先安排到空闲的加工机器上；

2）装配过程工序安排：由于简单图每层最多只有一个装配工序，在其子节点工序都完成情况下，按照树的层数从底层开始，由下往上的顺序安排到空闲的装配机器上。

4 多agent调度

每个简单图的调度都是用一个agent来代理，每个agent的独立调度通过底层优先方法得到，但全部agent受到产品整体逻辑关系的制约，非简单线性关系，因此多个agent之间进行的整体调度是问题关键。

考虑到各agent之间的关系，首先是竞争的，但同时也必须进行合作。因为资源有限，各agent都以自己代理的任务尽快尽早结束为目标；同时，受限于产品结构，不是所有agent都可以不受约束在任何时间点开始生产，有的必须等别的agent生产结束后才可上线生产，因此agent间也必须存在合作，各自都要服从在机器上时序的安排，最终达到目标的整体最优。

对于多agent的调度是研究的重点，本文采用多agent合作博弈的方法，具体算法如下：

1） 将所有agent分成三个集合：A是已参加博弈集，B是可选集，C是不可选集。可选集表示其前期工序已完成；不可选集表示受产品结构制约，其前期工序未完成，暂时不可进行调度。

2） 在调度过程中，依次增加进入A集合的agent个数，每次迭代过程只允许增加一个，直至全部agent都进入A集中。在最初，A是空集， B是能够直接加工无其他前序工序约束的所有agent集，调度开始后，依次对B中的每一个agent单独进行调度，选择B中makespan所需最长的那个agent加人A集中，然后更新集合A，B和C。以后每次迭代过程中，都是从B集中挑选一个agent加入A集。方法是将B集中的每个agent与A集中的agent分别合在一起做调度，在A中已存在的顺序不变情况下，将B中agent安排在A后面再调度即可，联合调度所需时间最长的agent的进入A。

3） 一旦B中有agent进入A，就需对集合A，B，C更新。

4） 在集合A内部的博弈也是个反复的过程，经过多次迭代优化，如果结果稳定就继续从B集中挑选一个合适的agent加入A集。一旦B集为空，则整个调度过程结束。

5 实例分析

对如图4产品结构先进行分解，得到多个agent，然后再进行优化调度。设定生产设备和装配机器都是2台，得到如图5调度结果，可以得到问题的最优调度，且机器的工作负载均衡。利用本方法对多种产品结构进行调度，都能够获得满意结果，对于产品结构更复杂，机器数设置更多的情况，可以判断出至少得到次优结果。

6 结论

在混合流水生产过程中，要经过多道加工工序和装配工序的复杂产品的生产，其调度具有多目标特征，本文采用合作博弈的方法基本可以较好的解决makespan最优的调度问题，实验结果也验证了本方法的有效性。同时，也可以采用本文提出的调度方法来解决类似于机器负荷均衡、装配件消耗均衡等其他问题。

参考文献

[1]徐俊刚，戴国忠，王宏安.生产调度理论和方法研究综述[J].计算机研究与发展.2004，41（2）：257-267.

[2]唐立新，吴亚萍.混合流水车间调度的遗传下降算法[J].自动化学报.2002，28（4）：637-641.

[3]任明，王成道.基于联邦结构的多agent协作[J].华东理工大学学报.2004，30（3）：311-314.

[4] 罗伯特·吉本斯. 博弈论基础[M]. 中国社会科学出版社.1999.3