一种并行分布式加工调度优化方法

摘要

本发明提出了一种并行分布式加工调度优化方法，所述方法考虑了加工设备负载均衡问题，并利用有权随机分配的方式向将加工工序分配加工设备，从而减少并行任务对关键加工设备的竞争。在有权随机分配过程中其权重依赖于调度环境(如运输时间、加工设备负载状态、加工设备运行时间以及加工设备执行代价因素)，并赋予高效加工设备较高的权重，从而使得有权随机分配结果兼具了设备负载均衡优化及加工执行代价优化。

说明书

技术领域

本发明属于柔性加工设备并行加工技术领域，适用于具有Dag(Directed AcyclicGraph)任务结构且加工任务动态出现的加工问题，特别是涉及一种并行分布式加工调度优化方法。

背景技术

加工任务的调度决策问题是调度中心根据加工环境(如加工设备及加工任务)的特征，对加工任务的工序分配最优的加工设备，并保障总体加工时间最优。因此，调度问题涉及加工环境的采集和工序的分配。在考虑加工设备负载均衡问题时，传统的调度模式需要由调度中心对各加工设备的加工状态进行感知，并进行统一决策，以均衡各加工设备的负载。因此，传统的调度模式，属于集中控制模式。对于集中控制模式，调度中心对所有任务进行统一调度，并将调度结果向各加工设备分配，其优势在于：所有的任务由唯一的调度中心进行处理，调度中心掌握所有加工设备的工作状态以及后续分配情况，因此，调度中心可对多个任务进行统一的加工设备分配，以避免多个任务在同一时间竞争同一加工设备的问题。其缺点在于：当任务的工序数量较多且任务结构复杂时，调度中心的负荷较大，不适用于大规模任务的执行。此外，当唯一的调度中心宕机时，所有任务调度均会停止，因此，其系统性风险较大。对于多调度中心模式，其优势在于：各调度中心可以并行调度任务，每个调度单元均可为多个任务提供调度服务，从而减小了各调度中心的负荷，以适应较大规模任务的执行。因此该调度式的系统性风险较小。其缺点在于：各调度中心无法掌握其它调度中心对各个加工设备的占用情况，因此，其调度结果中必存在多个工序在同一时间竞争同一加工设备的情况。若该情况发生，则各工序需要在加工设备上排队，从而延长了任务的预计执行时间，降低了系统的整体效率。

发明内容

本发明目的是为了解决现有的技术问题，提供了一种并行分布式加工调度优化方法。本发明考虑了多个柔性加工设备的加工负载问题，并以负载均衡作为任务调度的约束，实现动态多任务的全局调度优化。

本发明是通过以下技术方案实现的，本发明提出一种并行分布式加工调度优化方法，所述方法利用有权随机分配策略为加工工序分配加工设备，以减少并行任务对高效加工设备的竞争；

所述有权随机分配策略，对加工工序采用如下步骤分配加工设备：

步骤1：计算各个加工设备对该加工工序的适应度，并将归一化后的适应度制成饼图；

步骤2：在(0,1)区间内生成随机数，若该随机数落在饼图的某一区域，则将该区域所对应的加工设备作为该加工工序的加工设备；

在有权随机分配过程中适应度的计算以运输时间、加工设备负载状态、加工设备运行时间以及加工设备执行代价作为输入；所述适应度是加工设备运输优度、加工设备负载状态度量与加工设备执行代价度量之积。

进一步地，基于加工设备间的运输时间对后续加工工序执行时间的影响，所述加工设备运输优度中加工设备d_j的运输优度模型Q_j表示如下：

其中u_i,j表示设备d_i到设备d_j的运输时间，rank为任务分片后续调度时间的估计，其中i和j均表示设备编号，且i和j均为正整数。

进一步地，所述加工设备负载状态度量以设备在某一固定时间段内被占用的频率为输入，是对设备负载状态的量化预测；所述加工设备负载状态度量的计算方法为：

其中f为时间窗口中的加工工序个数，T为时间窗口的长度，τ_i为时间窗口中加工工序v_i的执行时间，w_i为τ_i所在时间窗口中的权重。

进一步地，所述加工设备执行代价度量以加工工序的执行代价及运行时间作为适应度的调控系数；其表达式如下：

其中x和y分别为运行时间与执行代价，β为函数的形状控制参数，α₁和α₂分别为运行时间与执行代价的权重系数。

本发明有益效果：

1.本发明利用了有权随机分配的方式向加工工序分配加工设备，可减少并行加工任务对高效加工设备的竞争。并以运输时间、加工设备负载状态、加工设备运行时间以及加工设备执行代价，作为权重控制因素，使得随机分配结果兼具了设备均衡及加工执行代价优化的合理性。

2.本发明所采用的有权随机分配的方式，是以各加工设备的负载作为反馈参数，控制各调度中心调度加工工序，是以逆向调节的方式解决调度中心间彼此间信息不同步的问题。因此，有权随机分配的方式可以优化解决多调度中心系统的动态调度问题。

3.本发明所设计的加工设备运输优度模型，表达了加工设备运输时间及加工工序执行时间的对调度次序的影响。由于分布制造调度具有分布式、不确定的特性，对此利用加工设备运输优度模型，可以为加工工序的排序问题提供决策依据。

4.本发明所设计的加工设备负载状态度量，表达了加工设备在某一固定时间段内的占用频率即负载。该度量可以预测加工设备在某一特定时刻的负载状态。通过向调度单元反馈该度量，可以判断各个加工设备的负载状态，从而减小处于忙碌状态加工设备的任务分配量，实现加工设备的负载均衡。

5.本发明所设计的加工设备执行代价度量，对加工运行时间及加工代价优化进行了综合建模。该度量表达了加工工序的执行代价对加工设备选择的影响，通过对该模型中权重系数的调整，可以控制执行效率与执行代价的倾向比重。

附图说明

图1是本发明的任务DAG结构模型图；

图2是图1所示加工工序运输时间对后续调度的影响示意图；

图3是图1所示加工工序在各加工设备上的执行时间示意图；

图4是加工设备在3个时间窗口内的占用情况示意图；

图5是当x＝y时加工设备执行代价度量取值示意图；

图6是当y＝0时加工设备执行代价度量取值示意图；

图7是当β＝0.1,α₁＝{2,3,4},y＝0时加工设备执行代价度量取值对比示意图；

图8是图1所示任务的调度结果甘特图。

具体实施方式

下面将结合本发明实施例中的附图对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明利用加工设备负载反馈的方法，以加工设备作为任务调度的主动因素，各调度中心进行调控。为避免多个工序在同一时间竞争同一加工设备的问题，本发明采用以时间窗口中加工工序的占用频次及占用时间为输入的调控机制。通过对设备自身负载状态的预测及反馈，调整各调度中心对其分配加工任务的概率。该过程实现了多调度中心对加工设备负载的逆向感知，以减小对其后续任务的分配量，从而实现加工设备的负载均衡。

本发明提出一种并行分布式加工调度优化方法，所述方法利用有权随机分配策略为加工工序分配加工设备，以减少并行任务对高效加工设备的竞争；

所述的有权随机调度策略，该策略是加工工序对所有满足其加工需求的加工设备进行选择的策略，其中若加工设备对加工工序的适应度越高，其被选择的概率越大，反之，若加工设备对加工工序的适应度越低，其被选择的概率越小。该策略以加工设备的适应度作为加工工序选择加工设备的概率比重，从而保障所有的加工设备均有获得加工的机会，减小加工设备的竞争。

所述有权随机分配策略，对加工工序采用如下步骤分配加工设备：

步骤1：计算各个加工设备对该加工工序的适应度，并将归一化后的适应度制成饼图；

步骤2：在(0,1)区间内生成随机数，若该随机数落在饼图的某一区域，则将该区域所对应的加工设备作为该加工工序的加工设备；

在有权随机分配过程中适应度的计算以运输时间、加工设备负载状态、加工设备运行时间以及加工设备执行代价作为输入；所述适应度是加工设备运输优度、加工设备负载状态度量与加工设备执行代价度量之积。

基于加工设备间的运输时间对后续加工工序执行时间的影响，所述加工设备运输优度中加工设备d_j的运输优度模型Q_j表示如下：

其中u_i,j表示设备d_i到设备d_j的运输时间，rank为任务分片后续调度时间的估计，其中i和j均表示设备编号，且i和j均为正整数。

所述加工设备负载状态度量以设备在某一固定时间段内被占用的频率为输入，是对设备负载状态的量化预测；所述加工设备负载状态度量的计算方法为：

其中f为时间窗口中的加工工序个数，T为时间窗口的长度，τ_i为时间窗口中加工工序v_i的执行时间，w_i为τ_i所在时间窗口中的权重，i为加工工序编号，且为正整数。

所述加工设备执行代价度量以加工工序的执行代价及运行时间作为适应度的调控系数；其表达式如下：

其中x和y分别为运行时间与执行代价，β为函数的形状控制参数，α₁和α₂分别为运行时间与执行代价的权重系数。

本发明所述方法考虑了加工设备负载均衡问题，并利用有权随机分配的方式向将加工工序分配加工设备，从而减少并行任务对关键加工设备的竞争。在有权随机分配过程中其权重依赖于调度环境(如运输时间、加工设备负载状态、加工设备运行时间以及加工设备执行代价因素)，并赋予高效加工设备较高的权重，从而使得有权随机分配结果兼具了设备负载均衡优化及加工执行代价优化。

结合图1-图8以一具体实例说明本发明所述方法：

以下将结合图1中的任务DAG结构模型对本发明所述方法的具体流程进行说明，图1中节点表示加工工序，节点v₁和节点v₈为起始加工工序和终止加工工序，有向边表示加工工序的有序关系，其权值代表加工工序间的运输代价；图2为各任务间运输时间对后续调度的影响，即u_i,jrank；图3中包含加工工序在各加工设备中的运行时间，并列举了各加工工序在3个加工设备d_1-3上的运行时间及rank值。

图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″，其开始时间分别为t_1-3″；在Crt'时刻占用了(Crt'-T,Crt')内的5个时间段τ₁′_-5，其开始时间分别为t₁′_-5，其中τ₄′与τ₅′为在(Crt'-T,Crt')时间段内新出现的时间段，且τ₅′的有效时间段为(t₅′,Crt')；在Crt时刻占用了(Crt-T,Crt)内的5个时间段τ_1-5，其开始时间分别为t_1-5，其中τ₅为新出现的时间段。

图5和图6分别为在x＝y以及y＝0时加工设备执行代价度量取值。从图5和图6的对比可知当β越小时执行代价度量取值的取值越低，说明此时加工设备d被选择的概率小。图7为当β＝0.1,α₁＝{2,3,4},α₂＝1时,y＝0与x＝0的执行代价度量取值对比，其中虚线为β＝0.1,α₁＝{2,3,4},α₂＝1,x＝0切片下的执行代价度量取值函数曲线。从α₁＝{2,3,4}，α₂＝1，y＝0的三条曲线与执行代价度量取值函数曲线(即虚线)对比可知，当α₁增加时会增加x对执行代价度量取值的负向影响，反之会增加x对执行代价度量取值的正向影响。同理当α₂增加时会增加y对执行代价度量取值的负向影响，反之会增加y对执行代价度量取值的正向影响。因此，α₁与α₂可以控制运行时间和加工代价对执行代价度量取值的贡献度，从而控制加工设备被选择的概率。

图8为利用有权随机调度策略所得到的图1所示任务的调度结果甘特图，其中调度总时间为115。

以上对本发明所提供的一种并行分布式加工调度优化方法，进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。