A Routing-Based Dynamic Workflow

INTRODUCTION

Workflow technology has been deployed and well accepted in a great diversity of environments such as software engineering, health care, finance, production, office automation and banking (Bradbury et al., 2004; Zhu et al., 2004). But there are so many uncertain factors in enterprise business processes that workflow processes become uncertain. Traditional workflow management systems can not adapt the variability of real business processes; even can not adjust themselves in time according to the changes of activities because of shortage of flexibility. And existing dynamic workflow mechanisms can not allow the business processes to achieve the most optimized. In order to make some adjustments it is necessary to introduce new technology into the existing dynamic workflow management systems.

In recent years, agent has become more important in the field of artificial intelligence and computer science, because of its self-adaptability, autonomy, interoperability and traceability, etc. (Long et al., 2009). If these characterizes of agent can be made good use and applied to the workflow management systems, then activities in the workflow management systems can collaborate with each other, so the current workflow management will be optimized. At the same time, a set of data can be delivered to the destination safely, reliably and speedy because routing algorithm is introduced into the internet. If a routing algorithm can be made good use in the workflow management systems, the workflow processes will be optimized.

In order to improve the performance and efficiency of workflow management systems and solve the problem of poor flexibility of the current workflow technology (Long et al., 2009), Agent technology is used to record the dynamic workflow’s routing information because of its features such as intelligence, autonomy and flexibility, as well as routing algorithm is used to select the right route. In this way Agent technology and routing algorithm will be applied into the workflow management systems, so that a new dynamic workflow technology is proposed and the flexibility of workflow management systems is improved.

WORKFLOWS AND WORKFLOW NETS

Over the years, there are many different definitions of workflows, but there is not a unified definition. Overall, a workflow is composed of activities which are interconnected by workflow control structures specifying control flow among activities (Son and Kim, 2000).

A workflow model is the abstraction of a workflow as well as the abstraction of business process, describing how the processes are carried out. One of the most important things in dynamic workflows is how to build a workflow model which can adapt the dynamic changes. In this study, Agent technology is introduced into the workflow model, using the features of Agent such as autonomy can characterize the dynamic changes of workflows preferably.

A workflow net (Van der Aalst, 1996; Du et al., 2007) is a directed net which is composed of workflow processes and there is no dead node in the workflow net (Du et al., 2008; Du and Jiang, 2008), in other words, starting from any activity, can reach one of the terminal activities. A workflow net consists of places, transitions and directed arcs. In the net a circle stands for a place; a rectangle stands for a transition; the directed arcs connect a place to a transition or connect a transition to a place. But there is no arc which connects a transition to a transition or connects a place to a place. In the workflow net, a place stands for the state of a current job; a transition stands for the implementation of an activity. In this study, activities will be divided into two categories, one of which named active place represent a state of an activity, AS represents the active place in the database. The other is branching place, the emergence of which can avoid the connection between transitions or places, but has no real meaning. ASt represents the branching places in the database. At the same time, in this study the weights of an arc no longer represent consumption and generation of the resources, but represent the time consumed by the running of a transition. The consumption and generation of resources are given in the routing table.

AN AGENT-BASED WORKFLOW MODEL

Agents are software entities that perform some sets of tasks on behalf of users with some degree of autonomy (Othman et al., 2007). In recent years, Agent has been well accepted with the following properties (Wooldridge and Jennings, 1995).

Autonomy: Agents operate without the direct intervention of humans or the others and have some kind of control over their actions and internal states.

Social ability: Agents interact with other Agents (and may be humans) via some kind of Agent communication language.

Reactivity: Agents perceive their environment and respond in a timely fashion to changes that occur in it.

Adaptive: Agents make plans according to the requirements and constraints of target and environment, modify their goals and plans when the environment changes.

Because of these characteristics of Agent, it is very significant to introduce Agent into workflow management systems. In this way, workflow management would be more intelligent and autonomous. In this study, each activity in the workflow process corresponds to an intelligent Agent. Taking advantage of the intelligence, selection of the next activity is autonomous. At the same time, these Agents record the corresponding activity’s routing relation with other activities and interact with their neighbors in time in order to update their routing information, so that we can choose a reasonable path autonomously using the routing algorithm and based on the relevant records of the corresponding intelligent Agent.

When building a workflow management system for an enterprise, the entire enterprise is described as an Agent federation. Each activity is corresponded with an intelligent Agent, so the whole system can be regarded as an Agent federation. In the system, information is exchanged between Agents, so the system is more coherent. Furthermore each intelligent Agent is an independent entity in the workflow management system. The Agent can complete the update independently and deliver the relative information to the neighbors, notify its neighbors to make some update. There are also an intelligent Scheduling Agent, an Artificial Agent and some Resource Agents in the system. Overall Fig. 1 shows an Agent-based workflow model.

The main function of each component in the Fig. 1 is as follows:

Fig. 1:	An Agent-based workflow model

The system model shown in Fig. 1 is adopted in this study. The business processes in the model are developed by the enterprise. The initial and terminal activities are presented when the business model was developed. The most optimized path is chosen by Routing Agents according to the routing information. The staff imports the initial and terminal activities into the entrance of workflow management systems (Long et al., 2009) and then is transformed into a workflow instance by a workflow engine. At first the workflow parser parses and initializes the workflow instance and then the workflow instance is executed from initial activity to terminal activity by the Routing Agent. In this process, the Resource Agents are fired when some resources are needed, the Scheduling Agent is fired at first when there are some exceptions and the Artificial Agent is fired when the exceptions can not be resolved by the Scheduling Agent, the Routing Agent is updated at last.

Through this model, the Agent technology was introduced into the workflow management systems, the dynamic nature of workflow was implemented preferably if the Agent features such as intelligence and autonomy are made best use of to realize the intelligence and autonomy of workflow management systems.

ALGORITHM OF ROUTING SELECTION

The process definition of workflow models will be made at first. All of the activities and paths are included into a directed-weighted net, the nodes in the net present the activities, the directed arcs present the paths, the weighted values present the time consumed by the execution of activities. In order to express the relation between activities clearly, the special symbols in the Fig. 2. (Van der Aalst and Van Hee, 2002) are presented to express the multiply path selection.

In Fig. 2, the structure AND-split expresses such a situation that the completion of transition t’s precondition have an effect on all the post-conditions of t. The structure AND-join expresses such situation that the post-condition of transition t can be executed only when all the preconditions of t are completed. The structure OR-split describes that when the precondition of transition t was completed, only one post-condition of t can be executed; The structure OR-join describes that when one of transition t’s preconditions was completed, the post-condition of t can be executed.

Fig. 2:	Several basic structures of the workflow net

Fig. 3:	The combination of basic structure

At the same time, there are such situations in workflow net. The post-condition of an activity is more than one and the relations between them are different. Some of them are dependent with each other, in other words, if the preconditions were finished all of these activities will be executed together. But there are also activities which have the same preconditions, but when the preconditions were completed, only one of them can be executed. The combination of AND-split, AND-join, OR-split, OR-join in Fig. 3 will be used to describe these situations.

At first, in this study the places will be divided into groups, in this way the relations between activities can be expressed clearly. The activities in some groups are dependent with each other; the activities in the other groups are independent with each other. For example, when we apply for a loan to buy a house in the bank, the load can be handled by real estate, then a group of documents will be needed and the load can also be handled by individuals, then the other group of documents will be needed in this situation. In Fig. 3, a1 and a2 which do not have any real meaning are branching places, but in order to avoid the directed connection between two places. The C-split in Fig. 3 is the combination of AND-split and OR-split, describes that when the precondition was completed only one of the groups of post-conditions can be executed. The C-join in Fig. 3 is the combination of AND- join and OR- join, describes that the post-condition of transition t can be executed when all of the preconditions in one of the groups were completed.

When the staff inputs the initial activity, the system will choose the next route dynamically according to the algorithm of routing selection. When there are no suitable routes for choosing at the running time, the suitable active nodes will be added dynamically through the interaction between Routing Agent, Scheduling Agent and Artificial Agent. After that the corresponding arcs and weights will be added to enrich the workflow net. In other words, the current workflow net need to update constantly through adding new arcs or new activities, all of these are completed by Scheduling Agent and Artificial Agent. When the business process run to an activity, it needs to conform whether the activity can be executed continuously. If it can be executed, the suitable and shortest time-consuming route will be selected from the routing table and the process will be continued. There are two potential reasons for the impossibility, one is that some preconditions of the activity do not completed, in this case, these preconditions will be executed. The other is that the resources are not enough, then the Resource Agent will be fired to coordinate the usage of resources.

Definition 1: A routing Agent is denoted by a 7-tupleA=<ID, P, A, R, Res, Pre, TA>, where:

The relation between activity and ID is one to one correspondence, in this way each activity can be found through ID. P is the description of the corresponding activity. Every activity needs some conditions to support its execution. There are several preconditions of an activity, so when the business process runs to an activity, it needs to check whether all the preconditions of the activity were completed. The activity can not continue if there are some preconditions uncompleted. The precondition needs to be executed before the activity when it was uncompleted. A is a finite set of the preconditions, A= {a1, a2, …, an}, where ai ( i = 1, 2, …, n) is the ID of activities. The implementation of each activity requires a number of resources and Res is the required resources of the activity, Res = {x1*r1, x2*r2,… xn*rn}, where ri is a specific resource and xi is the amount of ri. There are several relative activities of the current activity in the workflow net, but which one is the suitable post precondition? Based on this question Pre was introduced into this study to describe the conditions. There are not only resource constraints but also role constraints included in the Pre, what’s more, restricting rules of internal processes are included into the Pre.

Table 1:	An example of routing table

TA is the routing table of Routing Agent, the reachable activity of the current activity, the objective activity of each post-conditions, the needed resources of the post-condition, the resources can be produced when running to the post-condition, the description of the post-condition and the time spent by running to the terminal activity through this post-condition are all concluded in the Routing table. The description of the post-condition contains the description of the corresponding role and the description of the current state. The capital letters are used to indicate the available conditions of the activity. Res is the required resources of the corresponding activity, Res = {a*r1, b*r2, …, x*rn}, x*rn shows that the number of resource rn is x. If the number of resource r is indefinite, it will be presented as ∞*r. TA is expressed as Table 1.

When the process runs to a certain activity, it is necessary to select the next activity according to the routing table and the algorithm of routing selection. The algorithm of routing selection is just as follows:

Algorithm 1:	Algorithm of routing selection

Step 5 execute the activity A, update the routing table and relative information of Agent;

Step 6 launch the Scheduling Agent. The Scheduling Agent searches the activity which has the same objective activity with the current activity in the workflow net, add the activity to the routing table, then update the routing table and H1, go to Step 2;

if (the eligible activity was not found) go to Step 9;

Step 7 launch the Resource Agent. The Resource Agent coordinates the required resource of this activity with the method of first-come first-served, then update the routing table, go to Step 3

Step 8 launch the Artificial Agent. The administrator gets the feedback on the situation from the Artificial Agent at first. The new arcs will be added to the workflow net by the administrator and then update the routing table and H2, go to Step 3

Step 9 launch the Artificial Agent. The administrator gets the feedback on the situation from the Artificial Agent at first. The new activity or the new arcs will be added to the workflow net by the administrator and then update the routing table and H1, go to Step 2

In the algorithm, the set H1 of post-condition would be formed in the step 1, all the activity in H1 have the same objective activity with the current activity. If there is no activity satisfy the condition, skip to the step 6, then Scheduling Agent would be fired to search the matching activity from the whole workflow net with the method of breadth-first searching. The time complexity of step 6 is the activity number of the workflow net. If there is no activity matching the requirement, the Artificial Agent will be fired. In the step 2, the number of required resources would be checked, the activity meeting the resource requirement would be selected out and form the set H2, if there is no activity in H2, then skip to the step 7 and wait for the Resource Agent to coordinate the usage of all the resources. In the step 3, the qualification of each activity would be checked, all the activities meeting the requirements would be selected out from H2 and form the set H3. If there is no activity in H3, skip to step 8, then the Artificial Agent would be fired and new activities or new arcs would be added to the workflow net.

APPLICATION

In the company, there are several approaches to deal with the same problem and the result will be different or similar. In order to have the most effective and optimized approach it is necessary to optimize the process of selection and make use of the workflow net. There is a simple workflow net in the Fig. 4 and there are four terminal activities in the workflow net.

Suppose that there is a business process, the initial activity is a1, the terminal activity is s1, the resources of a1 is {4* r1, 3* r2, 6* r3}. The corresponding routing Agent of a1 is A1 = {1, B, {a1, a8, a16, a18}, {4* r1, 3* r2, 6* r3}, {}, A, T1}. The routing table T1 of A1 is in the Table 2. According to the routing table, the suitable route will be selected.

The corresponding Routing Agents of activity a2, a8, a16, a18 are A2 = {2, A, {a3, a5 }, {4* r1, 3* r2, 6* r3}, { r1, 2*r3}, Z, T2}, A8 = {8, L, {a9, a14 }, {3* r1, 2* r2, 4* r3}, { r1, r2, 2*r3}, K, T8}, A16 = {16, U, {a17 }, {4* r1, 6* r2, 3* r3}, { 6*r1, 2*r3}, H, T16}, A18 = {18, G, {a19}, {6* r1, 8* r2, 3* r3}, { 2*r1, 4* r2, 2*r3}, J, T18}. According to the algorithm of routing selection, the routing selection process is just as follows:

Suppose that a process is running to an activity a6, the corresponding Routing Agent of a6 is A6 = {6, H, {s1}, {3* r1, 5* r2, 7* r3}, {2* r1, 2* r2, 6* r3}, K, T6}, the corresponding Routing Agent of a7 is A7 = {6, K, {s1}, {2* r1, r2, 3* r3}, {4* r1, r2, 6* r3}, K, T7}. Table 3 is the routing table T6 of a6. When the process runs to a6, the preconditions of a6 are checked whether all of them are executed. If there are some unexecuted preconditions, a6 will wait for the complement of the preconditions. According to the algorithm of routing selection, a routing selection process is just as follows:

Table 2:	Routing table of a1

Fig. 4:	A simple workflow net

Table 3:	The routing table of a6

Run in this way, until running to the terminal activity s1.

Every activity in the workflow net in Fig. 4 can run to one of the terminal activity, in other words, there are no dead activities in the workflow net. When searching the objective activity, it concludes several situations.

So, the objective activity can be reached when starting from any activity.