[0032] 下面将结合本发明实施例中的附图对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0033] 本发明利用加工设备负载反馈的方法，以加工设备作为任务调度的主动因素，各调度中心进行调控。为避免多个工序在同一时间竞争同一加工设备的问题，本发明采用以时间窗口中加工工序的占用频次及占用时间为输入的调控机制。通过对设备自身负载状态的预测及反馈，调整各调度中心对其分配加工任务的概率。该过程实现了多调度中心对加工设备负载的逆向感知，以减小对其后续任务的分配量，从而实现加工设备的负载均衡。
[0034] 本发明提出一种并行分布式加工调度优化方法，所述方法利用有权随机分配策略为加工工序分配加工设备，以减少并行任务对高效加工设备的竞争；
[0035] 所述的有权随机调度策略，该策略是加工工序对所有满足其加工需求的加工设备进行选择的策略，其中若加工设备对加工工序的适应度越高，其被选择的概率越大，反之，若加工设备对加工工序的适应度越低，其被选择的概率越小。该策略以加工设备的适应度作为加工工序选择加工设备的概率比重，从而保障所有的加工设备均有获得加工的机会，减小加工设备的竞争。
[0036] 所述有权随机分配策略，对加工工序采用如下步骤分配加工设备：
[0037] 步骤1：计算各个加工设备对该加工工序的适应度，并将归一化后的适应度制成饼图；
[0038] 步骤2：在(0,1)区间内生成随机数，若该随机数落在饼图的某一区域，则将该区域所对应的加工设备作为该加工工序的加工设备；
[0039] 在有权随机分配过程中适应度的计算以运输时间、加工设备负载状态、加工设备运行时间以及加工设备执行代价作为输入；所述适应度是加工设备运输优度、加工设备负载状态度量与加工设备执行代价度量之积。
[0040] 基于加工设备间的运输时间对后续加工工序执行时间的影响，所述加工设备运输优度中加工设备dj的运输优度模型Qj表示如下：
[0041]
[0042] 其中ui,j表示设备di到设备dj的运输时间，rank为任务分片后续调度时间的估计，其中i和j均表示设备编号，且i和j均为正整数。
[0043] 所述加工设备负载状态度量以设备在某一固定时间段内被占用的频率为输入，是对设备负载状态的量化预测；所述加工设备负载状态度量的计算方法为：
[0044]
[0045] 其中f为时间窗口中的加工工序个数，T为时间窗口的长度，τi为时间窗口中加工工序vi的执行时间，wi为τi所在时间窗口中的权重，i为加工工序编号，且为正整数。
[0046] 所述加工设备执行代价度量以加工工序的执行代价及运行时间作为适应度的调控系数；其表达式如下：
[0047]
[0048] 其中x和y分别为运行时间与执行代价，β为函数的形状控制参数，α1和α2分别为运行时间与执行代价的权重系数。
[0049] 本发明所述方法考虑了加工设备负载均衡问题，并利用有权随机分配的方式向将加工工序分配加工设备，从而减少并行任务对关键加工设备的竞争。在有权随机分配过程中其权重依赖于调度环境(如运输时间、加工设备负载状态、加工设备运行时间以及加工设备执行代价因素)，并赋予高效加工设备较高的权重，从而使得有权随机分配结果兼具了设备负载均衡优化及加工执行代价优化。
[0050] 结合图1-图8以一具体实例说明本发明所述方法：
[0051] 以下将结合图1中的任务DAG结构模型对本发明所述方法的具体流程进行说明，图1中节点表示加工工序，节点v1和节点v8为起始加工工序和终止加工工序，有向边表示加工工序的有序关系，其权值代表加工工序间的运输代价；图2为各任务间运输时间对后续调度的影响，即ui,jrank；图3中包含加工工序在各加工设备中的运行时间，并列举了各加工工序在3个加工设备d1-3上的运行时间及rank值。
[0052] 图4为某一加工设备d在3个时间窗口{(Crt”-T,Crt”),(Crt'-T,Crt'),(Crt-T,Crt)}内的加工设备占用情况，其中时间窗口的长度为T。本发明在时间窗口的结束时刻Crt”，Crt'，Crt，分别根据{(Crt”-T,Crt”),(Crt'-T,Crt'),(Crt-T,Crt)}内加工设备d的占用情况，计算Crt”，Crt'，Crt时刻加工设备d的Busyness。图4中Crt”时刻占用了(Crt”-T,Crt”)内的3个时间段τ1-3″，其开始时间分别为t1-3″；在Crt'时刻占用了(Crt'-T,Crt')内的5个时间段τ1′-5，其开始时间分别为t1′-5，其中τ4′与τ5′为在(Crt'-T,Crt')时间段内新出现的时间段，且τ5′的有效时间段为(t5′,Crt')；在Crt时刻占用了(Crt-T,Crt)内的5个时间段τ1-5，其开始时间分别为t1-5，其中τ5为新出现的时间段。
[0053] 图5和图6分别为在x＝y以及y＝0时加工设备执行代价度量取值。从图5和图6的对比可知当β越小时执行代价度量取值的取值越低，说明此时加工设备d被选择的概率小。图7为当β＝0.1,α1＝{2,3,4},α2＝1时,y＝0与x＝0的执行代价度量取值对比，其中虚线为β＝0.1,α1＝{2,3,4},α2＝1,x＝0切片下的执行代价度量取值函数曲线。从α1＝{2,3,4}，α2＝
1，y＝0的三条曲线与执行代价度量取值函数曲线(即虚线)对比可知，当α1增加时会增加x对执行代价度量取值的负向影响，反之会增加x对执行代价度量取值的正向影响。同理当α2增加时会增加y对执行代价度量取值的负向影响，反之会增加y对执行代价度量取值的正向影响。因此，α1与α2可以控制运行时间和加工代价对执行代价度量取值的贡献度，从而控制加工设备被选择的概率。
[0054] 图8为利用有权随机调度策略所得到的图1所示任务的调度结果甘特图，其中调度总时间为115。
[0055] 以上对本发明所提供的一种并行分布式加工调度优化方法，进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。
