本发明属于柔性加工特定的分布式制造技术领域，适用于具有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是本发明的正序调度结果甘特图。

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