基于科学工作流的组织层级比较分析

杨旭超

摘要： 基于一个专门程序环境的科学工作流，对组织层级的比较分析进行了研究。结合科学工作流在S-P树变换与测度中的运用，为组织层级的比较分析提供了系统科学的处理办法：通过对不同组织层级之间的最小变换进行测度，为组织变革的代价提供一定程度的参考。

关键词： 科学工作流； S-P树； 变换与测度； 组织层级

中图分类号：G301文献标志码:A文章编号：1006-8228（2012）03-28-03

Comparison analysis of organization levels based on scientific workflow

Yang Xuchao1，2

（1. HangZhou DianZi University HangZhou ZheJiang 310018， China； 2. ZheJiang Technology Institute of Economy）

Abstract： The author studies in this paper scientific workflows based on a specific program of environment, and provides a more convenient and effective method to solve practical problems in operation research and computer sciences. Combining the application of scientific workflows in transformation and measurement of S-P tree, the author presents a systematic and scientific method to comparison analysis of organizational levels. It provides in some sense a reference for organizational reforming cost analysis through measuring the minimal transformation between various organization levels.

Key words： scientific workflow; S-P tree; transformation and measurement; organization levels

1 科学工作流概述

信息时代的特征是，知识信息与科研数据呈指数级增长，科学实验规模越来越大，基于虚拟环境下的科学研究方法日益复杂。在计算机技术与网络技术深入发展和广泛应用的今天，科学家往往需要使用许许多多的应用程序对大量的原始数据或中间数据进行研究分析，需要频繁地对海量数据进行操作处理。

科学工作流(Scientific Workflow, SWF)提供了一个专门的程序环境，以减少科研人员中进行研究的投入[1]。因此，科学工作流已成为在网络基础设施上进行大规模科学计算和协同研究的有效方法。

科学工作流的研究主要围绕科学计算、网格等展开[2]，内容涉及科学工作流在具体应用环境中的解决方案，科学工作流的建模，来源管理，系统可视化，语言，数据流控制[2]以及科学工作流管理系统( Scientific Workflow Management Systems，SWFMS)[5]的开发和优化等几个方面。

科学工作流管理系统提供了一个科学计算流程定义和自动运行的管理平台[5]。通过定义各个活动调用资源，在活动之间建立数据流关系和控制流关系，借助该平台可以完成特定的科学计算问题。

作为一种辅助科学家进行科学实验的手段, 科学工作流管理系统是对多领域或专门领域科学工作流进行管理的系统，涉及到多任务协调执行的活动，旨在定义、执行并监控整个活动过程，解决领域应用的具体问题及优化以往的研究成果，为促进和保障虚拟知识环境下的科研协作提供一种解决方案[2]。

科学工作流管理系统应具有有以下主要特点：

⑴ 具有计算集成、分析集成、数据集成、应用集成与大规模并行化等特点。可以组合不同领域的复杂应用程序，按照一定的规则在分布式计算资源上对海量数据进行查找、移动、分析、处理、存储、 仿真以及可视化操作[5]。

⑵ 适应应用的分布式和异构性[3]。科学计算中问题求解过程可能涉到不同系统之间的协作，而系统之间是分布式的，系统构架很难统一，加大了应用集成的难度。Web服务[8]对这类应用的封装可以有效解决这方面的问题，但封装过程通常比较复杂。

⑶ 适应各种应用的特殊性、易用性和灵活性[3]。科学计算中常常涉及大量的数据计算，且计算资源难以提供统一接口，随着应用类型的增加，用户需要不断熟悉各类应用集成和使用方法，某些应用要有较高的执行性能。

⑷ 适应应用间数据格式的差异性[3]。应用有不同格式的输入/输出，为了保证数据流在不同应用间的正确传递，用户需要花费大量精力开发数据格式的转换代码。

显见，科学工作流系统的特点是面向数据流，侧重高度密集的数据计算、分析与处理[3], 而且应用集成是科学工作流系统的一个显著特征。本文结合S-P树的科学工作流作变换分析，根据对科学工作流变换的适当测度，可以反映不同科学工作流之间的差距，为科学工作流的程序化实现提供了可能，从而解决一些科学工作流的最小变换代价问题。

2 科学工作流的变换与测度

将典型的S-P树变换成注释的S-P树如图1所示可以方便科学工作流之间的变换[6]。

图1科学工作流的变换

具体看一个组织的管理层级变换过程以→∧表示删除枝叶，∧→表示添加枝叶，则管理层级T1变换到T2的过程可以描述为：

⑴

图2T1组织层级

图3T2组织层级

对Ｓ-Ｐ图有以下几类基本的操作。

序列操作（用Ｓ表示）：子集的序列合成。

平行操作（用Ｐ表示）：平行操作包括了平行层面的一支或两支结点的所有的并集操作。

叉操作（用Ｆ表示）：叉操作要求结点下有一个或多个子结点，并对子结点进行平行处理。首先在叉点（数据源处），将数据分离，再在校准点处接合，以平行生成一个或多个子集。子集当中可以存在差异。

对于平行操作，记M为初始状态T1和最终状态T2之间的过渡匹配变量，M中的一对结点（v1，v2）如果满足以下两个条件，就称做不稳定匹配：

条件1：（v1，v2）是一对P结点；条件2：v1、v2都只有一个子结点，这对子节点同类且未被M所匹配。

相对应的，不稳定匹配的对立面就是稳定匹配。

给出一个来自T1与T2之间良好匹配的M，以及M中的一对子节点（v1，v2），使得M（v1，v2）成为T1[v1]到T2[v2]的相应匹配，我们可以将匹配消耗γ（M（v1，v2））作如下定义：

如果（v1，v2）稳定匹配，则有：

⑵

如果（v1，v2）不稳定匹配，则有：

⑶

上列各式中，c1、c2分别是v1、v2的子集，I1、I2分别是M在T1与T2之间的匹配结点集，XT(c)表示删除子枝T[c]的最小消耗，是删除h(v1)子枝的最小消耗，其中h(v1)的子枝不同于T[c]的子枝h(c1)。

3 不同组织层级的比较分析

3.1 组织层级概述

由于组织管理的需要，组织层级化成为组织管理的必然趋势。组织层级化是指组织在纵向结构设计中需要确定层级数目和有效的管理幅度，根据组织集权化的程度，规定纵向各层级之间的权责关系，最终使组织具有一个能够对内外环境要求做出动态反应的有效结构。

由于组织任务存在递减性，从最高层的直接主管到最低的基层具体工作人员之间就形成了一定的层次，这种层次便称为组织层级[7]。

3.2 程序设计

程序设计思路如下：

以M*（v1，v2）变量作为T1[v1]与T2[v2]之间的最小消耗匹配变量，s为计数器。

如果v1与v2完全相等，返回M*（v1，v2）的值，不作相应处理；反之，不作处理，进入下一阶段循环。如果v1与v2均为序列结点，将v1、v2的子结点序列合成结果M*（c1，c2）添加到M*（v1，v2）内，计数器进行计数，反之，不处理，进入下一阶段循环。如果v1与v2均为平行结点，分两种情况处理：

情形一：如果v1、v2均有一个结点c1、c2,选择满足⑷式的M*（c1，c2）返回M*（v1，v2）内，计数器进行计数，以达到最小消耗，反之，按情形二处理；

⑷

情形二：进行的选择，并将M*（c1，c2）返回M*（v1，v2）内，计数器进行计数，反之，进入下一阶段循环。

如果v1与v2均为叉结点，对M*（c1，c2）进行最小适配处理，将M*（c1，c2）返回M*（v1，v2）内，计数器进行计数。最后返回程序结果。

设计测度程序如下：

AlgorithmEdit-Distance-on-Trees

Input: T1[v1] and T2[v2] such that h(v1) =h(v2)

Output: M*（v1，v2）: the minimum-cost well-formed mapping

from T1[v1] toT2[v2] and s

1: add（v1，v2） to M*（v1，v2）

2:s=0

3: ifthen

4: return M*（v1，v2）

5: end if

6: if then

7: for each pair of children （c1，c2） of v1 and v2 do

8: add M*（c1，c2） to M*（v1，v2） and s=s+1

9: end for

10: end if

11: ifthen

12: if both v1 and v2 have only one child, say c1 and c2,

andthen

13: ifthen

14: add M*（c1，c2） to M*（v1，v2） and s=s+1

15: end if

16: else

17: for each pair of children （c1，c2） of v1 and v2 such

thatanddo

18: add M*（c1，c2） to M*（v1，v2） and s=s+1

19: end for

20: end if

21: end if

22: ifthen

23: B*:=the minimum-cost bipartite matching

24: for each pair of children （c1，c2） of v1 and v2 such that

do

25: add M*（c1，c2） to M*（v1，v2） and s=s+1

26: end for

27: end if

28: return M*（v1，v2） and s

利用返回M*（v1，v2）值与s可以得到不同管理层级之间的最小变换代价以及变换的最小次数。进一步地，通过M*（c1，c2）值与s大小，我们也可以得到不同管理层级之间的最小变换成本，可为组织变革的代价提供一定程度的参考。

参考文献：

[1] Taylor I J, Deelman E, Gannon D B. Workflows for E-Science[M].

New York: Springer, 2007.

[2] 苏明明.2007-2008年国外科学工作流研究进展[J]. 国外研究进展_

图书馆建设,2009.7:96~100

[3] 汪春杰.面向科学工作流的应用集成框架[J].计算机工程,2009.10:

258~263

[4] 罗海滨.工作流技术综述[J].软件学报,2000.11:899~907

[5] 张卫民.科学工作流技术研究综述[J].国防科技大学学报,2011.6:

56~65

[6] Zhuowei Bao、Sarah Cohen-Boulakia、Susan B.Davidson、Anat

Eyal、Sanjeev Khanna.Differencing.Provenance in Scientific Workflows[J]. IEEE International Conference on Data Engineering,2009:808~815

[7] 周三多.管理学[M].高等教育出版社,2005.