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

The objective of this work is to propose an approach based on a p-time Petri net model with hybrid resources to solve the real time scheduling problem of Workflow Management Systems. The proposed approach uses an activity diagram to show the main activities of the system and the different routings of the Workflow Process. Based on the activity diagram, the corresponding p-time Petri net model is produced by assigning a time interval to every Workflow activity. Hybrid resource (discrete + continuous) allocation mechanisms are modeled by an hybrid Petri net with discrete transitions in order to represent the different kinds of resources (equipment and human resources) in a more realistic way. Time constraint propagation mechanisms are presented and a token player algorithm is applied to the Petri net model in order to obtain an acceptable scenario corresponding to a specific sequence of activities which respects the time constraints. The approach is illustrated through an example of “Handle Complaint Process”.

The purpose of Workflow Management Systems [2] is to execute Workflow Processes. Workflow Processes represent the sequences of activities which have to be executed within an organization to treat specific cases and to reach a well defined goal. Of all notations used in the Software Industry, UML [22] is one of the best accepted. In particular, the activity diagrams of the UML notation seem to be very suitable for proposing approaches to represent Workflow Processes as these diagrams represent basic routings encountered in Workflow Processes which are the sequential routing (the sequential execution of activities), the parallel routing (two or more activities executed simultaneously) and the selective routing (when a choice must be made between two or more activities). Several authors like [8] and [12] have already used UML notations for the specification of Workflow Processes. However, UML notations have their limitations when they are used for specifying the real time characteristics of Workflow Management Systems. For example, activity diagrams do not represent real time constraints in a formal way and they do not show in an explicit manner resource allocation mechanisms. As a matter of fact, late deliveries in an organization are generally due to the problem of resource overload. Consequently, the model used at a Workflow Management System level should consider resource allocation mechanisms. In particular, time management of Workflow Processes is crucial for improving the efficiency of Business Processes within an organization. Petri nets [21] are very well adapted to model Real Time Systems, as they allow for a good representation of conflict situations, shared resources, synchronous and asynchronous communication, precedence constraints and explicit quantitative time constraints in the time Petri net case. Many papers have already considered Petri net theory as an efficient tool for the modeling and analysis of Workflow Management Systems. In [1] and [2], for example, high level Petri nets are used in order to model Workflow Management Systems. In [6], an enterprise model is automatically translated into a Petri net in order to check for properties which enhance good behavior. The approach described in [29] integrates standard object-oriented structure modeling using UML diagrams with Petri nets, in order to model Workflow Process. In [16], an extended Workflow Petri net model is defined. Such a model allows for the treatment of critical resources which have to be used for specific activities in real time. In [19], an extention of Workflow Nets is presented. This model is called Time Workflow Nets and associates time intervals with the transitions of the corresponding Petri net model. In particular, an example of a health care system is used to illustrate the approach where a nurse who takes care of two patients is represented by a single token in a shared place. In [28], clock specifications are combined with the Petri net theory for the specification of temporal requirements in Business Processes. This new formalization allows for some temporal verification which depends on the construction of a new reachability graph. Timing Constraint Petri net analysis and its application to schedulability analysis of real-time system specifications is studied in [26]. The specificity of the approach is to work with real time equipment represented as a single token in a shared resource place. The analysis of the model is then realized on the entire model for a specific initial marking and allows for some temporal verifications obtained through a kind of reachability simulation. In keeping with [26], a Timing Constraint Workflow Net is presented in [18]. In particular, a verification technique of the schedulability of a Workflow model is proposed. Such a technique is applied to the entire model for a specific initial marking and does not consider in an explicit manner the real time resource allocation mechanisms that can occur during the real time execution of the process. The majority of existing models put their focus on the process aspect and do not consider important characteristics of the Workflow Management Systems. In [1] and [2], for example, the resource allocation mechanisms are represented only in an informal way and in [6] and [18] they are not specified at all. In [16], [19], [26] and [29], resource allocation mechanisms are represented by simple tokens in places as it is generally the case in production systems [17]. But a simple token in a place will not represent in a realistic way human employees who can treat simultaneously different cases in a single day, as is usually the case in most Workflow Processes. The analysis of models which allow the specification of time information, such as [18], [26] and [28], is based on a kind of reachability graph which cannot be generated during the real time execution of Workflow Processes. As a consequence, the results obtained through such a technic will not be directly workable during the real time monitoring of Workflow Processes. In particular, the dynamic behavior of a system imposes a scheduling of control flow. The scheduling problem [9] consists of organizing in time the sequence of activities considering time constraints (time intervals) and constraints of shared resources utilization necessary for activity execution. From the traditional point of view of Software Engineering [23], the scheduling problem is similar to the activity of scenario execution. A scenario execution becomes a kind of simulation which shows the system’s behavior in real time. In the real time system case, several scenarios (several cases in a Workflow Management System) can be executed simultaneously and conflict situations which have to be solved in real time (without a backtrack mechanism) can occur if a same non-preemptive resource is called at the same time for the execution of activities which belong to different scenarios. The fundamental difference between the traditional scheduling problem of production systems [17] and the scheduling problem of Workflow Management Systems is the nature of the resources used to treat the activities. In the production system case, resources represent physical equipment and are represented by a simple token in a place. They are discrete type resources. In the Workflow Management System case, resources can represent physical equipment as well as human employees [2]. For example, it is possible to allocate a nurse in a hospital service to take care of several patients at the same time during her working day. In this case, the nurse could not be seen as a simple discrete token and a model based on an ordinary Petri net would not be able to represent the real features which exist at a Workflow Management System level. Some recent works [2] and [25] emphasize the lack of results which significantly cover the characteristics of Workflow Management Systems when considering the scheduling problem. In this paper, an approach based on UML notations and on a p-time Petri net model with hybrid resources is proposed to solve the real time scheduling problem of Workflow Management Systems.

This article has shown that the initial UML specification (the activity diagram) of a Workflow Management System can be transformed into a unique p-time Petri net with hybrid resources which represents the global behavior of the entire system with explicit time considerations and hybrid resource allocation mechanisms. Based on this model, a token player algorithm used for the scheduling problem of Workflow Management Systems has been applied. The advantages of such an approach are diverse. The fact to work with hybrid resources permits to represent in a more realistic way human behavior. The originality of the time constraint propagation mechanism comes from the idea of combining on a same Petri net model duration intervals (static intervals) which represent durations of activities in a Workflow Process and date intervals (visibility intervals) which represent the waiting times of the cases between activities. Finally, the conflict resolution principle which can be used for shared hybrid resources allows to solve conflict situations in real time without a backtrack mechanism. As a future work proposal, it will be interesting to study the possibility of introducing some fuzzy sets in the Petri net model in such a manner the natural flexibility of human behavior will be represented in a more expressive way at the Workflow Management System level.