一种制造系统自适应动态调度方法

摘要

本发明公开了一种制造系统自适应动态调度方法，涉及制造系统生产调度领域。本发明针对制造系统生产环境的不确定性，构建了一个基于多Agent的动态生产调度系统。为了保证设备能够根据当前的系统状态选择合适的中标作业，提出一种基于聚类-动态搜索的改进Q学习算法,以指导不确定生产环境下动态调度策略的自适应选择。该动态调度策略采用顺序聚类降低系统状态维数，根据状态差异度和动态贪婪搜索策略进行学习。给出了算法的收敛性和复杂性分析，并通过仿真实验，验证了本发明所提出的自适应动态调度方法的有效性和适应性。

权利要求

1.一种制造系统自适应动态调度方法，其特征在于，包括以下步骤：步骤1)，将最小化提前拖期惩罚作为调度目标，建立制造系统的动态调度目标函数；

步骤2)，建立制造系统的动态调度系统模型，所述动态调度系统模型包含作业Agent、状态Agent、设备Agent和缓冲Agent；

所述作业Agent用于与人机交互接口对接，对接信息包含作业的数量、工序及加工时间；

所述状态Agent用于代理调度系统的状态；

所述设备Agent用于代理调度系统的生产设备；

所述缓冲Agent表示生产设备的缓冲区，用于代理缓冲区中的待加工工序与设备Agent进行协商；

步骤3)，建立动态调度系统模型的调度协商机制；

步骤4)，利用顺序聚类方法对连续的调度系统状态进行聚类，以降低状态空间的复杂性；

步骤5)，将对调度规则影响较大的设备利用率UM、相对机器负载LR、平均交货因子FA和平均提前拖期损失PA定义为系统状态特征，对系统状态进行聚类；

步骤6)，利用状态差异度度量聚类状态与瞬时系统状态之间的距离，将聚类状态-动作值代替系统状态-动作值，以状态差异度作为权系数进行Q值函数的迭代更新，所述Q值函数迭代更新的公式为：

其中， 为第n次循环生成的状态动作对 的Q值，n为大于零的整数，t为调度时刻； 为步长参数； 为系统状态St+1与聚类状态 的差异度，该差异度是通过系统状态St+1与聚类状态 的Manhattan距离定量计算出的差异程度；

为第n-1次循环状态动作对 生成的Q值；rt+1为即时回报因子；γ为延迟回报的折扣因子； 为将来回报； 表示第n-1次循环时状态的最大模糊收益加权均值，即系统状态St+1下所有聚类状态的最大收益加权平均和。

2.根据权利要求1所述的制造系统自适应动态调度方法，其特征在于，所述步骤1)中制造系统的动态调度目标函数为：

其中，OBJ为最小化提前拖期惩罚，EPi为单位提前惩罚系数，TPi为单位拖期惩罚系数，Ci为作业Ji的实际完工时间，Di为作业Ji的交货期，Ji表示第i项作业，N为大于0的自然数，i为大于等于1且小于等于N的自然数。

3.根据权利要求1所述的制造系统自适应动态调度方法，其特征在于，所述步骤3)中的调度协商机制为：步骤3.1)，设备Agent在可用的空闲时段发出邀标请求，通知缓冲Agent中的工序进行投标；

步骤3.2)，缓冲Agent根据数据库中的信息及参数生成标书，并向设备Agent提交标书；

步骤3.3)，设备Agent评价所有收集到的标书，确定中标标书；

步骤3.4)，设备Agent通知中标工序并等待中标工序返回确认信息；若未返回，重新进行招投标，否则双方签订合同；

步骤3.5)，更新设备Agent的可用空闲时段，从缓冲Agent中移除中标工序，通知作业Agent发放新的加工工序；

步骤3.6)，重复步骤3.1)至步骤3.5)，直至所有作业分配完成。

4.根据权利要求1所述的制造系统自适应动态调度方法，其特征在于，所述步骤6)中的rt+1采用启发式立即回报函数，其公式如下：

其中，ΣE为作业提前完工惩罚，ΣP为作业拖期惩罚。

5.根据权利要求1所述的制造系统自适应动态调度方法，其特征在于，采用学习算法来实现调度规则的自适应选择和作业加工的自适应调度，所述学习算法采用基于学习次数n的动态贪婪策略：

其中，n为当前学习次数；G为总学习次数；η为搜索幅值，且满足0.95≤η＜1；ξ0为限幅调节系数，ξ0∈(0,(1-η)G)。

说明书

一种制造系统自适应动态调度方法

技术领域

[0001] 本发明涉及制造系统生产调度领域，尤其涉及一种制造系统自适应动态调度方法。

背景技术

[0002] 近年来，高效生产的优化调度或不确定和复杂生产环境下自适应调度是制造系统有待解决的一个重要问题，面对动态生产环境实现自适应的动态调度具有重要意义。不确定生产环境下的自适应生产调度研究正成为一个活跃的研究领域。针对动态调度约束复杂、多变问题，有学者建立了一种约束联动调度模型和算法以实现快速的人机交互动态调度，并提出一种根据系统当前状态动态选择最适应规则的随机自适应调度策略。亦有研究中建立了一种动态调度系统模型，采用改进的Q学习算法以确定自适应调度策略，能够根据生产环境的变化动态选择恰当的调度规则，以满足动态调度的自适应要求。但是，其动态调度算法在学习过程中，动作搜索采用固定的参数值贪婪策略，其贪婪参数取值具有一定的主观性和盲目性，忽略了学习过程中学习经验的动态累积。

发明内容

[0003] 本发明所要解决的技术问题是针对背景技术中所涉及的缺陷，提供一种制造系统自适应动态调度方法，用于指导动态环境下调度策略的自适应选择，提高制造企业的生产效益和竞争力。

[0004] 本发明为解决上述技术问题采用以下技术方案：

[0005] 一种制造系统自适应动态调度方法，包括以下步骤：

[0006] 步骤1)，将最小化提前拖期惩罚作为调度目标，建立制造系统的动态调度目标函数；

[0007] 步骤2)，建立制造系统的动态调度系统模型，所述动态调度系统模型包含作业Agent、状态Agent、设备Agent和缓冲Agent；

[0008] 所述作业Agent用于与人机交互接口对接，对接信息包含作业的数量、工序及加工时间；

[0009] 所述状态Agent用于代理调度系统的状态；

[0010] 所述设备Agent用于代理调度系统的生产设备；

[0011] 所述缓冲Agent表示生产设备的缓冲区，用于代理缓冲区中的待加工工序与设备Agent进行协商；

[0012] 步骤3)，建立动态调度系统模型的调度协商机制；

[0013] 步骤4)，利用顺序聚类方法对连续的调度系统状态进行聚类，以降低状态空间的复杂性；

[0014] 步骤5)，将对调度规则影响较大的设备利用率UM、相对机器负载LR、平均交货因子FA和平均提前拖期损失PA定义为系统状态特征，对系统状态进行聚类；

[0015] 步骤6)，利用状态差异度度量聚类状态与瞬时系统状态之间的距离，将聚类状态-动作值代替系统状态-动作值，以状态差异度作为权系数进行Q值函数的迭代更新，所述Q值函数迭代更新的公式为：

[0016]

[0017] 其中， 为第n次循环生成的状态动作对 的Q值，n为大于零的整数，t为调度时刻； 为步长参数； 为系统状态St+1与聚类状态 的差异度，该
差异度是通过系统状态St+1与聚类状态 的Manhattan距离定量计算出的差异程度；
为第n-1次循环状态动作对 生成的Q值；rt+1为即时回报因子；γ为延迟回
报的折扣因子； 为将来回报； 表示第n-1次循环时状态的最大模糊收益加权
均值，即系统状态St+1下所有聚类状态的最大收益加权平均和。

[0018] 作为本发明一种制造系统自适应动态调度方法进一步的优化方案，所述步骤1)中制造系统的动态调度目标函数为：

[0019]

[0020] 其中，OBJ为最小化提前拖期惩罚，EPi为单位提前惩罚系数，TPi为单位拖期惩罚系数，Ci为作业Ji的实际完工时间，Di为作业Ji的交货期，Ji表示第i项作业，N为大于0的自然数，i为大于等于1且小于等于N的自然数。

[0021] 作为本发明一种制造系统自适应动态调度方法进一步的优化方案，所述步骤3)中的调度协商机制为：

[0022] 步骤3.1)，设备Agent在可用的空闲时段发出邀标请求，通知缓冲Agent中的工序进行投标；

[0023] 步骤3.2)，缓冲Agent根据数据库中的信息及参数生成标书，并向设备Agent提交标书；

[0024] 步骤3.3)，设备Agent评价所有收集到的标书，确定中标标书；

[0025] 步骤3.4)，设备Agent通知中标工序并等待中标工序返回确认信息；若未返回，重新进行招投标，否则双方签订合同；

[0026] 步骤3.5)，更新设备Agent的可用空闲时段，从缓冲Agent中移除中标工序，通知作业Agent发放新的加工工序；

[0027] 步骤3.6)，重复步骤3.1)至步骤3.5)，直至所有作业分配完成。

[0028] 作为本发明一种制造系统自适应动态调度方法进一步的优化方案，所述步骤6)中的rt+1采用启发式立即回报函数，其公式如下：

[0029]

[0030] 其中，ΣE为作业提前完工惩罚，ΣP为作业拖期惩罚。

[0031] 作为本发明一种制造系统自适应动态调度方法进一步的优化方案，采用学习算法来实现调度规则的自适应选择和作业加工的自适应调度，所述学习算法采用基于学习次数n的动态贪婪策略：

[0032]

[0033] 其中，n为当前学习次数；G为总学习次数；η为搜索幅值，且满足0.95≤η＜1；ξ0为限幅调节系数，ξ0∈(0,(1-η)G)。

[0034] 本发明采用以上技术方案与现有技术相比，具有以下技术效果：

[0035] 1.本发明提出的动态调度系统模型中将缓冲Agent从设备Agent中分离出来，大大降低调度系统通信协商过程中的通信量；

[0036] 2.本发明在学习算法中采用基于学习次数的动态贪婪搜索策略，利用学习经验的累积，动态调节知识“利用”和“探索”的概率，使搜索策略更具智能化，避免了搜索的盲目性，提高了搜索效率；

[0037] 3.本发明提出的CDQ算法中Q值迭代同时考虑了将来回报和最大模糊收益加权均值，提高算法的遍历速度和精度；并对已有研究中的Q值迭代更新公式的加权求和进行了改进，进一步拟合算法学习过程与目标函数寻优的一致性；

[0038] 4.本发明提出的自适应动态调度方法对于不确定的生产环境具有更强的有效性和适应性。

附图说明

[0039] 图1是本发明的动态调度系统模型；

[0040] 图2是本发明的不同交货因子的提前拖期惩罚比较；

[0041] 图3是本发明的不同交货因子的求解效率比较；

[0042] 图4是本发明的不同到达率的提前拖期惩罚比较；

[0043] 图5是本发明的不同到达率的求解效率比较。

具体实施方式

[0044] 下面结合附图对本发明的技术方案做进一步的详细说明：

[0045] 本发明公开了一种制造系统自适应动态调度方法，包括以下内容：

[0046] 1、设计动态调度目标函数。给出调度过程中的符号定义如下：车间作业集表示为J＝{J1,J2,L JN}；加工设备集为M＝{M1,M2,L MM}；每个作业由多道工序组成，Oij表示作业Ji的第j道工序的加工时间，同一作业的相邻工序不能在同一台设备上加工，且某个时间段内一台设备只能加工一道工序；作业相互独立且无优先级，作业Ji实际完工时间为Ci，到达时间为ATi，交货期Di的公式如下：

[0047]

[0048] 其中，fi为交货因子；ki为作业Ji的工序总数；下标M、N为大于零的自然数，i为大于等于1小于等于N的自然数。在已有研究中，调度目标主要集中为最小化拖期，而未考虑作业提前完成对库存压力的影响和相应的成本提高。因此，本发明借鉴精良制造理念，充分考虑作业拖期和提前对企业产生的影响，将调度目标确定为最小化提前拖期惩罚：

[0049]

[0050] 式中，EPi为单位提前惩罚系数；TPi为单位拖期惩罚系数。

[0051] 2、针对生产过程的复杂性和动态生产环境的不确定性，本发明建立了基于多Agent的动态调度系统模型，如图1所示。模型主要由以下几种Agent组成：

[0052] 作业Agent(Job Agent,JA)，与人机交互接口对接，包含作业的数量、工序及加工时间等信息。内部封装数据库、注册信息模块、推理机和通讯接口模块。

[0053] 状态Agent(State Agent,SA)，代理调度系统的状态，内部封装数据库、注册信息模块、推理机、执行模块(聚类仿真器)和通讯接口模块。

[0054] 设备Agent(Machine Agent,MA)，代理调度系统的生产设备，通过自身的可用时段进行招标的方式进行动态调度。其内部封装数据库、注册信息模块、推理机、执行模块和通讯接口模块。

[0055] 缓冲Agent(Buffer Agent,BA)，表示生产设备的缓冲区，代理缓冲区中的待加工工序与MA进行协商。其内部封装数据库、注册信息模块、推理机和通讯接口模块。

[0056] 3、设计动态调度系统的调度协商机制。多Agent系统的问题求解是通过Agent之间的协商与优化得到结果。合同网协议是多Agent之间的基本作业分配技术，通过作业的招标、投标和制定合同进行合作与分配。招标Agent以广播的形式向其他所有Agent发布邀标信息。显然，这将产生庞大的通信量，并降低通信效率。为了避免这一问题，在本发明的动态调度系统模型中引入缓冲Agent，即把可在设备Agent加工的工序添加到缓冲Agent中。当设备Agent在可用的空闲时段发出邀标信息时，只需向相应的缓冲Agent发出通知即可，从而降低通信量并大幅提升协商通信效率。基于设备空闲的改进合同网招投标协商过程如下：(1)设备Agent在可用的空闲时段发出邀标请求，通知缓冲Agent中的工序进行投标。(2)缓冲Agent中的推理机根据数据库中的信息及参数生成标书，并向设备Agent提交标书。(3)设备Agent根据调度策略评价所有收集到的标书，确定中标标书。(4)设备Agent通知中标工序并等待中标工序返回确认信息；若未返回，重新进行招投标，否则双方签订合同。(5)更新设备Agent的可用空闲时段，从缓冲Agent中移除中标工序，通知作业Agent发放新的加工工序。(6)所有作业分配完成，调度过程结束。

[0057] 4、设计自适应动态调度算法具体包括：

[0058] A.利用顺序聚类方法对复杂的系统状态进行聚类，以降低状态空间的复杂性。利用状态差异度度量聚类状态与瞬时系统状态之间的距离，将聚类状态-动作值代替系统状态-动作值，以状态差异度作为权系数进行Q值函数的迭代更新。引入动态贪婪搜索策略，以提高算法的速度和精度。综上，本发明提出基于聚类-动态搜索的改进Q学习(Improved Q-learning Based on Clustering-Dynamic Search,CDQ)算法，用于指导设备Agent在动态环境下调度策略选择。

[0059] B.定义系统状态特征分别为对调度规则影响较大设备利用率UM、相对机器负载LR、平均交货因子FA和平均提前拖期损失PA，对系统状态进行聚类。则t时刻的系统状态可表示为St＝(UM,LR,FA,PA)。各状态特征定义如下：

[0060] 设备利用率UM＝To/Te表示t时刻之前设备Agent的有效使用时间To与设备Agent总的空闲可利用时间Te的比值。相对机器负载 表示t时刻设备缓冲区中最大剩余加工时间ωm与所有设备的平均剩余加工时间 的比值。平均交货因子 表示N项作业交货因子fi的平均值。平均提前拖期损失 表
示t时刻作业的损失成本，其中，nb为提前完工和拖期作业的数量之和，EPi和TPi分别为单位提前及拖期惩罚系数。

[0061] 此外，为了消除上述四种状态特征在聚类时单位和数量级差别所产生的影响，且保持各状态特征的原有语义，本发明采用比例因子法处理上述状态特征值。

[0062] 设Cx＝(Cx1,Cx2,L,Cxq)为状态聚类后得到的K个聚类中第x个聚类状态(系统状态中心)。其中，q为特征维数；x＝1,2,L,K。与传统的Q学习算法对明确的系统状态进行判断不同，本发明定义状态差异度以度量系统状态与各聚类状态(系统状态中心)的距离。

[0063] 定义1：t时刻系统状态St与聚类状态Cx之间的Manhattan距离为：

[0064]

[0065] 则系统状态St与聚类状态Cx的差异度为：

[0066]

[0067] 显然， 且当且仅当系统状态St与聚类状态Cx距离最小时，当且仅当系统状态St与聚类状态Cx距离最大时， 所有聚类的状态差
异度向量为：

[0068] 定义2：若满足 则称 为当前系统状态St对应的聚类状态；同理， 为状态St+1对应的聚类状态。

[0069] C.若系统状态St对每个聚类状态的差异度为 经动作at后达到系统状态St+1时的差异度为 则对于 A为系统动作(调度规则)集，各聚类状态动作值为Q(Cx,a))。为了反映将来时刻最大收益的平均水平，取系统状态St+1下所有聚类状态的最大收益加权平均和作为最大模糊收益加权均值 并以下式计算：

[0070]

[0071] 在已有研究中的Q值迭代策略同时考虑了将来回报和最大模糊收益，但此两项采用加权求和方式。当系统状态St+1与当前聚类状态 的相似度较高时，迭代策略中将来回报的权系数较大，使得将来回报与权系数的乘积成为主导因素。最大模糊收益加权系数则非常小，导致最大模糊收益与权系数的乘积对迭代策略产生的影响微弱；反之，将来回报与权系数乘积转为弱项。然而实际应用中，若系统状态与聚类状态距离较近，则将来回报和最大模糊收益与各自权系数的乘积均应较大；反之，乘积均应较小，表示与聚类状态距离较大系统状态的贡献小一些。因此，本发明对已有研究中的Q值更新策略进行改进，给出基于系统瞬时状态对聚类状态之差异度权系数的Q值更新迭代公式为

[0072]

[0073] 其中， 为当前聚类状态 第n次循环生成的Q值； 为步长参数；为系统状态St+1与聚类状态 的差异度； 为第n-1次循环生成的Q值；
rt+1为即时回报因子，采用启发式立即回报设计；γ为延迟回报的折扣因子； 为将来回报； 表示第n-1次循环时状态的最大模糊收益加权均值。步长参数 可由下式获得：

[0074]

[0075] 式中:Wα为αn的权系数变量，非负；ρ为αn非负的收缩因子，控制αn收缩速率；为第n次循环中状态-动作对 被访问的总次数。 增加，则步长参数
αn随之减小。

[0076] 由式(6)可知，将来回报和最大模糊收益加权均值的系数均为 当系统状态St+1与聚类状态 较近时，差异度 较小，而 较大。这使得将来回报
和最大模糊收益加权均值 与系数的乘积 和
均较大，从而保证迭代更新中与聚类状态距离较近的系统状态更易获得
最大的Q值，更容易满足迭代策略需求。

[0077] D.奖惩函数设计。奖惩函数设计应与系统的调度目标相对应。本发明目标函数为式(2)的最小化提前拖期惩罚，而CDQ学习算法又是收敛于最大值。为了使最小化目标函数和最大化Q值函数的优化方向一致，本发明采用启发式立即回报函数设计思想，通过算法的学习，系统将授予启发式的立即回报，引导学习算法更快地收敛到最优策略。因此，算法中的立即回报函数设计如下：

[0078]

[0079] 式中， lE为提前完工作业数量； lT为缓冲区内拖期作业数量；TPl为拖期作业Jl的单位拖期惩罚系数；EPj为提前完工作业Jj的单位提前惩罚系数；Dj和Cj分别为作业Jj的交货期和实际完工时间。

[0080] 式(8)将目标函数的最小化问题转变为回报函数的最大化问题。具体地，在每次学习迭代中，若有工件提前或拖期，则目标函数∑E+∑P＞0，立即回报r＝-(∑E+∑P)＜0。每次迭代学习中目标函数越小，获得的立即回报就越大；若无工件提前或拖期，目标函数最小为0。根据式(8)，系统获得最大的立即回报为1。因此，每次迭代的目标函数累积获得总的目标函数最小则意味着立即回报的累积最大。在调度系统的运行状态下，式(8)定义的启发式立即回报函数能够较精确地评价动作的优劣，为CDQ学习算法直接、及时地提供回报信息，进而引导CDQ算法更快地收敛到最优控制策略。

[0081] E.搜索策略设计。Q学习算法中动作搜索往往采用贪婪策略(ε-greedy)，ε表示知识搜索和利用的概率。它表示状态St下，选择最大评估函数值的动作(即“利用”)的概率为(1-ε)，而以概率ε随机选择其它动作(即“探索”)。ε的大小影响动作的搜索效果。根据ε值对算法的影响，开始学习时应主要进行“探索”。随着学习及经验的积累，知识“利用”的成分逐渐增加。在此过程中，ε值应逐渐减小。鉴于上述分析，经过实验验证，本发明提出以下基于学习次数n的动态贪婪策略：

[0082]

[0083] 式中，n为当前学习次数；G为总学习次数；η为搜索幅值，且满足0.95≤η＜1；ξ0为限幅调节系数，避免ε取无意义的边界值，ξ0∈(0,(1-η)G)。在学习之初，ε(n)≈1表示学习过程中几乎只“探索”不“利用”；随着学习次数的递增，“利用”成分增加，“探索”成分减少；当n接近G时，ε(n)≈0，表示学习过程中几乎只“利用”不“探索”。ε(n)随着n渐变的过程就是搜索过程由“探索”向“利用”经验知识的过渡过程。与传统的固定ε贪婪策略相比，动态贪婪策略更具智能化，可使学习过程动态调整，同时也避免了搜索的盲目性，提高了搜索效率。

[0084] F.算法步骤。结合Agent技术与CDQ算法，基于CDQ算法的自适应动态调度的具体实现概括为：

[0085] Step1：设置最大聚类数K，状态Agent利用顺序聚类法对系统状态进行聚类，得到K个聚类状态Cx,x＝1,2,L,K，并将聚类结果存储到状态Agent的数据库中。

[0086] Step 2：初始化所有聚类状态-动作对的Q值，并存储于设备Agent的知识库中。

[0087] Step 3：对 时刻，置学习次数n＝1，协商调度开始。

[0088] Step 4：如果τt时刻有设备Agent空闲，则随机选择其中之一作为MAk，然后MAk对其空闲时间发布招标信息，并邀请相应BAk中的工序参与投标,转Step 5；否则转Step 14。

[0089] Step 5：若MAk未收到BAk反馈的标书，表示缓冲区BAk中无待加工工序，转Step 12；否则转Step 6。

[0090] Step 6：SA根据式(4)计算当前系统状态St与聚类状态Cx,x＝1,2,L,K的差异度。

[0091] Step 7：若MAk收到h个标书，接收SA中的状态差异度，根据定义2求出当前状态St所对应的聚类状态 根据式(9)的动态贪婪策略从数据库的动作(规则)集中选择具有最大回报值的动作，根据该规则从h个标书中选择中标工序，并发出工序中标通知。

[0092] Step 8：BAk中的中标工序接收到中标消息后，向MAk发出确认信息，双方签订合同。

[0093] Step 9：MAk通过式(8)计算立即回报值；SA观测到下一时刻系统状态St+1，并计算St+1与各聚类状态的差异度。

[0094] Step 10：MAk根据定义2求取St+1对应的聚类状态 推理机通过搜索数据库获得聚类状态 下的最大将来回报 根据式(5)计算最大模糊收益加权均值根据式(6)迭代更新状态-动作对Q值，并将其存储于数据库中，置n＝n+1。

[0095] Step 11：将已签约工序从BA中移除。

[0096] Step 12：如有其它设备Agent空闲，转Step 4；否则，转Step 13。

[0097] Step 13：若所有空闲设备Agent对应的缓冲Agent中均无待加工工序，转Step 14；否则，转Step 15。

[0098] Step 14：BA接收JA分配的新工序。

[0099] Step 15：置t＝t+1，更新τt，转Step 4。

[0100] Step 16：重复Step 4-Step 15，当学习到所有状态-动作对Q值的最优值，算法结束。

[0101] 5、分析自适应动态调度算法的收敛性和复杂性。

[0102] A收敛性分析。令X为系统状态-动作对 的有限集，每个状态-动作对能被无限次访问，Pt是由集合 中所有子集组成的σ-域
系列，对于本发明的Q值迭代方程，当循环次数n→∞时，Qn以概率1收敛到最优控制策略的Q*。

[0103] B复杂性分析。在本发明建立的动态调度系统中，Agent之间的通信是影响系统性能的重要方面，而系统中主要通信发生在招投标阶段。因此，影响算法效率的Agent通信主要由以下几个方面：(1)MA向BA发送招标信息。由于系统中MA和BA分别为M个，招标次数表示为U，故此阶段的通信量为O(UM)；(2)BA提交标书至MA。因为BA中工序数一定小于等于系统中的作业总数N，所以此阶段的最大通信量为O(UNM)；(3)JA向BA发布新工序信息。系统中唯一的JA向M个BA发布的新工序数量不大于系统的作业总数N，故此阶段最大通信量为O(NM)；(4)JA向SA发布系统作业。因为调度模型中仅有一个SA，故通信量为O(N)；(5)SA与MA的信息通信。系统中唯一的SA向M个MA提供状态差异度信息，通信量为O(M)。由上述分析可知，本发明算法的最大通信量为O(MU)+O(MNU)+O(MN)+O(N)+O(M)＝O((M+MN)U+MN+N+M)，在已知的动态调度系统中，机器数M和作业数N均为确定的常数，因此，最大通信量近似为O((M+MN)U)，为计算机可接受。

[0104] 6、仿真实验

[0105] 本发明模仿生产过程中不确定生产环境下的调度环境，设计了一个动态调度仿真模型，以验证上述调度模型和策略的有效性。将作业到达及工序完工定义为系统事件，仿真以事件触发方式进行。系统由M台设备Agent组成。作业总数为N且随机进入系统，到达系统的时间间隔服从负指数分布，平均到达率为λ；作业Ji的交货因子fi服从均匀分布[uf1,uf2]，其包含的工序数是介于[nk1,nk2]之间的随机整数，每道工序的加工时间Oij服从均匀分布[up1,up2]，拖期惩罚系数TPi和提前惩罚系数EPi分别服从均匀分布[ut1,ut2]和[ut3,ut4]。设备Agent知识库中封装的调度规则为最短加工时间优先SPT、最早交货期优先EDD和最小松弛时间优先MST三种常用规则。当进入调度系统的作业数达到N后仿真停止。

[0106] 给出4个基于上述模型的仿真案例，4种案例中作业总数借我N＝3000，惩罚系数均取uf1＝1,uf2＝6，ut1＝2,ut2＝3,ut3＝1及ut4＝2，其他参数设置如表1所示。其中，案例1和2分别表示6台设备运行时，市场需求平稳，产品结构较简单和较复杂的生产情况；案例3和4表示8台设备运行时与案例1和2所对应的生产情况。

[0107] 表1案例参数设置

[0108]

[0109] CDQ算法中延迟回报的折扣因子取γ＝0.7；动作搜索过程中，采用式(9)的动态贪婪系数ε。仿真系统处理完3000个作业后仿真结束。为了减少随机因素的影响，对每个案例进行300次仿真，计算其提前拖期惩罚的均值，并与已有研究中的B-Q、WSQ和CMSQ算法进行比较。已有研究的目标函数为最小化平均拖期，为了便于比较分析，将其目标函数修正为最小化提前拖期惩罚，结果比较如表2所示。为了分析调度策略的求解效率，在4种案例情况下，对不同调度策略的平均运行时间(单位为s)进行比较，结果如表3所示。可以看出，本发明提出的基于聚类-动态搜索的CDQ算法性能优于已有文献中的3种改进Q学习算法。在不同的调度环境中，CDQ算法的调度结果比B-Q、CMSQ和WSQ算法中的最优结果均有所提升，且缩短了算法的求解时间。

[0110] 表2不同策略下的作业提前拖期惩罚比较

[0111]

[0112] 表3不同策略下的求解效率比较

[0113]

[0114] 以市场需求平稳，产品结构复杂的案例4为例进一步验证本发明提出的自适应动态调度策略性能。令交货因子uf1＝1,uf2＝6,6.5,L,9，分别对案例4进行300次仿真，得到4种算法的提前拖期惩罚如图2所示。同时，为了分析算法的求解效率，在相同的仿真环境下，对4种算法在不同交货因子情况下的平均运行时间进行比较，如图3所示。可以看出，对于不同交货因子的调度情况，基于CDQ算法的调度策略求解的提前拖期惩罚值均小于其他3种算法对应的调度策略，同时提高求解效率。

[0115] 在案例4的基础上，将作业到达率分别取λ＝1/4.5,1/5,L,1/6.5，以分析市场需求变化对调度性能的影响。同样经过300次仿真，得到提前拖期惩罚和求解效率结果分别见图4和图5。可以看出，随着市场需求的变化，本发明算法的提前拖期惩罚和平均求解时间均小于已有研究算法的提前拖期惩罚和求解时间，说明本发明算法对动态环境的变化的适应性更强。