本发明涉及一种基于超网络的制造服务供需匹配与动态调度方法，包括以下步骤：A.构建制造服务供需匹配超网络模型；B.在任务被实际执行之前，进行初始时刻的制造服务预调度；C.将制造服务动态调度的时间按单位时间单元进行等距连续划分，从t＝1时间单元起，每隔单位时间单元定期生成动态环境并执行超网络的动态更新；D.若超网络发生变化则执行动态调度判断，否则进入下一时间单元或者判断若满足终止条件则结束；E.若当前调度方案被破坏则执行动态再调度，生成新的调度方案。本发明能够有效反映面向服务的制造系统中的动态环境，并能保证制造服务动态调度的有效性以及参与企业较高的协作可靠性。
1.一种基于超网络的制造服务供需匹配与动态调度方法，其特征在于包括步骤如下：
A：将提交至面向服务的制造(Service-oriented Manufacturing,SoM)系统中的制造服务和制造任务抽象成网络节点，将不同制造服务之间和不同制造任务之间的各种关联关系抽象成网络中的边，分别构建制造服务网络模型和制造任务网络模型；将制造服务与制造任务之间的可匹配关系抽象成制造服务网络与制造任务网络之间的超边，最终构建制造服务供需匹配超网络(manufacturing service supply-demand matching hypernetwork,Matching_Net)模型，即制造服务供需匹配超网络Matching_Net模型由制造服务网络、制造任务网络以及两层网络间的超边集合三部分组成；此外若任务节点与多个服务节点具有可匹配关系，则该任务节点与这些服务节点间的超边构成了该任务节点的超边集合；
B：在任务被实际执行之前，提取Matching_Net模型中各个任务节点对应的超边集合以及提取各个超边对应的可靠性与效用值，根据面向不确定任务的制造服务预调度的目标函数，进行初始时刻t＝0的制造服务预调度，得到当前时刻最优执行方案；将制造服务动态调度的时间按单位时间单元Δt进行等距连续划分，t＝0时刻预调度得到的执行方案在之后的时间单元内进行执行；所述面向不确定任务是指任务需求的可执行时间区间确定，但实际执行时间区间不确定；
C：从t＝0直至结束的所有时间单元内，根据当前时间单元的开始时刻所决定的方案进行执行，并且Matching_Net模型以一定的概率在当前时间单元发生动态操作，从t＝1时间单元的开始时刻起，每隔单位时间单元Δt，定期判断前一时间单元内是否发生了动态操作，若发生了动态操作则更新Matching_Net模型，并进入步骤D，若没有发生动态操作则继续判断是否满足设定的终止条件以决定下一步操作；
D：判断更新后的Matching_Net模型是否破坏了前一时间单元的执行方案，若执行方案遭到破坏则进入步骤E，若执行方案没有遭到破坏则继续判断是否满足终止条件以决定下一步操作；
E：提取更新后的Matching_Net模型中各个任务节点对应的超边集合以及提取各个超边对应的可靠性与效用值，并对可靠性与效用值进行衰减处理，然后实施再调度，遭到破坏的执行方案被修复或新的执行方案生成之后，进入步骤C。
2.根据权利要求1所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述构建的制造服务网络模型为S_Net＝，其中S表示的服务节点集合可被描述为S＝{s1,s2,…,si,…,sn}，n为集合S中服务节点的数量，ES表示的S_Net中不同服务之间的边的集合可被描述为 i和j分别为不同服务之间的边 所连接的服务的编号。
3.根据权利要求1所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述构建的制造任务网络模型为T_Net＝，其中T表示任务节点集合，被描述为T＝{G1,G2,…,Gp,…,Gm}，m为集合T中任务节点的数量，任务节点用图Gp表示，它既可能是独立的简单任务又可能是可被分解成多个简单任务的复杂任务；ET表示T_Net中不同任务之间的边的集合，可被描述为 其中p和q为不同任务之间的边 所连接的任务编号，k为第p个任务的第k个简单子任务，l为第q个任务的第l个简单子任务，k和l为整数，k的取值最小为1最大为第p个任务分解成的简单子任务的数量，l的取值最小为
1最大为第q个任务分解成的简单子任务的数量， 表示第p个任务的第k个简单子任务与第q个任务的第l个简单子任务之间的关联边。
4.根据权利要求1所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述制造服务供需匹配超网络Matching_Net模型由制造服务网络S_Net，制造任务网络T_Net以及两层网络间的超边集合ES_T三部分组成：其中将每个制造服务节点与每个制造任务节点之间的可匹配关系抽象成超边，制造服务网络模型S_Net与制造任务网络模型T_Net两层网络之间的超边集合，描述为 其中 表示制造服务网络模型S_Net中第i个服务节点si与制造任务网络模型T_Net中第q个任务的第l个简单子任务节点 之间的可匹配关系。
5.根据权利要求1所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述步骤C中的动态操作是指：在面向服务的制造SoM系统的动态运营及其制造服务的动态执行过程中，供需匹配超网络Matching_Net模型中的三个组成部分所发生的动态变化，包括：Matching_Net模型中①制造服务节点或节点集合的新增与删除，服务关联边的新增、删除与属性变化；②制造任务节点或节点集合的新增与删除，任务关联边的新增、删除与属性变化；③两层网络之间的超边的新增、重连、删除与属性变化，当新增服务加入到SoM系统中时，创建新增服务节点并添加到服务网络S_Net中，并根据其与其他服务的关联关系添加新边，根据其与任务的关联关系添加超边；同理，当新任务到达后，新增任务节点并添加相应的新边和超边；另外，在动态执行过程中的第t个时间单元内，若服务节点si发生故障，则删除掉服务节点si及其所关联的超边；若超边 发生故障，则只删除该超边。
6.根据权利要求1所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述步骤B具体包括步骤：B1：提取Matching_Net模型中各个任务节点对应的超边集合，即各个任务节点对应的可选服务的集合，描述为 即第t个时间单元结束时任务节点 对应的可供选择的可匹配服务的集合，预调度时t＝0；i为制造服务网络模型S_Net中第i个服务节点，q和l分别为制造任务网络模型T_Net中第q个任务的第l个简单子任务节点；1≤i≤n，n为集合S中服务节点的数量，1≤q≤m，m为集合T中任务节点的数量，l为整数，l的取值最小为1最大为第q个任务分解成的简单子任务的数量；
B2：提取各个超边对应的可靠性、效用属性参数，效用值综合考虑成本、能耗、风险和完成时间四个指标，可靠性考虑服务执行任务时发生故障的概率；预调度的目标函数综合考虑系统中服务调用的平均效用和平均可靠性的综合值；
B3：执行制造服务预调度，得到当前最优执行方案，将制造服务动态调度的时间按单位时间单元Δt进行等距连续划分，t＝0时刻预调度得到的执行方案在t＝0之后的时间单元内进行执行。
7.根据权利要求1所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述步骤C具体包括步骤：C1：每间隔一个单位时间单元Δt进入新的时间单元是，根据当前时间单元的开始时刻所决定的方案进行执行，并且在当前时间单元内Matching_Net模型会以一定的概率发生动态操作；
C2：进入下一时间单元即触发下一时刻，t＝t+1，判断在前一时间单元内是否发生动态操作，若发生了动态操作则更新超网络模型Matching_Net，并进入步骤D，否则进入C3；
C3：若在前一时间单元内没有发生动态操作，继续判断当前时刻Matching_Net模型状态是否满足终止条件，若满足终止条件则结束，若不满足终止条件则保持前一时间单元内未发生变化的执行方案继续执行，并进入C1重复步骤C。
8.根据权利要求1所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述步骤D具体包括步骤：D1：判断更新后的Matching_Net模型是否破坏了前一时间单元的执行方案，即判断被调用的服务节点或者其与相应任务对应的超边是否发生故障；若影响了前一时间单元的执行方案，则进入下一步D2，否则进入D4；
D2：判断更新后的Matching_Net模型是否破坏了前一时间单元内制造任务节点所对应的超边集合；若没有破坏制造任务节点所对应的超边集合则直接进入步骤E，否则进入下一步D3；
D3：更新当前制造任务节点所对应的超边集合，然后进入步骤E；
D4：判断当前Matching_Net模型状态是否满足终止条件，若满足终止条件则结束，若不满足终止条件则保持前一时间单元内未发生变化的执行方案继续执行，并进入C1重复步骤C。
9.根据权利要求1所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述步骤E具体包括步骤：E1：提取更新后的Matching_Net模型中各个任务节点对应的超边集合，并提取各个超边对应的可靠性与效用值；
E2：受到影响的制造任务重新进行新的服务调用时，所产生的效用存在一定的衰减，对相应的超边所对应的效用值属性以一定的规律进行衰减处理；
E3：判断受到破坏的前一时间单元的执行方案是否可进行局部修复；若可局部修复则基于当前调度方案进行局部再调度，否则执行制造服务全局再调度重新生成新的最优执行方案；局部再调度与全局再调度统称为动态再调度，是动态再调度在上述两种情况下的不同再调度方式；
E4：动态再调度实施后，受到破坏的执行方案被修复或新的执行方案生成，进入步骤C。
10.根据权利要求2所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述制造服务网络模型S_Net中，对服务节点集合S中某服务节点si，其每一种功能对应有一组特定的输入输出描述信息集，u为服务节点si的功能的编号，u为整数，u的取值最小为1最大为服务节点si所具有的功能的总数量，不同服务之间的边的集合ES中的元素 的值定义如下：定义服务节点si与sj的功能相似关系判定参数为FSij＝∩，若 则认为服务节点si与sj之间为功能相似关系，令 定义服务节点si与sj的功能互补关系判定参数为若 或者 则认为服务
节点si与sj之间为功能互补关系，令 若 则认为服务节
11.根据权利要求3所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述制造任务网络模型T_Net中，任务节点集合T中某个任务节点对应的子图Gp，若Gp是简单任务，则Gp即是简单任务节点 其中k＝1；若Gp是复杂任务，则Gp可分解成多个简单任务节点，对任意分解后的简单任务节点 k为第p个任务分解成的多个简单子任务节点的编号，k为整数，k的取值最小为1最大为第p个任务分解成的简单子任务的数量，只有唯一的 一 对 输 入 和 输 出 描 述 信 息 则 可 描 述 为表示任务
需求执行时间段的开始时间与结束时间，不同任务之间的边的集合为ET中的元素 的值定义如下：当两个不同的简单任务分解自同一复杂任务子图时，k和l为第p个任务分解成的简单子任务节点的编号，k和l为整数，k和l的取值最小均为1最大均为第p个任务分解成的简单子任务的数量，存在三种情况：①有 指向 的边，令 表示 与 有需求互补即可组合关系且 为前驱任务，定义有向边参数 ②有 指向 的边，令则表示 与 有需求互补即可组合关系且 为后继任务，定义有向边参数 即③ 与 之间没有边，令 且 当两个不同简单任务来自不同的复杂任务子图时，若 则 与 之间有需求
相似边，k为第p个任务分解成的简单任务节点的编号，k为整数，k的取值最小为1最大为第p个任务分解成的简单子任务的数量，l为第q个任务分解成的简单任务节点的编号，l为整数，l的取值最小均为1最大均为第q个任务分解成的简单子任务的数量，令 若则 与 之间有有向边表示需求互补关系即可组合关系，且 是 的前驱任务，令 且有向边参数 同理若
补关系即可组合关系，且 是 的后继任务，令 且有向边参数 其他情况
12.根据权利要求4所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：所述供需匹配超网络Matching_Net中超边集合ES_T中的元素 的数值定义如下，若服务节点si，si的输入输出描述信息为，与任务节点 的输入和输出描述信息为 之间不可匹配即则超边不存在，令
13.根据权利要求9所述的基于超网络的制造服务供需匹配与动态调度方法，其特征在于：在进行动态再调度时，受到影响的制造任务进行新的服务调用时，新调用的服务所产生的效用会存在一定的衰减；衰减程度与任务原调用的服务已执行的时间成正比，即原调用的服务已执行的时间越长，则新调用的服务执行时所产生的效用的衰减程度越大。
一种基于超网络的制造服务供需匹配与动态调度方法
技术领域
[0001] 本发明属于面向服务的制造(Service-oriented Manufacturing,SoM)系统中制造服务与制造任务供需匹配与优化配置技术领域，具体涉及一种基于超网络的制造服务供需匹配与动态调度方法。
背景技术
[0002] 在SoM系统中，各类制造资源和制造能力通过一定的感知与接入、虚拟化、服务化等处理后，以制造服务的形式存在，并可以通过网络被聚合、检索、调用，为社会化的用户提供面向全生命周期的各类应用。同时，产品全生命周期过程中涉及到的所有与生产相关或与产品相关的任务以及其他服务需求，以制造任务的形式存在，这些制造任务需要调用不同的生产相关或产品相关的制造服务来完成。
[0003] SoM系统中的供需匹配即是制造任务与制造服务之间的映射。这种映射关系除了体现一般供需数量的匹配之外，更包括在供需对象功能匹配基础上进行的制造服务按需优选、组合、调度等一系列流程操作。同时，SoM系统中的供需匹配体现了制造执行过程中具有的持续性，因此其匹配同时包括静态预调度和动态再调度的双重决策。
[0004] 目前研究制造资源/服务的供需匹配与调度的方法有：基于模板的方法、基于流程驱动的方法、基于人工智能和规划的方法、基于供应链的方法、基于图论的方法等。然而，这些研究大部分主要针对某时刻的供需匹配问题进行研究并给出方案，而针对资源服务和任务需求同时不确定或者动态变化情况下的供需动态匹配，当前研究不足。同时由于制造的社会化，使得供需规模不断扩大，简化的数学模型已无法满足实际需求。
[0005] 为解决以上问题，实现SoM系统中制造服务与制造任务的供需匹配与优化配置，本发明首先构建了制造服务供需匹配超网络模型，在此基础上研究了动态环境下的制造服务动态调度方法。
发明内容
[0006] 本发明的目的：本发明涉及的基于超网络的制造服务供需匹配与动态调度方法，能够有效反映面向服务的制造系统中的动态环境，并能保证制造服务动态调度的有效性以及参与企业的较高的协作可靠性。
[0007] 其为一种能够反映制造服务与制造任务供需间的映射对应关系的供需匹配超网络模型的构建方法，以及在制造协作和服务执行过程中面对超网络模型多种动态操作时的制造服务动态调度方法。该发明能有效反映面向服务的制造系统中的动态环境，并能保证制造服务动态调度的有效性以及参与企业的较高的协作可靠性。
[0008] 本发明采用的技术方案为：一种基于超网络的制造服务供需匹配与动态调度方法，包括步骤：
[0009] A：将提交至面向服务的制造(Service-oriented Manufacturing,SoM)系统中的制造服务和制造任务抽象成网络节点，将不同制造服务之间和不同制造任务之间的各种关联关系抽象成网络中的边，分别构建制造服务网络模型和制造任务网络模型；将制造服务与制造任务之间的可匹配关系抽象成制造服务网络与制造任务网络之间的超边，最终构建制造服务供需匹配超网络(manufacturing service supply-demand matching hypernetwork,Matching_Net)模型，即制造服务供需匹配超网络Matching_Net模型由制造服务网络、制造任务网络以及两层网络间的超边集合三部分组成；此外若任务节点与多个服务节点具有可匹配关系，则该任务节点与这些服务节点间的超边构成了该任务节点的超边集合；
[0010] B：在任务被实际执行之前，提取Matching_Net模型中各个任务节点对应的超边集合以及提取各个超边对应的可靠性与效用值，根据面向不确定任务的制造服务预调度的目标函数，进行初始时刻t＝0的制造服务预调度，得到当前时刻最优执行方案。将制造服务动态调度的时间按单位时间单元Δt进行等距连续划分，t＝0时刻预调度得到的执行方案在之后的时间单元内进行执行；所述面向不确定任务是指任务需求的可执行时间区间确定，但实际执行时间区间不确定；
[0011] C：从t＝0直至结束的所有时间单元内，根据当前时间单元的开始时刻所决定的方案进行执行，并且Matching_Net模型以一定的概率在当前时间单元发生动态操作，从t＝1时间单元的开始时刻起，每隔单位时间单元Δt，定期判断前一时间单元内是否发生了动态操作，若发生了动态操作则更新Matching_Net模型，并进入步骤D，若没有发生动态操作则继续判断是否满足设定的终止条件以决定下一步操作；
[0012] D：判断更新后的Matching_Net模型是否破坏了前一时间单元的执行方案，若执行方案遭到破坏则进入步骤E，若执行方案没有遭到破坏则继续判断是否满足终止条件以决定下一步操作；
[0013] E：提取更新后的Matching_Net模型中各个任务节点对应的超边集合以及提取各个超边对应的可靠性与效用值，并对可靠性与效用值进行衰减处理，然后实施再调度，遭到破坏的执行方案被修复或新的执行方案生成之后，进入步骤C。
[0014] 所述构建的制造服务网络模型为S_Net＝，其中S表示的服务节点集合可被描述为S＝{s1,s2,…,si,…,sn}，n为集合S中服务节点的数量，ES表示的S_Net中不同服务之间的边的集合可被描述为 i和j分别为不同服务之间的边 所连接的服务的编号。
[0015] 所述构建的制造任务网络模型为T_Net＝，其中T表示任务节点集合，被描述为T＝{G1,G2,…,Gp,…,Gm}，m为集合T中任务节点的数量，任务节点用图Gp表示，它既可能是独立的简单任务又可能是可被分解成多个简单任务的复杂任务；ET表示T_net中不同任务之间的边的集合，可被描述为 其中p和q为不同任务之间的边所连接的任务编号，k为第p个任务的第k个简单子任务，l为第q个任务的第l个简单子任务，k和l为整数，k的取值最小为1最大为第p个任务分解成的简单子任务的数量，l的取值最小为1最大为第q个任务分解成的简单子任务的数量， 表示第p个任务的第k个简单子任务与第q个任务的第l个简单子任务之间的关联边。
[0016] 所述制造服务供需匹配超网络Matching_Net模型由制造服务网络S_Net，制造任务网络T_Net以及两层网络间的超边集合ES_T三部分组成：其中将每个制造服务节点与每个制造任务节点之间的可匹配关系抽象成超边，制造服务网络模型S_Net与制造任务网络模型T_Net两层网络之间的超边集合，描述为 其中 表示制造服务网络模型S_Net中第i个服务节点si与制造任务网络模型T_Net中第q个任务的第l个简单子任务节点之间的可匹配关系。
[0017] 所述步骤C中的动态操作是指：在面向服务的制造SoM系统的动态运营及其制造服务的动态执行过程中，供需匹配超网络Matching_Net模型中的三个组成部分所发生的动态变化，包括：Matching_Net模型中①制造服务节点或节点集合的新增与删除，服务关联边的新增、删除与属性变化；②制造任务节点或节点集合的新增与删除，任务关联边的新增、删除与属性变化；③两层网络之间的超边的新增、重连、删除与属性变化，当新增服务加入到SoM系统中时，创建新增服务节点并添加到服务网络S_Net中，并根据其与其他服务的关联关系添加新边，根据其与任务的关联关系添加超边；同理，当新任务到达后，新增任务节点并添加相应的新边和超边；另外，在动态执行过程中的第t个时间单元内，若服务节点si发生故障，则删除掉服务节点si及其所关联的超边；若超边 发生故障，则只删除该超边。
[0018] 所述步骤B具体包括步骤：
[0019] B1：提取Matching_Net模型中各个任务节点对应的超边集合，即各个任务节点对应的可选服务的集合，描述为 即第t个时间单元结束时任务节点对应的可供选择的可匹配服务的集合，预调度时t＝0；i为制造服务网络模型S_Net中第i个服务节点，q和l分别为制造任务网络模型T_Net中第q个任务的第l个简单子任务节点；1≤i≤n，n为集合S中服务节点的数量，1≤q≤m，m为集合T中任务节点的数量，l为整数，l的取值最小为1最大为第q个任务分解成的简单子任务的数量；
[0020] B2：提取各个超边对应的可靠性、效用属性参数，效用值综合考虑成本、能耗、风险和完成时间四个指标，可靠性考虑服务执行任务时发生故障的概率；预调度的目标函数综合考虑系统中服务调用的平均效用和平均可靠性的综合值；
[0021] B3：执行制造服务预调度，得到当前最优执行方案；将制造服务动态调度的时间按单位时间单元Δt进行等距连续划分，t＝0时刻预调度得到的执行方案在t＝0之后的时间单元内进行执行。
[0022] 所述步骤C具体包括步骤：
[0023] C1：每间隔一个单位时间单元Δt进入新的时间单元时，根据当前时间单元的开始时刻所决定的方案进行执行，并且在当前时间单元内Matching_Net模型会以一定的概率发生动态操作；
[0024] C2：进入下一时间单元即触发下一时刻，t＝t+1，判断在前一时间单元内是否发生动态操作，若发生了动态操作则更新超网络模型Matching_Net，并进入步骤D，否则进入C3；
[0025] C3：若在前一时间单元内没有发生动态操作，继续判断当前时刻Matching_Net模型状态是否满足终止条件，若满足终止条件则结束，若不满足终止条件则保持前一时间单元内未发生变化的执行方案继续执行，并进入C1重复步骤C。
[0026] 所述步骤D具体包括步骤：
[0027] D1：判断更新后的Matching_Net模型是否破坏了前一时间单元的执行方案，即判断被调用的服务节点或者其与相应任务对应的超边是否发生故障；若影响了前一时间单元的执行方案，则进入下一步D2，否则进入D4；
[0028] D2：判断更新后的Matching_Net模型是否破坏了前一时间单元内制造任务节点所对应的超边集合；若没有破坏制造任务节点所对应的超边集合则直接进入步骤E，否则进入下一步D3；
[0029] D3：更新当前制造任务节点所对应的超边集合，然后进入步骤E；
[0030] D4：判断当前Matching_Net模型状态是否满足终止条件，若满足终止条件则结束，若不满足终止条件则保持前一时间单元内未发生变化的执行方案继续执行，并进入C1重复步骤C。
[0031] 所述步骤E具体包括步骤：
[0032] E1：提取更新后的Matching_Net模型中各个任务节点对应的超边集合，并提取各个超边对应的可靠性与效用值；
[0033] E2：受到影响的制造任务重新进行新的服务调用时，所产生的效用存在一定的衰减，对相应的超边所对应的效用值属性以一定的规律进行衰减处理；
[0034] E3：判断受到破坏的前一时间单元的执行方案是否可进行局部修复；若可局部修复则基于当前调度方案进行局部再调度修复，否则执行制造服务全局再调度重新生成新的最优执行方案；局部再调度与全局再调度统称为动态再调度，是动态再调度在上述两种情况下的不同再调度方式；
[0035] E4：动态再调度实施后，受到破坏的执行方案被修复或新的执行方案生成，进入步骤C。
[0036] 所述制造服务网络模型S_Net中，对服务节点集合S中某服务节点si，其每一种功能对应有一组特定的输入输出描述信息集，u为服务节点si的功能的编号，u为整数，u的取值最小为1最大为服务节点si所具有的功能的总数量，不同服务之间的边的集合ES中的元素 的值定义如下：定义服务节点si与sj的功能相似关系判定参数为FSij＝∩，若 则认为服务节点si与sj之间为功能相似关系，令 定义服务节点si与sj的功能互补关系判定参数为若 或者 则认为服务节点si与sj之间为功能互补关系，令 若 则认为服务
节点si与sj之间不存在关联边，令
[0037] 所述制造任务网络模型T_Net中，任务节点集合T中某个任务节点对应的子图Gp，若Gp是简单任务，则Gp即是简单任务节点 其中k＝1；若Gp是复杂任务，则Gp可分解成多个简单任务节点，对任意分解后的简单任务节点 k为第p个任务分解成的多个简单子任务节点的编号，k为整数，k的取值最小为1最大为第p个任务分解成的简单子任务的数量， 只有唯一的一对输入和输出描述信息 则 可描述为表示任务
需求执行时间段的开始时间与结束时间，不同任务之间的边的集合为ET中的元素 的值定义如下：当两个不同的简单任务分解自同一复杂任务子图时，k和l为第p个任务分解成的简单子任务节点的编号，k和l为整数，k和l的取值最小均为1最大均为第p个任务分解成的简单子任务的数量，存在三种情况：①有 指向 的边，令 表示 与 有需求互补即可组合关系且 为前驱任务，定义有向边参数 ②有 指向 的边，令 则表示 与 有需求互补即可组合关系且 为后继任务，定义有向边参数 即
③ 与 之间没有边，令 且 当两个不同简单任务来自不同
的复杂任务子图时，若 则 与 之间有需求
相似边，k为第p个任务分解成的简单任务节点的编号，k为整数，k的取值最小为1最大为第p个任务分解成的简单子任务的数量，l为第q个任务分解成的简单任务节点的编号，l为整数，l的取值最小均为1最大均为第q个任务分解成的简单子任务的数量，令 若则 与 之间有有向边表示需求互
补关系即可组合关系，且 是 的前驱任务，令 且有向边参数 同理若
则 与 之间有有向边表示需求互
补关系即可组合关系，且 是 的后继任务，令 且有向边参数 其他情况
则
[0038] 所述供需匹配超网络Matching_Net中超边集合ES_T中的元素 的数值定义如下，若服务节点si，si的输入输出描述信息为，与任务节点 的输入和 输 出 描 述 信 息 为 之 间 不 可 匹 配 即则超边不存在 ，令 否则，当
时 ，其 中 有 且
则si与 之间存在可匹配超边，令
[0039] 在进行动态再调度时，受到影响的制造任务进行新的服务调用时，新调用的服务所产生的效用会存在一定的衰减。衰减程度与任务原调用的服务已执行的时间成正比，即原调用的服务已执行的时间越长，则新调用的服务执行时所产生的效用的衰减程度越大。
[0040] 本发明的优点在于：
[0041] (1)本发明提出的供需匹配超网络Matching_Net模型具有可扩展性，一方面是网络本身的规模具有可扩展性，当考虑更多环境因素和关联关系时，超网络中服务节点、任务节点以及不同网络层内的关联边、层间的超边的数量和类型都会随之增加；另一方面，超网络中的节点和边对应的属性具有可扩展性，当面向特定的供需匹配与调度等优化问题时，可以视具体情况对节点和边的相应属性赋予更加多样的意义和更加多元的赋值方式。
[0042] (2)本发明针对SoM系统的社会化应用与动态环境等特点，考虑企业服务调用时的效用和可靠性的综合值，分别建立了制造服务预调度和动态再调度的优化问题模型，为解决系统中社会化的制造任务在满足相关需求的前提下分别在什么时间段内调用哪一个制造服务的问题，提供了具体的基于超网络的制造服务动态调度方法和流程。
[0043] (3)本发明为一种能够反映制造服务与制造任务供需间的映射对应关系的供需匹配超网络模型的构建方法，以及在制造协作和服务执行过程中面对超网络模型多种动态操作时的制造服务动态调度方法。该发明能有效反映面向服务的制造系统中的动态环境，并能保证制造服务动态调度的有效性以及参与企业的较高的协作可靠性。
附图说明
[0044] 图1是基于超网络的制造服务供需匹配与动态调度方法总体流程图；
[0045] 图2是制造服务供需匹配超网络Matching_Net的构成示意图；
[0046] 图3是制造服务供需匹配超网络Matching_Net的建模流程图；
[0047] 图4是基于超网络的制造服务动态调度流程图；
[0048] 图5是制造服务供需匹配超网络模型中不同节点间各种关联边的含义；
[0049] 图6是供需匹配超网络的动态操作与物理意义。
具体实施方式
[0050] 下面结合附图对本发明作进一步详细的描述。
[0051] 如图1所示，本发明涉及的一种基于超网络的制造服务供需匹配与动态调度方法，主要包括以下步骤：
[0052] 步骤A，如图3、5所示，制造服务供需匹配超网络Matching_Net模型的构建具体包括：A1：构建制造服务网络S_Net模型。(1)将提交至SoM系统中的制造服务抽象成网络节点，将不同服务之间的各种关联关系抽象成服务节点间的边。对任意服务节点si，其每一种功能对应有一组特定的输入输出描述信息集，则服务节点si可描述为si＝。(2)判断两个服务之间是否存在功能相似关系。定义服务节点si与sj的功能相似关系判定参数为FSij＝∩。若 则认为服务节点si与sj之间为功能相似关系，令 并计算功能相似度
(3)若 则判断两个服务之间是否存在功能互补关系。定义
服务节点si与sj的功能互补关系判定参数为
若 或者 则认为
服务节点si与sj之间为功能互补关系，令 此时权重系数 表示服务节点si与sj之间的互补程度即不同服务间的可组合强度。若 则认为服务节
点si与sj之间不存在关联边，令 (4)判断所有服务节点是否都已经进行判定，若是则结束建模并输出制造服务网络模型，否则继续步骤(2)和(3)。最终制造服务网络模型S_Net可描述为S_Net＝，其中S表示的服务节点集合可被描述为S＝{s1,s2,…,si,…,sn}，ES表示的S_Net中不同服务之间的边的集合可被描述为
[0053] A2:构建制造任务网络T_Net模型。(1)将提交至SoM系统中的制造任务抽象成网络节点，将不同任务之间的各种关联关系抽象成任务节点间的边。与制造服务不同的是，SoM系统中的制造任务可分为细粒度的简单任务和粗粒度的复杂任务，复杂任务可以被再分解并可被看作是具有一定流程和时间约束的多个简单子任务的集合。在制造任务网络T_Net中，对任意简单任务节点 只有唯一的一对输入和输出描述信息因此， 可描述为 制造任务网络中的
任务可被描述为任务子图的集合，即T＝{G1,G2,…,Gp,…,Gm}。其中，若Gp是简单任务，则任务子图 且 若Gp是复杂任务，则任务子图Gp＝中的Tp表示复杂任务可分解的简单子任务集合，可被描述为 而其中的Ep表示可分解的简
单子任务之间的关联关系，可描述为 (2)判断两个任务节点是否处在同一个复杂任务子图中，若是，则两个不同任务节点 与 之间存在三种情况：①有 指向 的边，令表示 与 有功能互补关系(可组合)且定义有向边参数 ②有 指向 的
边，令 则表示 与 有功能互补关系(可组合)且定义有向边参数 即
③ 与 之间没有边，令 且 当两个不同简单任务来自不同的
复杂任务子图时，其他情况则 (3)当两个不同任务节点来自不同的任务子图时，判断两个任务之间是否具有需求相似性，若
则 与 之间有需求相似边，令 (4)否则判断两个任务之间是否具有需求互补性(可组合)，若 则 与 之间有有向
边表示功能互补关系(可组合)且 是 的前驱任务，令 且 同理若
令 且 (5)若两个
任务节点之间没有关联关系，则 (6)判断所有任务节点是否都已经进行判定，若是则结束建模并输出制造任务网络模型，否则继续步骤(2)、(3)、(4)和(5)。制造任务网络模型T_Net可描述为T_Net＝，其中T表示任务节点子图集合，即T＝{G1,G2,…,Gp,…,Gm}；而ET表示T_Net中不同任务之间的边的集合，可被描述为
表示第p个任务的第k个简单子任务与第q个任务的第l个子任务之间的关联边。
[0054] A3：构建供需匹配超网络Matching_Net模型，将每个制造服务节点与每个制造任务节点之间的可匹配关系抽象成超边。(1)判断每一个服务节点与每一个任务节点之间是否存在可匹配关系，若不可匹配(即 )，则超边不存在， 否则si与 之间可匹配(即
)，则超边存在， (2)判断所有服务节点与任务节点是否都已经进行判定，若是，则结束建模并输出供需匹配超网络Matching_Net模型；否则，继续步骤(1)。最终输出的供需匹配超网络Matching_Net模型中，S_Net与T_Net两层网络之间的超边集合可描述为表示S_Net中第i个服务si与T_Net中第q个复杂任务的第l个简单子任务
之间的可匹配关系。
[0055] 综上，如图2所示，制造服务供需匹配超网络Matching_Net模型由制造服务网络S_Net、制造任务网络T_Net以及两层网络间的超边集合ES_T三部分组成。制造服务供需匹配超网络Matching_Net模型中各个节点之间的关系如图5所示，制造服务网络S_Net内部的服务节点之间存在着两种关联关系，即服务之间的功能相似性关系，如竞争或替代关系，以及服务之间的功能互补关系，如服务间的可组合关系等。制造任务网络T_Net内部的任务节点之间存在着两种关联关系，即任务之间的需求相似性，如互补与可组合关系，和任务之间的需求互补关系(即可组合)，如串联组合关系中的前序与后续约束，此外还有并联可组合关系中的并发约束等。两层网络之间服务节点与任务节点之间的关联关系时服务与任务之间的可匹配关系，即某服务可执行某任务的可能性。
[0056] 步骤B，如图4所示，在任务被实际执行之前，根据面向不确定任务(任务需求的可执行时间区间确定，但实际执行时间区间不确定)的制造服务预调度的目标函数，进行初始时刻(t＝0)的制造服务预调度，具体步骤包括：
[0057] B1：提取Matching_Net模型中各个任务节点对应的超边集合，即各个任务节点对应的可选服务的集合，描述为
[0058] B2：提取各个超边对应的可靠性、效用等属性参数。效用值综合考虑成本、能耗、风险和完成时间四个指标，可靠性考虑服务执行任务时发生故障的概率。假设决策系数为
，其中aip＝1表示调用服务si来执行任务tp且在aip_starttime时刻开始执行。在服务si执行任务tp时会以概率 发生故障，服务si执行任务tp所产生的效用值为超网络Matching_Net中所有服务的总数为NoS,所有任务的总数为NoT,所有企业用户的 总 数为 N oE ，任 一企 业 用 户en p所 拥有 的 制造 服务 集合 可 表示 为预调度的目标函数综合考虑系统中服务调用的平均效用和平均可靠性，可被描述为 其中，
wr和wu分别表示服务调用的可靠性和效用的权重。
[0059] B3：执行制造服务预调度，得到当前最优执行方案。
[0060] 步骤C：如图4所示,将制造服务动态调度的时间按单位时间单元(Δt)进行等距连续划分，从t＝1时刻起，每隔一个单位时间单元周期性地执行动态环境生成模块从而得到超网络更新模型，具体步骤包括：
[0061] C1：每间隔一个单位时间单元Δt，具体单位时间单元可视具体情况调整)进入新的时间单元时，在当前时间单元内超网络模型以一定的概率发生动态操作。超网络模型发生的动态操作和物理意义如图6所示。动态操作举例：如当新增服务加入到SoM系统中时，创建新增服务节点并添加到服务网络S_Net中，并根据其与其他服务的关联关系添加新边，根据其与任务的关联关系添加超边。同理，当新任务到达后，新增任务节点并添加相应的新边和超边。另外，在动态执行过程中，若服务节点sk发生故障，则删除掉服务节点sk及其所关联的超边；若超边 发生故障，则只删除该超边。当删除的服务节点恢复功能时，恢复该服务节点及其所有关联的超边。当删除的超边恢复时，则需在相应的服务节点可被正常调用的前提下恢复该超边。
[0062] C2：进入下一时间单元即触发下一时刻，t＝t+1，判断在前一时间单元内是否发生动态操作。若发生，则更新超网络模型并进入步骤D，否则继续执行当前方案直至进入下一时间单元或者判断若满足终止条件则结束；
[0063] 步骤D：如图4所示,若超网络发生变化则执行动态调度判断，否则进入下一时间单元或者判断若满足终止条件则结束，具体步骤包括：
[0064] D1：若在前一时间单元内发生了动态操作，判断更新后的超网络模型是否破坏了当前的调度方案。当前一时间单元的调度方案中被调用的服务节点sk或者该服务节点所对应的可匹配超边 发生故障，则认为制造服务调度方案遭到破坏。若影响了当前调度方案则进入下一步D2，否则继续执行当前方案直至进入下一时间单元或者判断若满足终止条件则结束；
[0065] D2：判断更新后的超网络模型是否破坏了当前制造任务节点所对应的超边集合。若不影响直接进入步骤E执行动态再调度，否则进入下一步D3；
[0066] D3：更新当前制造任务节点所对应的超边集合，然后再进入步骤E执行动态再调度。
[0067] 步骤E，如图4所示，具体包括步骤：
[0068] E1：提取更新后的Matching_Net模型中各个任务节点对应的超边集合，并提取各个超边对应的可靠性与效用等属性值。
[0069] E2：受到影响的制造任务重新调用新的服务时，所产生的效用存在一定的衰减。衰减程度与任务ti原调用的服务已执行的时间成正比，即原调用的服务已执行的时间越长，则调用新的服务时所产生的效 用的衰减程度越大。衰减系数可描述为其中 为原调用
的服务si执行完成任务tp所需的时间。
[0070] E3：判断当前调度方案是否可进行局部修复。若可局部修复则基于当前调度方案进行局部再调度，具体步骤如下：①首先筛选出当前由于动态操作而受到影响的制造任务ti，即所有被删除的可匹配超边所对应的任务；②根据效用衰减的修正评估公式对受到影响的任务ti所对应的所有可选的服务sl进行排序；③依次判断服务sl是否满足再调度要求，若满足则调用服务sl作为服务sk的替补服务。一旦某个制造任务ti对应的所有可选服务均被判定为无法满足局部再调度时，执行制造服务全局再调度，即将当前时刻作为新的初始时刻，根据效用衰减修正后的目标函数进行重新的制造服务调度优化。动态再调度完成后，新的调度方案生成，进入下一时刻，执行步骤C。
