基于改进合同网协议的作业车间调度方法研究

朱云飞，楼佩煌，钱晓明，何　珍

(南京航空航天大学机电学院，江苏 南京　210016)

车间调度是制造系统中一个重要的环节，合理科学的调度方案可以有效地提高产品的生产效率。传统的调度方案多采用集中式控制手段，由系统中的主控制器对加工任务进行分配。从理论上说，依靠合理的算法与规则，集中式控制方式可以得到最佳的控制效果，使系统中各个设备的性能和效率发挥到最优。但是集中式控制方式要获得最佳的控制效果有两个必不可少的前提：一是控制系统对全局知识的及时获取；二是主控设备拥有较高的计算能力。在实际生产中，随着生产规模的扩大，系统中的信息量呈爆炸式增长，主控设备通常难以实时获取系统中各个部分的信息，从而不能及时作出决策。同时海量的信息也会给主控设备带来庞大的计算负担。

随着物联网技术的发展，制造业也开始逐步融入物联网技术[1]。在物联制造环境下，制造系统中各设备间一般是采用分布式控制方案，即由相关设备集合相互协商来完成相应加工任务。而在分布式协商算法中，合同网协议(contract net protocol，CNP)是使用较多的一种方案。

基于CNP的MAS系统在生产调度中有着大量应用，例如徐青等[2]利用合同网的协商策略解决锻造车间工艺规划和车间调度问题；ALEKSIS等[3]利用合同网协议解决多机器人任务分配问题；宋娟[4]提出了一种基于合同网的多Agent车间调度系统；HSIEH等[5]研究了分布式柔性系统中任务分配问题。

但是在实际的应用研究中，传统合同网协议算法存在很多缺点，例如：其一般采用广播方式对任务进行招标，大量能力不足的Agent一样会收到招标信息，这样造成了大量的通信消耗；传统合同网中接受任务的Agent完成任务后没有反馈，任务发布者无法知道此次任务分配到底是好是坏，即使任务失败下次任务分配时依然会对其招标，系统存在潜在隐患；传统合同网分配方式约束比较单一，不能综合考虑车间生产的各种约束；传统合同网协议一般在当前任务完成后才能进行下一次任务的招标，这样在任务分配时，设备将处于空闲等待状态，从而降低生产效率。

针对传统合同网协议的不足，研究人员纷纷提出了各种改进方案，例如张海俊等[6]提出了引入信任度的动态合同网协议；万武南等[7]提出了一种基于任务熟人集的合同网模型；ZHAO等[8]利用改进的合同网协议解决制造车间的动态重调度问题；WANG等[9]利用距离矩阵改进合同网来优化作业分配过程；杨件等[10]引入投标阈值和可用度来限制不必要的招标活动；HUANG等[11]利用容量因子和协作层次来改进合同网协议并用其优化水库防洪的调度问题；李明等[12]利用改进的合同网来解决AGV任务分配问题。上述改进方案虽然在一定程度上解决了传统合同网协议的缺陷，但是在用于作业车间调度问题上时依然存在不足。例如，文献[6]的信任度机制面临着信任度无限增加的问题，同时第一次分配对于系统后续分配的影响较大；文献[12]虽然提出了能力值模型来解决AGV由于正在执行任务而盲目拒标造成的信任度降低的问题，但是没有解决信任度无限增长的问题；文献[13]虽然引入了信任度随时间降低的函数，但是函数的各参数确定比较困难。上述改进方案在分配任务时采用的仍然是一种贪婪策略，并没有基于以往的分配经验来决策当前分配过程。

考虑到作业车间调度环境复杂、车间各个设备对同一零件的加工能力的差别、各个工序之间加工质量的相互影响，本文引入强化学习机制，令设备Agent主动学习，逐渐使系统趋向于最优分配，同时引入设备的积极性来防止设备负载不均匀。

1　问题描述

柔性作业车间调度问题(flexible job-shop scheduling problem，FJSP)是指给定N个零件在M台机器上加工，每个零件由若干工序组成，每个零件的每道工序由若干机器加工。调度目标是使系统的某些指标达到最优。为了简化问题，一般作如下约束：

1)加工工序一旦开始除非加工站出现故障否则不能停下。

2)同一零件各个加工工序必须顺序进行，即前一工序加工完才能进行下一工序，不同零件之间没有加工顺序要求。

3)每台机器同一时刻只能加工一个零件的一道工序。

4)每个工件的各道工序是已知的，每台机器能否加工某一零件的某道工序也是已知的。

本文以图1中车间布局为研究对象。

在某个生产周期内，对作业车间调度问题定义相关数学符号，见表1。

图1　作业车间布局

表1　建模数学符号及含义

对于某工作站Mk(k=1,2,3,…,m)记矩阵

Sk(Pi)=[x1x2x3…xNi]

(1)

式中：xj=1表示零件Pi的第TPj道工序可以由该设备加工，xj=0表示零件Pi的第TPj道工序不能由该设备加工，j=1,2,3,…,Ni。

(2)

(3)

式中：n为该生产周期内总加工任务数；m为设备总数。

本文以最小化设备平均空载时间和平均空载时间方差作为设备负载均衡的指标，所以优化函数为：

(4)

f2=minσ2

(5)

考虑到设备的加工能力将随时间而变化，本文将加工时间作为系统动态学习的一个因素。

2　改进的合同网确认协议

2.1　任务缓冲池机制

考虑到传统合同网协议在分配任务时，设备必须执行完当前任务后才能参与投标，这样会导致系统产生较多无意义的通信，同时系统会由于正在执行任务的设备不能参与投标而无法获得较好的加工方案，故本文为工作站引入缓冲区。设计工作站模型如图2所示。

图2　工作站模型

工作站有如下特点：工作站由输入缓冲区、加工中心和输出缓冲区构成，其中输入缓冲区和输出缓冲区可存放零件为3，加工中心同一时间只能加工一个零件的一道工序；加工中心每次从输入缓冲区中选择某一零件进行加工，车间搬运设备则每次从输出缓冲区中选择某一零件进行搬运；只要输入缓冲区未满，工作站就可参与投标或者接受任务的直接授权，所以工作站一般将会有0～3个待加工任务。

2.2　分配收益与加工能力值反馈

在引言中已经讨论过传统合同网协议或者基于信任度等一些改进的合同网协议在作业车间调度问题上缺少对作业分配情况好坏的反馈。本文考虑引入增强学习(reinforcement learning，RL)模型。目前增强学习算法很多，考虑到作业车间任务分配具有离散性质，故本文采用离散处理性能较好的Q学习方式[14]。

为了在全局上获得较好的分配方案，提高工作站任务分配的效益，为工作站引入分配收益和加工能力值两个指标。基于上文的车间模型，在柔性作业车间任务分配中，任务的各工序依次由完成上一道工序的设备将当前工序加工任务分配给下一个设备。为了在分配任务时，可以直接在有能力加工该零件下一工序的设备集中进行任务分配，假设对于任一零件Pi，若设备Mk分别可加工其第TPJi(Ji对应零件Pi的某道工序)道工序，则为设备Mk定义p×m加工能力矩阵Rk，其中p为零件种类，m为设备个数。

(6)

式中：rij=1表示设备Mj具备加工零件Pi下一道工序的能力，rij=0表示设备Mj不具备加工零件Pi下一道工序的能力，i=1,2,3,…,p,j=1,2,3,…,m。

从上文Sk(Pi)的定义可知

(7)

同时为设备Mk定义p×m分配收益矩阵Gk:

(8)

式中：gij表示工作站Mk认为将零件Pi下一道工序分配给工作站Mj将获得的分配收益，i=1,2,3,…，p,j=1,2,3,…,m。

Gk初始状态为0，下面介绍其更新方式。

若某时间段任务Tj连续三道工序TPh-1，TPh，TPh+1加工情况为(Tj，TPh-1，Mkh-1)，(Tj,TPh,Mkh)，(Tj,TPh+1,Mkh+1),从上文模型可知加工任务Tj对应零件种类为Phj。

则在加工完第h道工序后，定义

C(Tj,TPh,Mkh)=(1-ω)×(s/PT(Tj,TPh,Mkh))+ω×Q(Tj,TPh,Mkh)

(9)

作为本次加工情况反馈。式中：Q(Tj,TPh,Mkh)为加工质量信息；s为加工时间换算到加工质量的系数；ω为加工时间和加工质量选取的权值。

记Qk(Pi,TPj)(j=1,2,3,…,Ni)为工作站Mk对第i种零件Pi的第TPj道工序加工能力，同时更新

(10)

更新工作站Mkh-1的Gkh-1为

(11)

式中：∂(0<∂≤1)表示学习速率，越接近1表示收益矩阵可以更快收敛获得分配效果；α(0≤α≤1)表示收益权重，接近0表示更看重本次任务分配收益，接近1表示更看重后续整体的分配收益。

同理当第(h+1)道工序完成后得到

C(Tj,TPh+1Mkh+1)=(1-ω)×(s/PT(Tj,TPh+1Mkh+1))+ω×Q(Tj,TPh+1,Mkh+1)

(12)

更新

Qkh+1(Phj,TPh+1)=

(13)

更新工作站Mkh的Gkh为

(14)

图3为3个工作站Agent分配收益计算模型。

图3　工作站Agent收益模型

基于上述加工能力值，设集合S为该生产周期内任务序列{T1,T2,T3,…,Tn}的所有完成方案，集合T为其中一种方案。增加优化函数

(15)

分配收益模型主要为引进Q学习的强化学习机制，由于Q学习属于收敛的学习方式，所以在经过长期的学习后，工作站Agent的收益分配矩阵Gk将在一个固定值上下波动，不会像文献[6]中的信任度无限增长，也无需构思信任度降低函数，并且当工作站由于磨损或其他无法主观察觉的原因造成精度缺失、能力下降时，工作站Agent可以利用学习机制慢慢察觉其变化进而主动向系统更优的方案偏移。

2.3　基于加工能力值和积极性的投标策略

传统合同网协议中任务分配完成需要管理器和承包商通过多次的信息交互。上文所述依据分配收益矩阵分配任务是一种直接授权的任务分配方式，在任务分配时可以减少通信交互。但是直接授权方式需要系统学习足够多的样本才能获得较好的分配效果，所以本文采用ε概率分配方式，即系统在分配任务时依据合同网协议分配的概率为ε，依据分配收益矩阵分配的概率为(1-ε)。ε计算公式为：

(16)

式中：a(0≤a≤1)决定系统采用合同网分配的最低概率，Numi较大时ε近似为(1-a)，所以a越大，系统采用合同网分配的最低概率越低；Numi为该工作站对第i种零件分配任务的总次数；b为常数，其越大则ε减小的速率越低,表示系统希望获得更多的学习样本。

采用合同网协议进行任务分配时，工作站以式(10)计算得到的加工信息反馈和分配收益矩阵Gk综合进行投标，以上文(Tj,TPh-1,Mkh-1)，(Tj,TPh,Mkh)，(Tj,TPh+1,Mkh+1)连续3道工序为例，假设当前状态为第二道工序已完成，正在进行第三道工序的招标，工作站Mkh根据矩阵Rkh找出满足加工下一工序的设备集，当工作站Mkh+1接到招标请求时，其以式(17)参与投标竞争。

W=Qkh+1(Phj,TPh+1)+α×

(17)

为了避免某些工作站接收任务较多导致工作站加工负荷较大，以输入缓冲区待加工零件作为工作站判断是否投标的依据。例如，若输入缓冲区代加工零件为0，则工作站100%参与投标，若输入缓冲区待加工零件为1，则工作站75%概率参与投标，依次类推。

2.4　投标标书格式与任务分配流程

标书数据区统一格式为

Task_Announcement={TaskID, Initiator,Addresses, TaskDescription}

其中：TaskID为任务号；Initiator为招标发起者；Addresses为招标发起者地址；TaskDescription为任务描述，包括零件类型、当前工序等。

工作站任务分配流程为：

步骤1，初始化各工作站矩阵Rk和Gk。

步骤2，各批次零件的第一道工序由系统中的中央调度器分配，其余工序则由加工该零件上一道工序的工作站进行分配，在分配任务时由ε决定依据收益矩阵进行分配或者依据合同网协议进行分配。

步骤3，各工作站接收任务后，当其加工完零件后，若加工任务成功完成，计算本次加工能力值C(Tj,TPh,Mkh)，更新自身数据库，同时计算本次分配收益因子并将其传回分配该零件加工任务的工作站，该零件上一道工序加工站根据传回的分配收益因子更新自身分配收益矩阵Gk；若零件加工失败，则根据失败原因作相应更新。

步骤4，若零件工序未完成，重复步骤2和步骤3。

图4为加工站任务分配流程图。

图4　加工站任务分配流程图

3　实验仿真

本文利用MATLAB来进行仿真，并验证算法的有效性。仿真基于如下假设：加工任务的零件类型以等概率方式随机确定，生产系统中有10种零件、20台设备；加工任务以恒定时间到达。式(11)中为了获得较快的学习速度和较好的预期收益,令∂=1,α=0.8；式(9)中主要考虑时间因素,故令ω=0.2；式(16)中令a=1，b=100。

分别比较传统的CNP和本文提出的ICNP方法在f1,f2,f33个指标上的区别。每批加工任务个数分别设为100，150，200，250，300，…，2 000。图5为两种方式平均加工质量对比图。

图5　加工质量对比图

图中横线为理论最佳状态，可以看出随着零件加工次数的增多，通过ICNP方式分配任务，零件的平均加工质量总是向着理论最佳状态逼近，这是因为经过增强学习后，系统逐渐找到了该零件的最佳加工路线，但是由于在任务分配时该零件最佳加工路线的加工设备不一定总是处于空闲状态，所以ICNP方式和理论最佳方案总是有一定差距，而传统的CNP任务分配方案由于没有定义学习机制，所以其加工路线比较随机，总体比ICNP方案偏弱。图6，7为仿真后两种方式获得的平均空载时间和平均空载时间方差对比。

图6　平均空载时间对比

图7　平均空载时间方差对比

从图中可以看出，基于ICNP的分配方案总体上优于基于传统CNP的分配方案。

4　结束语

本文通过分析在分布式制造环境下集中式分配方案的不足，确立了采用合同网协议的分布式作业车间任务分配方案。在讨论了传统合同网协议在通信效率、分配可靠性等方面存在较大缺陷后，以柔性作业车间任务分配为研究对象，考虑引入增强学习、积极性等手段改进传统合同网协议。最后用仿真实验验证了本文提出的ICNP方案要稍优于传统CNP方案。

参考文献：

[1]侯瑞春,丁香乾,陶冶,等. 制造物联及相关技术架构研究[J]. 计算机集成制造系统,2014,20(1):11-20.

[2]徐青,李东波. 基于多agent的锻造生产工艺规划与车间调度集成研究[J]. 机械设计与制造工程,2013,42(10):29-32.

[3]LIEKNA Aleksis,LAVENDELIS Egons,GRABOVSKIS Arvids. Experimental analysis of contract net protocol in multi-robot task allocation[J]. Applied Computer Systems,2012,13(1):6-14.

[4]宋娟. 基于CNP的多Agent车间调度系统设计与实现[J]. 工业控制计算机,2010(6):82-84.

[5]HSIEH Fu-shiung,LIN Jim-bon. A dynamic scheme for scheduling complex tasks in manufacturing systems based on collaboration of agents[J]. Applied Intelligence,2014,41(2):366-382.

[6]张海俊, 史忠植. 动态合同网协议[J]. 计算机工程, 2004, 30(21): 44-46.

[7]万武南, 张蕾. 基于任务熟人集的合同网模型的改进[J]. 计算机应用, 2003, 23(3): 3-5.

[8]ZHAO F, WANG J, TANG J. Research on dynamic rescheduling program based on improved contract net protocol[J]. Journal of Software, 2011, 6(5): 798-805.

[9]WANG H, LUO D, ZHANG F, et al. Multi-task assignment 0-1 programming model and algorithm based on the improved contract net protocol[C]//Applied Mechanics and Materials. Shanghai:Trans Tech Publications Inc, 2014: 1376-1383.

[10] 杨件, 李文立, 洪春宇. 基于阈值和可用度的合同网协议改进方案研究[J]. 计算机集成制造系统, 2009, 15(5):1016-1022.

[11] HUANG W, ZHANG X, WEI X. An improved contract net protocol with multi-agent for reservoir flood control dispatch[J]. Journal of Water Resource and Protection,2011,3(10):735-746.

[12] 李明,刘玮,张彦铎.基于改进合同网协议的多Agent动态任务分配[J].山东大学学报(工学版),2016,46(2):51-56.

[13] 徐燕妮. 基于合同网协议的多 Agent 协作技术研究[D]. 青岛：山东科技大学, 2006.

[14] 王世进. 面向制造任务动态分配的改进合同网机制[J]. 计算机集成制造系统, 2011, 17(6): 1257-1263.