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

Effective methods of workflow scheduling can improve the performance of workflow systems. Based on the study of existing scheduling methods, a method of workflow scheduling, called phased method, is proposed. This method is based on colored Petri nets. Activities of workflows are divided into several groups to be scheduled in different phases using this method. Details of the method are discussed. Experimental results show that the proposed method can deal with the uncertainties and the dynamic circumstances very well and a satisfactory balance can be achieved between static global optimization and dynamic local optimization.

Workflow is the automation of a business process, in whole or part, during which documents, information or tasks are passed from one participant to another for action, according to a set of procedural rules [1]. A workflow management system (WfMS) is a system that defines, creates and manages the execution of workflows through the use of software, running on one or more workflow engines, which is able to interpret the process definition, interact with workflow participants and, where required, invoke the use of IT tools and applications [1]. Nowadays, workflow technology has received much attention for its capability to support today's complex business processes. Workflow engine is the heart of a WfMS, while scheduling is one of the core tasks of workflow engine. Scheduling of workflows is a problem of finding a correct execution sequence for the workflow tasks, i.e., execution that obeys the constraints that embody the business logic of the workflow [2]. The goal of workflow scheduling is to allocate the proper task to the proper resource so that workflow instances can be executed by the proper resource in the proper way at the proper time. Scheduling exists almost everywhere. Scheduling of workflows is different from scheduling in other fields. First of all, workflow is dynamic. It has many uncertainties [3] and [4] which have not been dealt with in traditional scheduling literature. (1) The uncertainties of workflows: ➢ Arrival time of workflow instances are uncertain; ➢ Execution paths of instances are uncertain; ➢ Execution time of task is uncertain, etc. (2) The uncertainties of resources: ➢ Execution of a workflow process instance can last a long time. The states of resources may be changed during this period. ➢ More than one resource can execute a task, and a single resource can execute many tasks. Many factors will affect the result of resource allocation, and these factors are dynamically changing. Parallel structures, in which two or more tasks are executed at the same time, have not been dealt with in traditional scheduling literature either. These new challenges mentioned above need to be overcome in workflow scheduling contexts. A phased method of workflow scheduling based on colored Petri nets is proposed in this paper. This method cannot only deal with the problem mentioned above, i.e., the dynamic environment, uncertainties, and concurrent workflows, but also can achieve a preferable balance between global optimization and local optimization. Before getting into the details, some workflow terms that will be used in the rest of this paper are introduced first [1]. 1) Process model: the representation of a business process in a form which supports automated manipulation. The process model consists of a network of tasks and their relationships, criteria to indicate the start and termination of the process, and information about each individual task. 2) Instance: the representation of a single enactment of a workflow process, including its associated data. Each instance represents a separate thread of execution of the workflow process and is created and managed by a workflow management system for each separate invocation of the workflow process. 3) Task: a description of a piece of work that forms one logical step within a process. A task requires human and/or machine resource(s) to support its execution. A task is typically the smallest unit of work which is scheduled by a workflow engine during process enactment. 4) Resource: an actor or agent to carry out workflow tasks. Depending on the application domains, resources can be human resources or nonhuman resources, such as machines, money, software etc. Here, we consider only durable resources, i.e. resources that are claimed and released during the execution, but not created or destroyed [5]. And we assume that a resource can only work on one task at one time. The rest of the paper is organized as follows. In Section 2, different kinds of workflow scheduling methods are introduced. A workflow scheduling system based on colored Petri net is presented in Section 3. The details of the phased method of workflow scheduling are described in Section 4. In Section 5, examples are given to show the feasibility and validity of the method. Some related researches on workflow scheduling are discussed in Section 6. Finally, a conclusion and proposals for future research directions are addressed in Section 7.

Scheduling of workflows is one of the most important and hottest problems in the workflow field. Good scheduling can improve the performance of a workflow system. Many researches have been done on this area. However, existing methods cannot accomplish the scheduling of workflows very well. Static methods of workflow scheduling can reach a global optimal solution for each single instance under static circumstance. But they cannot deal well with uncertainties and dynamic nature of workflows. Dynamic scheduling methods can optimize workflow scheduling while taking all the uncertainties and the dynamic circumstance into account and balance between several instances. But the results achieved are usually optimal for a single task, while not preferable for the whole system. Based on a deeply study and analysis of static methods and dynamic ones, a phased method of workflow scheduling is proposed in this paper. The method, based on colored Petri nets, can adapt to dynamic circumstances and deal with uncertainties and variations very well. There is no need to take guesses on paths. It schedules tasks in batches which can reach global optimization to some extent and can achieve a good balance between several instances. Examples were given to illustrate the process of the phased method. And simulative experiments were done to show the feasibility and superiority of this method. It shows that our method has good performance and is superior to other methods. For further research, how to set scheduling places reasonably or even dynamically is an interesting issue. Actually, the techniques proposed by Panagos etc. [21] and Chen etc. [19] can be used to help setting up scheduling places reasonably. A second line of investigation is the rescheduling of scheduled tasks that has not been executed in order to meet some extra performance requirements or adapt to some changes of the system.