一种基于时间约束的并行工作流优化调度方法

1.本发明涉及一种基于时间约束的并行工作流优化调度方法，属于智能计算与调度优化领域。


背景技术：

2.随着信息技术的不断发展，工艺流程日益复杂，需要通过工作流管理系统来实现工艺流程的自动化、标准化和优化。工作流优化是指通过对工作流程进行分析和优化，使得工作流程更加高效、透明和可控。基于时间约束下的工作流优化方法是一种综合考虑时间约束和多目标优化的工作流优化方法，可以帮助企业提高工作效率、降低成本、提高服务质量。
3.在大规模工作流中，优化调度是提高系统性能的关键因素之一。时间约束是工作流调度中最基本的限制条件之一，因为每个任务都有一个截止时间。基于时间约束的并行工作流调度可以确保任务在其截止时间之前完成，同时最大化系统资源利用率和吞吐量。
4.近年来，制造工艺优化领域引起了国内外学者的广泛关注和研究。工作流技术被应用于制造工艺优化调度，以解决时间、质量和成本等关键参数的优化问题。通过工作流技术的应用，可以实现制造工艺优化调度的全面考虑和综合优化。这将对提高制造工艺的效率、质量和成本效益产生积极影响，并在实践中发挥重要作用。


技术实现要素：

5.为实现上述目的，本发明提出一种基于时间约束的并行工作流优化调度方法，包括以下步骤：(1)通过工艺流程的执行关系，并结合dag的特点建立抽象的工作流调度模型。(2)根据优化规则计算每个结点的执行区。(3)将并行路径中的结点集合虚拟成一个结点，使工作流转化为串行路径工作流；通过并行路径的工作流调度算法由后向前进行迭代，通过局部最优解求得全部最优解。(4)遍历dag图通过正向调度输出优化路径及优化值。
6.所述步骤(1)具体为：(1.1)工艺流程中的所有任务组成一个集合，用p＝{p1,p2,
…
pi…
pn}；s表示任务中能完成该任务的服务集合s＝{s1,s2,
…
sj…
sn}；r
p
表示任务的数目，rs表示某个任务中服务的集合。(1.2)任务的服务属性可用一个三元组表示s
ij
＝{t
ij
,c
ij
,a
ij
}；t
ij
表示服务sj完成任务pi所花费的时间，c
ij
表示所花费的成本，a
ij
表示所所达到的准确率。(1.3)添加虚拟开始start及对应的服务ss集合和虚拟结束结点end及对应的服务se集合，以满足顺序依赖和数据依赖执行工作流。(1.4)工作流集合用w＝{v,e}表示；v表示工作流包含虚拟开始start和虚拟结束结点end的结点集合，e表示结点间的顺序关系的集合。
(1.5)扫描工艺流程中的各任务，在起点ps处开始安排首项任务并建立相关联的连接。(1.6)查询与当前任务存在顺序关系的任务集合，使其建立连接，接着查询它的所有后继任务，建立连接，循环迭代，当任务集中无任务时，将最后一层的任务连接到pe(1.7)将相应的服务集添加到现有的dag图中，以便执行任务，并生成一个包含这些服务的列表。
7.所述步骤(2)具体为：(2.1)生产活动结点执行区规则。生产活动执行区可由exi[bai,eai]表示；(2.2)其中：exi为执行区的名称，表示工艺结点活动的时间段；bai表示加工任务pi的最早开始时间，eai示加工任务pi的最晚开始时间；bai和eai的值按照公式1进行计算。(2.3)生产参数约束识别规则。在进行生产过程中，可以累积计算三种指标，分别是累积生产时间、累积生产费用和累积生产质量；用符号分别表示为tq、aq和cq，；因此，对于工作流图中的各结点pi，可以按照公式2进行识别和计算其累积生产参数。(2.4)其中：t
p
表示执行pq前驱任务p
p
时所花费的时间；ψ和c和a分别表示工艺加工中的截止期，成本限制和质量限制。
[0008]
所属步骤(3)具体为：(3.1)将生产工艺流程与bpp算法相结合。(3.2)如果dag图中存在并行路径，通过整合方式将并行任务集合虚拟成一个结点，使工作流串行化；对于dag图中的虚拟结点，同样存在服务集合以及对应服务的属性；v
i-j
表示从任务pi到任务pj组成的虚拟结点。(3.3)循环3.1的操作直到dag图中没有并行路径。(3.4)公式3求解该虚拟结点对应执行域。
(3.5)其中：最快与最慢执行的区间，表示为ψ＝[ψ
min
,ψ
max
,]coni表示为虚拟结点是否包含关键路径某一部分若是则coni＝1否则为0；t
min
表示虚拟结点pi不包含业务流程某部分关键路径时，其通过最小关键路径算法求得的最少执行时间。(3.6)通过虚拟结点对应的执行域下，利用公式4通过逆向的方式计算不同域值下串行路径成本，生成虚拟结点的服务集并最近进行汇总，以达到最小化成本的目标。(3.7)其中：pj表示为i的前驱任务结点，fa(j,t)和fc(j,t)分别表示为不同时刻任务花费的最小成本和最大质量；(3.8)通过层层迭代，确定每个任务所选择的服务，同时得到对应的优化路径。
附图说明
[0009]
图1电厂基建锅炉煤炭管理工艺流程图。
[0010]
图2电厂基建锅炉煤炭管理工作流模型图。
[0011]
图3 bpp算法流程图。
[0012]
图4算法bpp虚拟化过程图。
[0013]
图5算法对生产性能的影响图。
具体实施方式
[0014]
下面结合说明书附图，对本发明作进一步说明。
[0015]
本发明实例如下：步骤1：如图1电厂基建锅炉煤炭管理工艺流程是一个涉及多个生产步骤的复杂系统。该工艺流程被分解为一系列结点p，每个结点p代表一个具体的生产步骤。具体生产步骤如表1所示。表1工艺流程的结点集合步骤2：任务流程中每个任务结点都有一个服务集，其中包含多个服务属性，如时间、准确率和成本等。这些服务属性可以帮助任务流程选择最适合任务需求的服务。具体来说，在任务pi对应的第j个服务中，服务属性s
ij
包括时间、成本和准确率，分别用t
ij
、c
ij
、a
ij
表示如表2。
表2任务所对应服务集步骤3：如图2对电厂基建锅炉煤炭管理工艺流程进行建模，明确每个步骤的执行顺序和所需的资源。然后，将这些步骤和资源组织成一个工作流，以实现业务流程的自动化执行。把时间作为约束条件，以业务流程的准确率或成本为优化目标。通过这种方法，可以找到最佳的优化路径，使得业务流程能够在规定时间内以最小的成本或最高的准确率完成。步骤4：如图3为bpp算法流程图，先求解任务的执行区，然后把时间作为约束条件，以业务流程的准确率或成本为优化目标。查看工作流模型中是否有并行路径，若有将并行路径通过整合的方式将该并行任务集合虚拟成一个结点如图4。通过虚拟化的方式来实现业务流程的串行化。然后从后向前求解并生成调度路径。通过这些步骤，bpp算法可以实现业务流程的高效调度和优化，从而提高生产效率和经济效益。其具体优化结果示意图如图5所示。
[0016]
此外，应当理解，虽然本说明书按照实施方式加以描述，但并非每个实施方式仅包含一个独立的技术方案，说明书的这种叙述方式仅仅是为清楚起见，本领域技术人员应当将说明书作为一个整体，各实施例的技术方案也可以经适当的组合，形成本领域技术人员可以理解的其他实施方式。

技术特征：
1.一种基于时间约束的并行工作流优化调度方法，所述方法具体步骤如下：(1)通过工艺流程的执行关系建立抽象的工作流调度模型。(2)根据优化规则计算每个结点的执行区。(3)将并行路径中的结点集合虚拟成一个结点，使工作流转化为串行路径；接着根据所提出的工作流优化调度算法由后向前进行迭代，通过局部最优解求得全局最优解。(4)遍历dag图通过正向调度输出优化路径及优化值。2.根据权利要求1所述的一种基于时间约束的并行工作流优化调度方法，其特征在于：所述步骤(1)具体为：通过扫描制造工艺流程中的各个生产部门和各部门偏序关系，可以将其抽象为结点集p和边集e，通过调度策略，生成了工艺流程工作流模型。3.根据权利要求2所述的一种基于时间约束的并行工作流优化调度方法，其特征在于：所述步骤(2)具体为：工艺流程的工作流需要遵循特定的约束条件和识别规则，包括生产活动结点的执行区规则和生产参数约束识别规则。同时，需要基于提出的规则计算每个结点的执行区。4.根据权利要求3所述的一种基于时间约束的并行工作流优化调度方法，其特征在于：所述步骤(3)具体为：当工作流模型图中存在并行路径时，可以通过整合方式将并行任务集合虚拟成一个结点，以达到工作流的串行化。同时，需要求解该虚拟结点对应的执行域，接着，通过由后向前的归约来计算每个结点的最优解，即基于各个结点的约束条件，确定最优的执行方案。5.根据权利要求4所述的一种基于时间约束的并行工作流优化调度方法，其特征在于：所述步骤(4)具体为：在正向调度过程中，根据结点的输入输出要求和约束条件，确定一条完整的时间、生产质量和成本最优的调度路径。最后输出优化路径及优化值。

技术总结
一种基于时间约束的并行工作流优化调度方法。本发明主要针对如何优化并行工艺流程提出了工作流模型优化算法。该算法首先根据工艺流程中的任务和偏序关系建立工作流模型。然后根据所提出的规则计算各结点的执行区间，如果工作流模型图中存在并行路径，通过整合方式将并行任务集合虚拟成一个结点，使工作流串行化，同时求解该虚拟结点对应执行域，再通过由后向前归约来计算每各结点的最优解，通过局部最优解获取全局最优解，最终通过正向调度输出优化路径。对比发现，该算法优于传统单目标优化调度算法，对工作流模型的优化效果显著。因此，本发明具有一定的可行性和有效性。本发明具有一定的可行性和有效性。本发明具有一定的可行性和有效性。


技术研发人员：滕文瑶 罗智勇 王姝懿 齐宏卓
受保护的技术使用者：哈尔滨理工大学
技术研发日：2023.07.29
技术公布日：2023/10/15