基于串归约的网格工作流费用优化方法

针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明: BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD.     

有向无环图的高效归约算法

将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行。该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程。而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题。为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同。提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点。新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级。还提出了一种并行化的算法思想来加速可归约子图的搜索过程。     

基于数据归约的模型设计

讨论了模型管理系统设计中模型表示方法、模型操作的实现方法、模型执行的具体过程.提出了一个模型表示的形式化方法,通过可量化、可陈述化、可公式化描述使得模型表示与基于规则逻辑的数据表示、基于归约的推理过程相兼容.使用推理机制,作为模型处理的基础,提高了模型实例化的有效性.     

基于SAT工具的限界模型检测归约方法

限界模型检测主要对路径上的属性进行检测,基于此给出一种编码方法,将LTL公式在路径上展开,从而将限界模型检测转换为命题逻辑的可满足性问题,使用SAT求解工具来完成模型检测过程。阐述归约过程的正确性与完全性,通过一个具体例子证明了该方法的有效性。     

基于有向生成图的需求验证方法

软件工程中的需求具有抽象性和复杂性,未经验证的需求会给项目带来较大需求风险。该文提出一种基于有向生成图的需求验证方法,论述UML对话图建模和模型映射规则、任务分解策略和形式化描述,以及需求验证过程涉及的转化模型和算法。该方法有效克服了需求验证过程中的复杂性和经验操作。从理论上分析该方法的可用性,通过实例验证了该方法的有效性。     

基于图归约法的工作流模型验证

详细论述了对基于有向有环图（DCG图）的工作流模型结构正确性进行验证的图归约法及其五种归约规则，根据这些规则即可判定工作流模型中存在的结构冲突，从而迅速对其进行修正。     

基于拓扑序列归约的Web服务组合QoS度量算法

考虑有向无环图 (DAG)描述的组合服务模型,提出了一种新的组合服务QoS度量方法--基于拓扑序列归约的Web服务QoS度量方法（QCMTSR）。其借鉴迭代归约度量方法中的基本结构及QoS计算公式,定义了DAG图中的两类基本结构,串归约结构和并归约结构,并给出了两种基本结构的QoS属性计算公式;通过逐步归约DAG图拓扑序列中的每个节点,直至最后一个节点的QoS属性值就是组合服务的各QoS属性的度量结果。从理论上证明了QCMTSR算法适用于所有DAG描述的组合服务,并实验证明QCMTSR算法对可靠性和可用性能够更准确的度量。     

基于Pi-演算的扩展有向图工作流模型及验证

为了加强工作流模型对业务流程的描述能力,提出了一种扩展有向图工作流模型及其验证方法.针对基于有向图工作流模型的不足,提出了扩展有向图工作流模型,并给出了该模型的定义和图形符号描述.在用Pi-演算准确描述扩展有向图工作流模型的基础上,给出了用Pi-演算分析和验证扩展有向图工作流模型正确性的方法.最后,结合实验对扩展有向图工作流模型及验证方法进行了仔细分析,实验结果表明了该工作流模型及验证方法的有效性和正确性.     

一种过程定义模型及其验证性分析

软件过程是管理、开发、维护软件系统所需要的一系列活动的偏序集合。软件过程作为一种工作流,其建模和分析可以采用工作流的理论和技术作为支撑。因为任务控制流的图示表示办法直观方便,因此大多系统都采用这种定义方式为软件过程建模。而过程定义的合理性验证问题复杂度通常是非常高的,必须寻求合理的算法。图规约算法就是一种实际可行的算法。     

基于Petri网的工作流模型合理性验证

工作流管理系统具有实时性、同步和异步操作等特点,其建模方法是成功实施工作流管理的关键,而工作流模型应该完整地支持工作流定义的概念,正确、高效地反应企业的经营组织过程,为确保工作流的正确运行,必须对工作流模型的合理性进行分析和研究,因此工作流的模型分析和优化成为工作流研究的一个重点[7]。该文从各种研究资料出发,利用工作流模型的合理性定义,给出基于Petri网的工作流模型的验证步骤和方法。     

一种基于Petri网化简的工作流过程语义验证方法

过程验证是保证工作流过程定义正确性的重要手段.针对过程定义中控制流、数据流和资源三维元信息相结合的冲突检测问题,研究了过程的语义验证方法.首先根据语义验证的需求,定义3DWFN网作为过程描述的形式化模型,然后基于该模型阐述了完成语义验证的化简规则.并通过与其他相关化简规则的比较,说明了这些规则在语义验证层面的优势.     

基于P/T系统化简方法的工作流过程模型验证

目前工作流技术在管理、生产和科学研究等领域中已经被广泛应用.由于过程逻辑的复杂性和变化性等原因,如何建立良构的业务过程是一个比较现实的问题.因此,对过程模型进行分析和优化成为工作流技术的研究方向之一.首先,根据改进的工作流过程元模型,研究并提出了一种基于P/T系统的工作流过程模型过程网.基于过程网给出了一组化简规则,用于验证过程模型中的死锁和乏同步两种结构冲突.最后,结合一个业务过程实例,根据转换规则把它映射为过程网,应用规则进行化简并得到验证结果.     

工作流过程建模中的形式化验证技术

工作流过程建模是一个复杂且易错的过程.若过程定义在投入运行之后被发现有错,则修复错误的代价相当高,这个问题引起了研究界和工业界的高度重视.因此,在建模阶段进行有效的过程验证是十分必要的.综述了工作流过程验证技术的发展现状,包括强调验证的重要性,叙述了需要验证的问题和复杂度;介绍了对验证方法的要求;讨论了过程合理性验证和化简验证技术等;并通过对研究现状的分析和对比,提出了仍然没有解决的问题和将来的工作.     

面向业务流程的数据模型异常检测方法

当前,流程驱动的信息系统构建方式得到了越来越广泛的应用.在流程驱动的方式中,流程模型对数据模型有着不可忽视的影响.但是当前的数据模型异常检测方法都是针对数据模型本身的特点而未考虑流程模型.同样,流程模型的验证方法也缺乏对数据模型的考虑.文中提出并分析了面向业务流程的数据模型的异常问题,并给出了其3种基本类型.为了检测这些异常,文中提出了Data-process Graph(DP-Graph)模型,将数据模型和流程模型放在统一的架构下进行研究.而后,基于DP-Graph,文中提出了DPGT算法,有效地实现了面向业务流程的数据模型异常检测.文章中的实验结果验证了DPGT算法对于这些异常的高检出率.     

时态工作流过程模型及其合理性验证

为了提高工作流产品对信息时效性的处理能力,通过将时间维引入工作流概念空间,对构成工作流的基本概念及概念间的关系进行了全面的时间属性扩展,提出了时态工作流的概念.在前期对时态信息表示及演算、时态工作流元模型研究的基础上,提出了一种能够综合描述过程、资源、案例、时间四维信息的时态工作流过程模型TPWF-net,并证明了TPWF-net与WF-net的结构等价性、自由选择同步TPWF-net和良构TPWF-net的合理性可以在多项式时间内判定等结论.在此理论的指导下,提出了结构化建模的思想,并阐述了基于结构化简的TPWF-net模型合理性验证的方法.时态工作流能够更加全面地描述和分析工作流领域的时间相关问题,开发的一个时态工作流引擎原型已在一些应用研究性项目中得到了验证.     

产品开发过程中的数据流建模与分析

通过分析产品开发过程管理中各种数据的特征,指出数据流建模和分析在面向产品开发过程的工作流管理系统中格外重要.基于提出的工作流模型,开发了一种面向版本控制的数据流模型,它支持包含任意环的过程结构.引入变量影响列表描述这种数据流模型并给出该模型正确性分析的方法.能够适应面向产品开发过程的工作流管理系统中数据管理的需求.     

一种多学科设计优化工作流验证方法

在多学科设计优化集成系统中,设计过程和优化求解算法均通过可视化工作流实现,工作流有效性验证对提高设计效率和提高系统的用户体验具有重要意义。当前验证方法主要针对办公自动和企业管理系统中的工作流验证问题,多学科设计优化集成系统中的工作流验证问题研究较少。在分析前期工作验证技术的基础上,针对以循环结构为特征的优化环,提出一种基于图论方法的,名为浓缩环(concentration-loop)的验证算法。结合发射平台数字化设计系统的设计与实现,对该算法进行了验证。