Business process in a large organization generally include various system resources, humans, and tools which are geographically distributed. The concept of a workflow has emerged in an objective of automating and computerizing these processes. A workflow is an abstract of a business process, which identifies the various workflow activities, procedural rules and associated control data used to manage the workflow execution. An activity is a description of a piece of work that forms one logical step within a business process. When a business process is described within a workflow definition, several unit tasks comprising the business correspond to activities in the workflow.
In distributed workflow systems, each task is placed at some particular host and accesses workflow resources such as information sources. These resources are also placed at some hosts and are commonly shared by multiple tasks. The nature of distributed workflow systems may incur significant overhead of remote processing if involved tasks and their required resources are not allocated to appropriate hosts. Thus, if we can locate workflow components as close as possible in the distributed workflow environment, we can improve the performance of distributed workflow processing. In this aspect, we propose the efficient workflow task allocation method.
We first define the workflow task allocation problem that places workflow components in order to maximize the proximity of adjacent tasks as well as the locality of references between a task and its required resources. Next, we prove that the problem is NP-Complete. Because the integer programming is the most proper approach for the workflow task allocation problem, we transform the problem into the form of integer programming. In addition, we also show through experiments that the task allocation obtained by the proposed method gives better performance than those obtained by other heuristic methods.
The proposed workflow task allocation method can easily be adapted for the various workflow constraints and environment. We show that this method finds out an optimal solution for medium scale workflow systems with reasonable amount of time even though the problem is inherently intractable.
