本发明属于柔性加工特定的分布式制造技术领域，适用于具有Dag(DirectedAcyclic Graph)任务结构且产品输出位置固定的制造业调度优化问题，特别是涉及一种面向定点输出的分布式制造调度方法。

对于一般产品加工任务以DAG(Directed Acyclic Graph)为主要结结构。为满足柔性调度模式，任务中的同一个工序可在不同的设备上加工，且同一设备可加工不同的工序，不同设备对不同工序的加工时间不同。另外，为满足分布式调度模式的要求，设备呈分散状态且由设备间的物流关系形成了设备加工网络。产品的对定点输出是在满足柔性调度及分布式调度的前提下对产生调度的另一现实需求。

已有的面向定点输出的分布式制造调度方法,包括基于动态rank的调度算法，逆序分治求解算法、启发式算法以及动态回退算法等。这些方法的本质是以任务路径的长短以及运输代价的高低作为调度决策,没有将设备柔性加工能力与考虑设备的运输进行综合考虑。对于定点输出问题，任务在选择加工设备时，不仅需要考虑其自身的最早完工时间，还需要考虑所选设备对后续加工的贡献度。此外，由于存在定点输出约束，使得备选设备与输出节点的距离成为任务调度决策的重要因素。因此，在解决具有定点输出的分布式制造调度问题时，应该考虑任务结构及设备网络的分布状态对工序调度的影响，以整体利益最大化作为局部调度决策的导向，从而实现分布式生产的整体调度优化。

本发明目的是为了解决现有的技术问题，提供了一种面向定点输出的分布式制造调度方法。

本发明是通过以下技术方案实现的，本发明提出一种面向定点输出的分布式制造调度方法，采用数据场模型对任务结构及设备分布状态进行度量，其中任务结构度量反应了后续工序对备选工序的影响，设备分布状态度量反应了设备在设备网络中的局部影响力；采用逆向调度方法，从终止设备与终止工序出发，为工序逆向分配设备，从而保障任务的定点输出约束；所述逆向调度方法即从终止设备与终止工序开始调度，并依据工序的紧前约束关系依次进行逆向调度，将开始工序作为最后一次调度的工序。

进一步地，所述逆向调度方法具体为：

步骤1：将终止工序分配到终止设备上，并将终止工序的紧前工序作为备选工序，由备选工序构成的集合即为备选工序集合；

步骤2：若某一任务已分配至设备，则该任务的紧前工序需要以该任务的加工设备或直接相邻的设备作为备选设备；

步骤3：将任务结构度量与设备分布状态度量的比值作为备选工序与其备选设备的优先度，选择优先度最小的一对备选工序与其备选设备作为调度结果；

步骤4：重复上述过程，直到所有的工序分配完毕。

进一步地，所述的任务结构度量的具体实施步骤如下：利用如下公式(1)计算工序vi的任务结构度量：

式中foreword(vi)表示工序vi的备选工序集合，dis(vi,vj)表示工序vi与工序vj在任务结构图中的最小距离，α为控制参数，Aj,·表示加工矩阵A的第j行向量，即工序vj在各设备上加工所需要的时间，其中i和j均表示工序编号，且i和j均为正整数。

进一步地，所述设备分布状态度量的具体实施步骤如下：利用如下公式(2)计算设备mi的设备分布状态度量：

式中uk,i为设备mk与mi之间的运输时间，σ为距离控制参数，Rk和Ri分别为备选工序在设备mk与设备mi上加工的等待时间，其中k和i均表示设备编号，且k和i均为正整数，|M|为设备的数量。

本发明有益效果：

1.本发明利用了逆序调度方法，并在调度过程中考虑了后续加工设备与终止设备的距离以及后续设备的加工能力。在调度决策过程中，以任务结构度量与设备分布状态度量的比值作为备选工序与其备选设备的优先度，选择优先度最小的一对备选工序与其备选设备作为调度结果，从而保证了后续工序的调度优化。

2.本发明利用了数据场的建模方法构造了任务结构度量模型，该模型考虑了后续工序对后续工序对备选工序的影响。任务结构度量体现了后续工序对设备资源的依赖性，并在调度决策过程中对备选工序的调度进行限定，从而建立了以后续约束前续的迭代式全局优化。

3.本发明利用了数据场的建模方法构造了设备分布状态度量模型，该模型考虑了设备的运输距离、设备的忙碌状态以及终止设备距离对备选设备的影响。设备分布状态度量不仅体现了备选设备在网络中的重要性，还体现了忙碌设备对备选设备的影响，因此，以该模型作为调度决策因素，兼顾了运输代价及设备负载代价的调度优化。

4.本发明采用了工序与设备的量化度量方法，并在调度决策时以量化取值作为评判的标准，由于采用了量化式方法，可以对各类任务及加工设备网络提供调度评估方案。

图1是本发明的产品任务结构模型及设备分布状态图；

图2是本发明的产品工序在各设备上的执行时间示意图；

图3是本发明的设备间运输时间矩阵示意图；

图4是本发明对图1所示任务及设备的调度过程示意图；

图5是本发明对工序v5,v6,v7的调度过程图；

图6是本发明对工序v1,v2,v4的调度过程图；

图7是本发明对工序v3的调度过程图；

图8是本发明的正序调度结果甘特图。

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

本发明提出一种面向定点输出的分布式制造调度方法，采用数据场模型对任务结构及设备分布状态进行度量，其中任务结构度量反应了后续工序对备选工序的影响，设备分布状态度量反应了设备在设备网络中的局部影响力；采用逆向调度方法，从终止设备与终止工序出发，为工序逆向分配设备，从而保障任务的定点输出约束；所述逆向调度方法即从终止设备与终止工序开始调度，并依据工序的紧前约束关系依次进行逆向调度，将开始工序作为最后一次调度的工序。

所述逆向调度方法具体为：

步骤1：将终止工序分配到终止设备上，并将终止工序的紧前工序作为备选工序，由备选工序构成的集合即为备选工序集合；

步骤2：若某一任务已分配至设备，则该任务的紧前工序需要以该任务的加工设备或直接相邻的设备作为备选设备；

步骤3：将任务结构度量与设备分布状态度量的比值作为备选工序与其备选设备的优先度，选择优先度最小的一对备选工序与其备选设备作为调度结果；

步骤4：重复上述过程，直到所有的工序分配完毕。

所述的任务结构度量的具体实施步骤如下：利用如下公式(1)计算工序vi的任务结构度量：

式中foreword(vi)表示工序vi的备选工序集合，dis(vi,vj)表示工序vi与工序vj在任务结构图中的最小距离，α为控制参数，Aj,·表示加工矩阵A的第j行向量，即工序vj在各设备上加工所需要的时间，其中i和j均表示工序编号，且i和j均为正整数。

所述设备分布状态度量的具体实施步骤如下：利用如下公式(2)计算设备mi的设备分布状态度量：

式中uk,i为设备mk与mi之间的运输时间，σ为距离控制参数，Rk和Ri分别为备选工序在设备mk与设备mi上加工的等待时间，其中k和i均表示设备编号，且k和i均为正整数，|M|为设备的数量。

本发明所述方法根据任务结构及设备网络的分布状态，分别建立了任务结构度量及设备分布状态度量，其中任务结构度量反应了后续工序对备选工序的影响，设备分布状态度量反应了设备在设备网络中的局部影响力。所建立备选工序与备选设备的量化度量，可以为任务调度提供依据，简化了调度过程，并考虑了任务与设备结构两方面优化。

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

以下将结合图1中的产品任务结构模型及设备分布状态对本发明所述方法的具体流程进行说明，图2和图3分别为产品工序在各设备上的执行时间及设备间运输时间矩阵。任务结构度量仅取决于任务的结构特征，因此，工序的任务结构度量在调度过程中不发生改变。设备分布状态度量取决于设备的等待时间，在进行调度时，设备的等待时间会随调度时刻的改变而改变，因此，设备的分布状态度量在调度过程中会发生变化。图4列出了任务调度过程中各工序的任务结构度量及各时间设备分布状态度量。

对于图1的调度任务，将公式(1)和公式(2)参数取值分别设定为α＝1,σ＝5。当时间t＝0时，由于设备m7与任务v8分别是终止设备与终止工序，因此，需要将设备m7分配给任务v8；当t＝8时，v8在设备m7上加工完毕，此时，v8的前续工序v6与v7成为备选工序，m7与其直接相邻的设备m3,m6成为备选设备。因此，需要判断v6,v7与设备m3,m6,m7的优先度O。此时，由于3个设备上均无加工任务，因此R3＝R6＝R7＝0。图4中，t＝8时，优先度分别为：O6,3＝3.79,O7,3＝1.67,O6,6＝17.24,O7,6＝15.41,O6,7＝7.17,O7,7＝4.22，因此选择O最小的O6,3及O7,7作为任务分配方案，v6与v7的任务分配过程如图5所示。

当t＝15时，v7在设备m7上加工完毕，此时，v7的前续工序v5成为备选工序，m7与其直接相邻的设备m3,m6成为备选设备。如图5所示，此时，设备m3有任务v6正在加工，且m3的最早开始时间为t＝16，因此R3＝1。根据优先度O，选择O5,3作为分配方案。

当t＝16时，v6在设备m3上加工完毕，此时，v6的前续工序v2,v4成为备选工序，m3与其直接相邻的设备m1,m2,m3,m5,m6,m7成为备选设备。如图6所示，此时，设备m3有任务v5正在加工，且m3的最早开始时间为t＝23，因此R3＝7。根据优先度O，选择O2,1,O4,2作为分配方案；当t＝19时，v2在设备m1上加工完毕，此时，v2的前续工序v1成为备选工序，m1与其直接相邻的设备m1,m3,m4成为备选设备。如图6所示，此时，设备m2,m3分别有任务v4,v5正在加工，且m2,m3的最早开始时间分别为t＝22,t＝23，因此R2＝3,R3＝4。根据优先度O，选择O1,1作为分配方案。

当t＝23时，v5在设备m3上加工完毕，且v4已在t＝22时在设备m2上完成加工，此时，v3成为备选工序，与m3,m2与其直接相邻的设备m1,m2,m3,m5,m6,m7成为备选设备。如图7所示，此时，所有设备的R均为0。根据优先度O，选择O3,2作为分配方案。此时调度完毕，对调度结果进行镜面对称得到图8所示的正向调度结果，其总时间为28。

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