面向作业车间重调度的改进合同网机制研究

车间初始生产调度方案实际执行时，会遇到各种各样的扰动，这些扰动会带来重调度的需求，并且这些扰动对重调度方法的实时l生、动态性及其耦合能力都有很高要求。基于多Agent的调度技术采用协商机制解决调度决策中的各类冲突，能够准确地反映系统的动态重调度过程，降低问题求解的复杂性，对动态的现实环境具有良好的灵活性和适应性。

现有的协商机制中基于合同网(CNP)的协商机制最为常用，-般认为，合同网协商机制具有较好的开放性以及动态分配和自然平衡能力。但是，传统的合同网协商机制仅仅规定单-的工作过程，本身没有优化能力和动态学习能力，因此具有 自学习能力的合同网协商机制成为了该领域研究的热点。Csai等n 以提高Agent的学习能力为目的，提出了基于时间差分学习算法 TD(A)，从而在协商过程中获得更好的投标者。Wang和Usher 为解决动态单机调度问题中调收稿 日期：2012-127基金项目：浙江省 自然科学基金资助项 目(Y1111118)；浙江省重大科技专项与优先主题资助项 目(2009C11164)作者简介：丁彬楚(1988-)，男，浙江宁波人，主要从事制造执行系统、生产计划与调度方面的研究.E-I'lail：bendbc###163-c0m机 电 工 程 第30卷度规则动态优化选择的问题，集成了强化学习中的Q-学习和CNP机制。王世进等 在此基础上，深入探讨了集成Q-学习和CNP机制的分布式柔性作业车间环境下作业动态分配优化问题，给出了具有针对性的集成机制的策略决策过程和学习过程。Q学习能够使Agent从给定的调度规则中选择出较好的调度规则，但是当这些启发式规则在学习中得不到最优解时，不能及时得到修正，并且Q学习本身无规划能力，不能满足重调度需求。张化祥等 通过考虑个体多步进化效果优化变异策略的选择，提出了-种基于Q学习的适应性进化规划算法(QEP)，用变异策略代替了启发式规则，提供了更多的交互机会，使Q学习更具有广泛性。

在以上Q学习、QEP等算法的研究基础上，本研究将其应用于动态重调度问题的研究，并引入滚动窗口技术改进QEP算法，提出集成QEP和CNP的协商机制，以实现柔性作业车间动态重调度过程。

1 重调度假设及目标本研究中的动态重调度针对的对象为柔性作业车间，给出假设条件如下：(1)各设备同-时刻只能加工-个工件；(2)工件在设备上的加工时间已知；(3)正在加工的工件不进行重调度；(4)调度过程中除设备以外的其他资源充足，无需调度。

重调度的目标描述如下：首先，仍应尽量保证原调度方案的优化目标，即最大完成时间最小；其次，在实际的生产过程中，调度系统总体上是按照初始调度方案准备调度所需加工工具和材料，当调度方案改变时，势必会造成这些工具和材料的运输和浪费 ，所以重调度产生的调度方案应尽量减少与当前调度方案的差异，即最携与重调度前调度方案的背离。

对于多目标的求解方式主要有 3种：决策先于优化、决策与优化交替以及优化先于决策 ]。本研究采用传统的决策先于优化的方式，给出重调度目标函数数学表达式如下：Fmin(u1 t2厂2)，maxF10

2 改进QEP重调度算法本研究给出的调度目标重点在于吸收和修复动态事件对调度的影响，因此笔者引入滚动窗口重调度技术。滚动窗 口技术的应用可以减少动态重调度涉及的对象，缩小问题求解的规模 ，并将该技术集成到QEP算法中，使算法在求解重调度问题时具有合理的规划性，避免盲目进化，提高进化效率。

输出最优策略和初始化进化个体和滚 个体动窗口，设定进化步长为I 否/ 滚动窗口 /- 、 否为空7// 选择滚动窗口中的第- -< 个工单，对应工序采用代，给每-个后代个体分配-个临时滚动窗口 采用局部更新方法并且进行初始化 更新滚动窗口选择使 大化的对每个后代个体进行Q 变异策略作为个体的学习，计算每-个变异 .. 变异策略，选择其对策略对应的Q值 应的后代替代父代，忽略其他后代图 1 改进QEP算法流程2.1 滚动窗口初始化及更新设计当生产过程中有扰动事件发生时，某工件当前加工工序受到影响，并且由于该工件受到工序约束和设备约束，影响会进-步扩散，即重调度的扩散效应 。

研究者通常采用二维分支树(即工件分支和设备分支)来描述该扩散过程。滚动窗口初始化和更新建立在这种扩散过程的基础上。

针对3种常见扰动事件，滚动窗口初始化方法为：(1)加工延迟。初始滚动窗口为延迟工件两分支上的工单；(2)设备故障。初始滚动窗口为故障设备故障时间内待加工工单，如果设备故障时间未知，则表示为故障设备上所有工单；(3)故障恢复。初始滚动窗口为所有可在该设备上加工的工单，已完工和正在加工的工单除外，同时滚动窗口内工单按照开工时间的先后顺序进行排列。

本研究设计了局部和全局两种滚动窗口更新方法。局部更新是针对某-工单进行更新、整合，步骤如下：第2期 丁彬楚，等：面向作业车间重调度的改进合同网机制研究(1)以更新的工单为根节点，将工件分支和设备分支上的工单加入滚动窗口并删除更新的工单；(2)去除滚动窗口中重复的、无延迟发生的工单；(3)按照工单开工时间的先后顺序进行排序。

全局更新是针对滚动窗口内所有工单进行更新、整合，步骤如下：(1)根据当前滚动窗口，将各工单工件分支和设备分支上的工单作为当前滚动窗口，替换原滚动窗口，在二维分支树上表示为下-层的工单集；步骤(2)、(3)同局部更新。

2.2 进化分析Q学习通过选择最大化Agent带折扣累积收益的行动，可以学习到Agent的最优行动集▲化过程中，研究者若把个体变异策略看成行动，则个体选择最优变异策略就转化为Agent选择最优行动，在选择最优行动时考虑行动的立即及多步滞后收益，即计算折扣累计收益。

本研究假设个体进化步长为 m(m>1)，即考虑m-1步滞后收益，个体开始选择变异策略为口，可以计算个体采用行动口时的收益为：Q r(a)yQ(a。 )3/ Q(a - ) (2)式中：r###)-个体采用变异策略口的立即收益，此时个体进化了-次。

新生成的个体采用。∞生成新个体，此时收益记为Q(a∞)，依次类推，m-1次进化后，新生成的个体采用口m 生成新个体，此时收益记为Q(a )。式(2)为个体采用口，0∞，，(m-1)变异策略集的累计收益。定义个体立即收益r(口) ㈦。其中： ###)-父代个体对应的适应度值， ㈦-采用变异策略口后生成的子代个体对应的适应度值。适应度函数计算公式如下：(3)其中，函数 ， 已在公式(1)中给出。本研究将立即收益代人式(3)，得到Q值的计算公式为：Q( ( -(1- )fo( -y(1- )-- ，.、y - ) 42.3 改进Q学习过程设计在Q学习过程中，为保证滞后收益对Q(0)的有效性，本研究针对每个个体分配了-个临时滚动窗口。

Stepl：获取临时滚动窗口，设置进化代数t2；如果临时滚动窗口为空，转人step5；Step2：遍历临时滚动窗VI中每-个工单，采用获取Q学习个体临时滚动窗口，设定t-2L 去 是： //l否T。

依次选择临时滚动窗口中的工单，对应工序采用变异策略产生 计算个体的Q值新的后代，Bcdt2Ⅱ脚n分布选择其中-个后代替代父代采用全局更新方法更新临时滚动窗口，f ～- .- 图2 Q学习流程图Boltzmann选择每-个工单对应工序的变异策略；Bohzmann分布计算变异策略被保留下来的概率为：r(a。)p(a ) ， (1-OlX t) (5)e式中： -工序变异产生的后代个数； -调节系数，∈(0，1)； -初始温度。

在Q学习的初始阶段，温度参数 设置较高，系统探索未尝试的动作(选择非最优变异策略)，以获得更多回报的机会；在Q学习的后期，笔者设置较低的温度参数，使系统倾向于利用当前最优的变异策略。

Step3：采用全局更新的方法更新临时滚动窗口，同时设置进化代数加1；Step4：判断 t是否大于 m ，或者临时滚动窗口为空；满足条件则转step5；不满足则转step2；Step5：计算个体的Q值，Q学习结束。

以下给出m2时的Q学习过程示意图：t2 tl t2/ (5图3 Q学习过程示意图2.4 变异策略基于文献[1O]的研究，本研究给出以下变异策机 电 工 程 第30卷略 ：(1)工序所用设备不变，加工顺序不变，只是调整各个工序的开始时间和结束时间，记为设备不变，顺序不变”；(2)工序所用设备不变，但在设备内的加工顺序可以调整，记为设备不变，顺序可变”；(3)工序使用设备发生变化，插入到并行设备加工列表中，记为设备可变，顺序可变”。

3 集成QEP的改进合同网协商机制扰动事件发生时，集成QEP的合同网机制协商过程如图4所示。其基本交互过程发生在工序Agent(PA)和设备Agent(MA)之间。

图4 QEP-CNP协商流程图基本流程描述如下：Stepl：初始化滚动窗口；Step2：获取滚动窗 口中的第-个工单，生成相应的工序Agent(PA)，解除原先合约，并获取调度需要的相关信息，包括加工时间、可加工设备、设备上的工单列表等；Step3：PA向能够加工它的设备发送招标请求；Step4：设备Agent(MA)作为投标方进行Q学习，根据工件平均背离、总完成时间和设备负载等生成多份标书，向PA发送应标信息；Step5：PA评价各MA发回的投标书，选择中标的MA和最优变异(最大Q值)，更新调度方案；两份标书评价值相等时，根据设备负载，选择负载小的MA和最优变异策略；Step6：采用局部更新方法更新滚动窗口；Step7：判断滚动窗口是否为空；否，转Step2；是，协商结束，输出调度方案。

4 仿真实验本研究将文献[11]给出的10×10标准算例调度最优解作为初始调度解，其甘特图如图5所示。笔者针对表 1给出的动态事件进行重调度仿真。

骠姐H暑031 O22 O23O51 l o52 062 l 063032 lO41 0102l 0103 033 l 092091 O61 l 073 093 lO81 l053 043 I O130101 O42 072 lol2 1 082 1 083Ol1 0l2l O71t/s图5 10×10甘特图(最短加工时间：t7 s)表1 动态事件表事件时间/s 事件内容123设备2发生故障，恢复时间未知工单0102加工延迟，延迟O.5 s设备2故障恢复动态重调度算法选择参数如下：完成时间权重为0.8，工时偏差权重为0.2，进化步长为2，变温调节系数为0.8，初始温度为10。由于重调度协商过程中工件和设备目标明确，容易达成-致，直接受影响的工件重调度所需要的时间可以忽略。

本研究通过仿真得到3个时刻重调度后的甘特图如图6所示。

本研究将改进的合同网协商机制与基本合同网协商机制相比，得到的仿真结果如表2所示。通过对比可以看出，改进的合同网协商机制具有较好的全局优I化I生能。

表2 仿真结果表5 结束语本研究针对面向作业车间重调度问题的改进合