رویکرد عامل گرا برای برنامه ریزی در جابجایی سیستم های جریان کاری و پردازش پارتیشن

Mobile agents act as the task executors in migrating workflow system. As the size of workflow is increased by including many tasks and branches, multiple mobile agents should be used where each agent is responsible for a branch of the workflow process and fulfills the workflow goal by cooperating with its partners. In this case, the workflow process needs to be partitioned into a set of sub-processes before execution so that each sub-process can be assigned to one mobile agent. This paper proposes a structured process partition approach that includes process structure partition and Quality of Service(QoS) objective partition. The former partitions a structured process into a set of sub-processes with dominant relations and each sub-process consists of a sequence of tasks. The latter distributes QoS objectives, such as the expected budget or deadline of the whole workflow, over all of the sub-processes. In addition, a sub-process execution planning algorithm with QoS objective based on Markov Decision Process (MDP) is also put forward in this paper. The experiment results show that the effects of workflow partition method and MDP based process planning method are sound.

By definition of Workflow Management Coalition (WfMC), workflow is an automation of a business process, in whole or parts, where documents, information or tasks are passed from one participant to another to be processed, according to a set of procedural rules (Workflow Management Coalition, 1999). The migrating workflow is a new model for workflow management by adopting mobile agent technology (Cichocki and Rusinkiewicz, 2004), in which the mobile agent migrates from one site of network to another in order to achieve workflow goal by using site services. The behavior of mobile agent in the migrating workflow model is similar to people working in moving manner, such as buyers move from shop to shop, information searchers move from library to library, etc. Traditionally, the workflow management system is constructed with one or more centralized workflow engines and relied on remote procedure call (RPC) principle (Workflow Management Coalition, 1999). However, the RPC depends on the reliability of network connection and lacks the adaptability to network environment. The mobile agent computing paradigm changes RPC to local procedure call (LPC), that is, a mobile agent moves among sites of network and utilizes the local services to achieve its goal. Except for moving time, a mobile agent does not require any reliability of network connection and can alternate its workplace when the expected site is down or expected service is changed. Therefore, adopting mobile agent technology can bring more flexibility to workflow management. Like many applications of mobile agent technology (Loke and Zaslavsky, 2001, Foster et al., 1999, Merz et al., 1997 and Meng et al., 2000), in the migrating workflow system, the whole process of workflow can be executed by a single mobile agent. But when the size of workflow is increased, i.e., comprising many tasks and branches, the workflow completion time will be prolonged because all of the parallel tasks have to be executed serially by one mobile agent. In such a case, multiple mobile agent mechanism should be adopted to support execution of parallel tasks in order to improve the workflow system performance (Feng et al., 2007). In such workflow systems, each mobile agent will be responsible for a part of workflow process and fulfill the workflow goal by cooperating with its partners. To this end, the workflow process needs to be partitioned into a set of sub-processes before execution so that each sub-process can be assigned to a mobile agent. As indicated in the literature (Tan and Fan, 2007), process partition is a primary step for distributed workflow management model and some methods have been obtained so far. We will introduce these approaches as the related works in Section 6. Considering the decentralized, loosely coupled and autonomous nature of mobile agent computing paradigm, the mechanism of process partition for migrating workflow is quite different from those methods appropriate for the WfMC model. First, there is no central workflow engine to coordinate the workflow services and mobile agents in a migrating workflow system. Instead, the dominant relations among mobile agents, such as synchronization of tasks and coordination of service conflicts, have to be handled by the mobile agents themselves. This must be taken into account in the workflow partition. Second, the looped task and logical or-relative tasks, e.g., or-Split and or-Join need not be considered, because a looped task can be executed by one mobile agent in the same workplace, it does not require mobile agent moving; a group of logical or-relative tasks can be treated as a single task with redundancy and left choice to mobile agent. In other words, the migrating workflow partition method must be mobile agent oriented. Finally, QoS objective is also a major aspect to evaluate the performance of workflow applications. Since the price and time of service may be different among service sites even if they provide same services, thus execution time and cost are usually the main constraints to be considered. Based on above considerations, this paper proposes an agent-oriented workflow partition approach that partitions the workflow process into a set of sub-processes; each of them consists of a sequence of tasks and will be mapped into a mobile agent. We denote the dominant relations among sub-processes as a tree structure, where nodes represent sub-processes, and upper sub-processes dominate the lower ones in cooperative semantics. After sub-processes are assigned to mobile agents, the dominant relations among the sub-processes will become the cooperative relations among the mobile agents. Based on the structure partition tree, we present two kinds of QoS objective partition method named as minimal cost within a deadline (MCD) and minimal time with a budget (MTB). Due to the sequential structure of sub-processes, a task execution planning method is also proposed by modeling the sequential sub-process as a Markov Decision Process (MDP). The working path for a mobile agent is constructed based on the MDP sub-process planning with QoS objective. The remainder of this paper is organized as follows. Section 2 gives an overview of migrating workflow framework. The workflow process partition approach and planning methods are detailed in 3 and 4, respectively. Section 5 illustrates the experimental results. In Section 6, we introduce the related works and make some discussion. Section 7 concludes the paper and gives the directions for future work.

As we stressed before, our work is aimed to partition the structured workflow with QoS constraints into a set of sub-processes with dominant relation so that the sub-processes can be executed by the MIs in cooperative way. Although there are still many non-structured workflow applications, structured workflow is proved to be superior in supporting flexible and dynamic workflow definition because it greatly simplifies the complexity of workflow structure validation (Hauser et al., 2006). Additionally, structured workflow is also the most type used in practices, such as administrative workflow and production workflow applications. The main contributions of this paper are as follows. (1) The DAG-based workflow partition method for migrating workflow management is proposed. The method is combined process structure partition with QoS constraints partition. The former partitions the whole workflow into a set of sub-processes and each sub-process consists of a sequence of tasks, and the latter distributes the workflow QoS objective over all of sub-processes according to the expected execution time or payment; (2) The concept of partition tree is put forward. Deferent from the spanning tree of the DAG, the partition tree is constructed with partitioned sub-processes and dominant relations among them. The partition tree is useful to perform the QoS constraints on sub-processes and coordinate the service conflict between MIs; (3) The MDP-based sub-process planning method with the MCD or MTB objective is given. The results of simulated experiments show that the feasibility and effectiveness of our partition and planning methods. To make the migrating workflow management more flexible, in the near future, we will further enhance our research to process dynamic partition and QoS constrained planning approach. Additionally, we will pay attention to the unstructured and dynamically-defined workflow partition and execution planning.