چارچوب ساده شده برای شبکه های جریان کار استوکستیک

This paper presents a novel method to simplify stochastic workflow networks for their performance analysis under a unified computable framework. This method is based on two techniques: (1) module simplification, and (2) PH equivalence and PH approximation. In the first technique, simplified procedures for at least four crucial modules: sequential routing, parallel routing, selective routing and iterative routing are given, respectively; while in the second technique, the closure properties and the two-order approximation for the PH distributions are discussed. Using this method, we analyze several examples for the stochastic workflow networks and illustrate that performance evaluation of complicated stochastic workflow networks can be obtained by means of subsystems which are clearly constructed by some of the four structured modules. Numerical examples indicate that the method of this paper can tackle large-scale and complicated stochastic workflow networks with both effective approximation and low computational complexity.

During the last three decades considerable attention has been paid to studying workflow. Workflow is an effort to automate and redesign the way that an organization tries to increase efficiency, reduce cost and create competitive advantages. Since the late 1980s, not only has workflow become a useful technology, but also it has been motivated by many practical applications including computer supported cooperative work (CSCW) systems, information systems, electronic commerce, manufacturing systems and communication networks. Hollingsworth [1] explained workflow as computerized facilitation or automation of a business process. Based on his interpretation, a large number of workflow products were developed such as FlowMark, MQSeries, FloWare, Action Workflow, Staffware, OPEN/workflow, InConcert, Visual Workflo and Lotus Notes (see, e.g. [2]). Also, some organizations made workflow management systems (WFMSs), which provide the ability to specify, execute, register and dynamically control such workflows. According to the workflow products and the WFMSs, some useful workflow patterns were abstracted, e.g., see [3]. Gamma et al. [4] catalogued 23 design patterns, which describe the smallest recurring interactions in object-oriented systems. It is worthwhile to note that several patterns constitute a basic routing, which always can be found in each workflow product. Besides, other patterns may be referred to as more advanced routings, which are difficult to be supported by workflow products. van der Aalst and van Hee [5] indicated that a workflow routing defines the order of performed tasks, and identified four basic routings including sequence, parallelism, choice and iteration. Kumar and Zhao [6] studied the dynamic routing of the WFMSs. Lin et al. [7] provided an exponential approximation for simplifying the four basic routings by using stochastic Petri nets (SPNs). Workflow should be well cared for its representation, reasoning and execution. Trajcevski et al. [8] addressed the requirements of workflow specification. Useful specification languages have been proposed, for example, Opera Graphical Workflow Language (OGWL) by [9], State and Activity Charts by [10], Concurrent Transaction Logic (CTR) by [11], Transaction Datalog (TD) by [12] and Yet Another Workflow Language (YAWL) by [13]. Based on the 23 design patterns given by Gamma et al. [4], van der Aalst and ter Hofstede [14] recognized considerable differences in the expressive power of some workflow specification languages, and indicated that those languages can perform better to support the workflow patterns by using Petri nets (PNs). For a comprehensive introduction of PNs, readers may refer to a survey by [15] and a book by [16]. Reijers [17] reviewed workflow modeling and crucial techniques. Miller et al. [18] discussed simulation technology of workflow. van der Aalst [19] introduced PNs based analysis techniques for modeling checking of workflow. Adam et al. [20] concentrated on temporal logic analysis of workflow. A PN based language for workflow modeling, called Workflow net (WF-net), has attracted considerable interests. van der Aalst [21] showed two assumptions of a WF-net: (1) there is one input place and one output place, and (2) for each node there exists a directed path from the input place to the node and another directed path from the node to the output place, where the node is either a transition or a place. Except for the above two assumptions, he also indicated that the soundness should be needed. The soundness ensures that the process can terminate eventually, upon termination there is a single token in the output place while all the other places are empty, and more crucially, there should be no dead tasks. Dehnert and Rittgen [22] proposed the relaxed soundness. Ludwig and Whittingham [23] and van Glabbeek and Stork [24] illustrated the importance and necessity of inter-organizational workflows, which consist of several cooperative organizations. To support inter-organizational workflow management, a specific research project, called CrossFlow, was started in 1989. Grefen et al. [25] gave an overview for the CrossFlow project. Subsequent papers have been published on modeling and verification of inter-organizational workflows, among which see van der Aalst [26], Yan and Wang [27], and Meng et al. [28]. Few methods were available to evaluate performance measures of the inter-organizational workflows. One of the major challenges results from the study of complicated stochastic systems, performance evaluation of which in general is intractable by means of ordinary Markovian analytic methods. To overcome difficulty due to a large state space of a Markov chain, simplification methods are always needed and have been proposed by some researchers, for example, state truncation by [29] and [30], state aggregation by [31], [32] and [33], time scale decomposition by [34], [35] and [36], fix-point iteration strategy by [37] and [38], and hierarchical decomposition by [39], [40] and [41]. In this paper, we extend the inter-organizational workflow to a more general model: Stochastic workflow network, and then propose a novel method for computing performance measures of a stochastic workflow network under a unified approximate framework. This method consists of two steps: (1) using four crucial modules to simplify a more complicated network into a simple system, and (2) computing performance measures of the simple system, which are an effective approximation of these performance measures of the corresponding original network. Also, we show that such an approximation is more appropriate in the performance analysis of complicated stochastic workflow networks from a clear subsystem structure. The main contributions of this paper are twofold. The first one is to provide four crucial modules, each of which can be simplified as one node of a workflow network under an equivalent setting of the PH distributions. For a comprehensive introduction of the PH distributions, readers may refer to a book [42] by Neuts. We believe that there must still exist other crucial modules with respect to simplification of complicated stochastic workflow networks, and the other modules can be similarly analyzed by the method for the four crucial modules proposed in this paper. Many practical examples indicate that a complicated stochastic workflow network in general can be decomposed into several key subsystems, thus such a decomposition technique is an important direction in the study of stochastic workflow networks. Specifically, the idea of subsystem decomposition has recently been developed by such as Stochastic Process Algebras (SPAs), e.g., see [43]. In SPAs, the four crucial modules can be regarded as basic operational elements. Each of these basic elements can be reduced by means of a lower-order PH distribution with a better approximation. Note that the PH approximation is able to widen the application fields of the SPAs. Therefore, the study of the four crucial modules becomes fundamental to our simplification techniques. The second contribution of this paper is to construct a simplification framework to deal with complicated stochastic workflow networks. This framework depends on the module based simplification with respect to all the key subsystems involved. Note that the PH distributions play an important role in the simplification framework, for example, the two-order PH distribution is frequently used in the simplification procedure, which makes the computational complexity low and the systemic structure simple. Therefore, the simplification method can be used to analyze large-scale and complicated systems more effectively than those in the literature. Some numerical examples indicate that the implementations of the simplification framework are convenient and efficient for stochastic workflow networks. It is worthwhile to note that Scarpa and Bobbio [44] applied PH distributions to SPNs and made an effort to reduce computer storage requirements via Kronecker algebra operators, but they do not consider structure simplification which can reduce computation complexity more effectively. He, Wu and Li [45] studied a longer production line by using the PH approximate method, the idea of which is further developed in this paper. The remainder of this paper is organized as follows. Section 2 describes a stochastic workflow network, and also provides three simple and practical examples for a necessary interpretation. Section 3 analyzes four crucial modules and simplifies them under an equivalent or approximate setting based on the PH distributions. Section 4 presents a simplification framework in order to compute the performance measures of complicated stochastic workflow networks. Section 5 gives some numerical examples to indicate implementations of the simplification framework. The final section provides some concluding remarks.

In this paper, a novel simplified framework is proposed for studying complicated stochastic workflow networks. For four crucial modules: sequential routing, parallel routing, selective routing and iterative routing, we discuss their two-order PH equivalence and approximation under keeping the same first three moments. Numerical implementations indicate that this method is effective for dealing with complicated stochastic workflow networks. Unlike the ordinary methods suffering from rapid explosion of the state space, this method can simplify a stochastic workflow network into a simpler model module by module. As such, the solving structure of a complicated stochastic workflow network can be controlled within an allowable and tractable range. It is worth mentioning that this method can be expanded to arbitrary SPNs as long as we can recognize these basical modules. As indicated in Li, Wang and Zhou [49] and Li [50], there are still a number of directions for potential future research, for example, (1) providing other key modules, such as advanced synchronization patterns and cancelation patterns, and giving the corresponding simplifications, (2) providing more effective algorithms with computational complexity analysis for stochastic workflow networks, and (3) applying the simplified computation for performance evaluation of stochastic workflow networks to some practical areas such as finance, business, communication networks and manufacturing systems.