Patent Document

FIELD OF THE INVENTION  
         [0001]    The invention relates to workflow management and web service composition. More particularly, the invention relates to automated workflow analysis and prioritization.  
         BACKGROUND OF THE INVENTION  
         [0002]    Many business-related processes depend upon the execution of pre-defined tasks. Computers and other automated systems are applied to automating a number of these pre-defined tasks, handling such aspects as: identification and allocation of resources; time management; inventory control; accounting procedures; etc. Systems dedicated to the definition, execution, management, and monitoring of such business processes are generally referred to as Process Management Systems (PMSs). When the process is used to compose (i.e., orchestrate the execution of) web services, then PMSs are also called “Service Composition Engines”. The term PMS as used in this document refers to both systems executing business processes and to systems composing web services.  
           [0003]    A process management system makes at least two determinations for each step in a business process: the services or specific procedures required; and the resources needed to do perform them. Under this context, resources include, for example: personnel; office machinery; forms and other printed matter; computer hardware; software applications; third-party services (i.e., shipping contractor; technical consultant; etc.); consumables; etc.  
           [0004]    Generally, a resource will be assigned to several pending activities, representing numerous different processes. For example, an administrative employee may have to process several travel reimbursement requests, to book hotels for visitors, arrange meetings, and so on. Thus, any given resource is likely to have involvement in several different tasks concurrently. Within current Process Management Systems, personnel can choose the order in which they process activities assigned to them, or, in the case of an automated resource, will perform the assigned tasks on a First Come, First Served (FCFS) basis.  
           [0005]    The inherently arbitrary order in which personnel may choose to perform (or avoid) assigned tasks often leads to poorly prioritized execution of that task, sometimes to the extent that deadlines are missed, or unnecessary time and cost burdens are assumed in meeting the deadline. Such burdensome, “hurry-up” situations can also lead to sacrificing service quality or missing other deadlines, having a compounding effect on other assigned tasks. The first come, first served nature of automated systems can lead to similar inefficiencies and missed deadlines, for example, if several relatively low-priority tasks are completed before a longer-duration, relatively high-priority task, simply because of their order within the work queue.  
           [0006]    Attention is directed to commonly assigned U.S. patent application Ser. No. 09/860,230, filed May 18, 2001, titled “Method of Identifying and Analyzing Business Processes from Workflow Audit Logs”, listing as inventors Fabio Casati, Ming-Chien Shan, Li-Jie Jin, Umeshwar Dayal, Daniela Grigori, and Angela Bonifati, Attorney Docket Number 10010068-1, which describes workflow management systems and workflow audit logs, and which is incorporated herein by reference. Attention is also directed to U.S. patent application Ser. No. 09/464,311, filed Dec. 15, 1999, titled “Custom Profiling Apparatus for Conducting Customer Behavior Pattern Analysis, and Method for Comparing Customer Behavior Patterns”, naming Qiming Chen, Umeshwar Dayal, and Meichun Hsu as inventors, and which is incorporated herein by reference.  
         SUMMARY OF THE INVENTION  
         [0007]    The invention relates to a system and method for automatically assigning and dynamically modifying priorities of the work items (i.e., nodes) in order to optimize process execution performance.  
           [0008]    One aspect of the invention provides a system for estimating a cost of a process, the system comprising a first store of process instance data, a second store of data including predictions and statistics respectively corresponding to the process instance data, and a dynamic prioritization system configured to selectively access data in the first store and the second store and to estimate a cost of a process instance responsive to the accessing.  
           [0009]    Another aspect of the invention provides a method of estimating a cost of a process, the method comprising a first store of process instance data, providing a second store of data including predictions and statistics respectively corresponding to the process instance data, selectively accessing data in the first store and the second store, and estimating a cost of a process instance responsive to the accessing using a dynamic prioritization system.  
           [0010]    Another aspect of the invention provides a system comprising means for selectively accessing data related to a process, means for accessing predictions and statistics data related to the process, means for computing a cost of a step within the process responsive to the accessing, and means for selectively prioritizing the step responsive to the computing. 
       
    
    
     DESCRIPTION OF THE DRAWINGS  
       [0011]    [0011]FIG. 1 provides a block diagrammatic illustration of a business system according to one embodiment of the invention.  
         [0012]    [0012]FIG. 2 provides a block diagrammatic illustration of a business system according to another embodiment of the invention.  
         [0013]    [0013]FIG. 3 provides a block diagrammatic illustration of a business system according to still another embodiment of the invention.  
         [0014]    [0014]FIG. 4 provides a block diagrammatic illustration of a business system according to yet another embodiment of the invention.  
         [0015]    [0015]FIG. 5 provides a block diagrammatic illustration of a business system according to another embodiment of the invention.  
         [0016]    [0016]FIG. 6 is a flowchart of the steps executed by some embodiments of the invention.  
         [0017]    [0017]FIG. 7 is a flowchart of the steps executed by another embodiment of the invention.  
         [0018]    [0018]FIG. 8 is a flowchart of the steps executed by yet another embodiment of the invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0019]    [0019]FIG. 1 provides a block diagram of a system  110  according to one embodiment of the invention. The system  110  includes a store of process execution data (i.e., process instance data)  112 . In one embodiment, the store  112  is defined by a memory such as a floppy disk, a hard drive, an optical disk, a digital tape, a ROM, a RAM, or any other type of storage device used by computers or digital equipment. The process data is generated by a process engine  124  configured to gather and store process instance data as process execution progresses. The process instance data within the store  112  can include, for example: overall process definitions; specific sub-steps, or ‘nodes’ within a defined process; process instance input parameters; process instance output parameters; process instance activation and completion time(s); process instance priority; and input and output parameters, activation and completion time(s) and priorities for each node within a process instance.  
         [0020]    The system  110  further includes a store of predictions and statistical data  114 . The prediction and statistical data within the store  114  includes statistical aggregation data, such as, for example: average execution time for each type of process instance and node; total execution times for each type of process instance and node; average number of times a certain node is invoked within a certain process instance; etc. The prediction data within the store  114  includes, for example: data predicting the next node to be executed; data predicting the time required to execute the node; data predicting the time and date a given process instance will be complete; etc.  
         [0021]    In the illustrated embodiment, a dynamic prioritization system  116  is integrated within a worklist manager  122 . The worklist manager  122  stores a listing of tasks or process instances which are pending. The dynamic prioritization system  116  is in data communication with the data store  112  and the data store  114  by way of data links  130  and  132 , respectively. The dynamic prioritization system  116  functions to keep the list of process instances in worklist manager  122  in priority order to ensure the proper sequence of execution by their corresponding resources (described hereafter).  
         [0022]    The process engine  124  is further configured to read data from, write data to, and exercise control of worklist manager  122  and data store  112 . In one embodiment, a processor is included which executes the functions of, dynamic prioritization system  116 , worklist manager  122 , and process engine  124 . Other embodiments are possible. Furthermore, system  110  includes user interfaces  118  and automated resources  120 , which request work task information (i.e., assigned process instances) from the dynamic prioritization system  116  by way of respective data links  134  and  136 .  
         [0023]    [0023]FIG. 6 provides a sequence flowchart of the operations performed by dynamic prioritization system  116 , generally referred to as numeral  210 . The sequence  210  is executed each time any node of a process instance is scheduled for execution.  
         [0024]    The sequence  210  begins with step  212 , in which the dynamic prioritization system  116  determines which process instances within the worklist manager  122  are active (i.e., in progress), and are therefore in need of analysis. Corresponding data is then gathered from store  112  by dynamic prioritization system  116 .  
         [0025]    In step  214 , the dynamic prioritization system  116  gathers corresponding prediction and statistical data from store  114 .  
         [0026]    In step  216 , the dynamic prioritization system  116  computes the cost of executing the process instance that is under analysis. The cost of executing a given process instance is determined by way of a ‘cost function’ f 1 , which is a multi-variable function defined as follows:  
         [0027]    f 1 ) C=Fpd(t, Vn)  
         [0028]    where: C denotes the computed cost; pd denotes the specific process definition; t denotes the time; and Vn denotes the process instance execution trace.  
         [0029]    The specific values for the parameters in cost function Fpd are taken from the predictions and statistical database store  114 . Particular attributes and characteristics of cost function Fpd( ) shall be subsequently described. Continuing the description of step  216 , the dynamic prioritization system  116  computes the predicted value of C for each possible (i.e., defined) prioritization option of the process instance. Steps  212 ,  214  and  216  are performed in an iterative fashion until all active process instances have been cost analyzed.  
         [0030]    In step  218 , the dynamic prioritization system  116  selects that combination of prioritization options that provides the minimum cost of performing the active process instances.  
         [0031]    In step  220 , in which the dynamic prioritization system  116  alters the order of the analyzed process instances (i.e., those in progress or still awaiting execution) presently queued within worklist manager  122  corresponding to the priorities selected in step  218 . In this way, user interfaces  118  and automated resources  120  receive the most recently prioritized tasks (i.e., nodes) within a given process instance in response an assignment request to worklist manager  122  by way of respective links  134  and  136 . This manner of requesting process instance node assignments on an “at-will” basis is known as a ‘pull’ model.  
         [0032]    Referring to FIG. 2, a system  150  according to another embodiment of the invention is shown in block diagrammatic form. The system  150  is substantially the same as system  110 , with like reference numbers indicating like components, except that the dynamic prioritization system  316  is remote from worklist manager  322 , having data communication therebetween by way of link  154 . In addition, the process execution data store  112  is in data communication with the worklist manager  168 . In one embodiment, a processor executes the functions of the process engine  124 , the dynamic prioritization system  316 , and the work list manager  322 . Other embodiments are possible.  
         [0033]    The system  150  is governed substantially by sequence  210  as previously described, with the principal difference occurring at step  220 . Rather than altering the order of the process instances queued within worklist manager, the dynamic prioritization system  316  simply passes the highest priority nodes within pending process instances to user interfaces  118  and automated resources  120  in response to corresponding assignment requests. In this way, the dynamic prioritization system  166  acts as the ‘front end’ of system  150  as seen by user interfaces  118  and automated resources  120 . This prevents the need to reorder the process instance queue within worklist manager  322 . The system  150  is another embodiment of a pull model.  
         [0034]    Turning now to FIG. 3, a system  160  according to still another embodiment of the invention is provided in block diagrammatic form. The system  160  is substantially the same as the system  150 , with the distinction that the dynamic prioritization system  416  is remote from the worklist manager  422 , having no direct data communication link therebetween. The system  160  is governed substantially by the sequence  210  as previously described, with the difference being that sequence  210  is executed periodically, rather than in response to node execution scheduling.  
         [0035]    Process instances queued in the worklist  422  are reordered in step  220  by the dynamic prioritization system  416  in correspondence to the priorities selected in step  218  after each execution of sequence  210 . Furthermore, user interfaces  118  and automated resources  120  request assignments directly from worklist  422  by way of respective links  162  and  164 . The system  160  is another embodiment of a pull model. In one embodiment, a processor executes the functions of the process engine  124 , the dynamic prioritization system  416 , and the work list manager  422 . Other embodiments are possible.  
         [0036]    [0036]FIG. 4 provides a block diagram of a system  170  according to another embodiment of the invention. The system  170  includes previously described elements  112 ,  114 ,  118 ,  120  and  124 . Further included in the system  170  are messaging system  172  and work queues  174 , as well as dynamic prioritization system  516 . The pending process instances are queued within work queues  174 , rather than within a worklist manager (not used in system  170 ), as before. In one embodiment, a processor executes the functions of the process engine  124 , the messaging system  172 , and the dynamic prioritization system  516 . Other embodiments are possible.  
         [0037]    Concurrent reference is now made to FIGS. 4 and 7. FIG. 7 provides a sequence flowchart of the operations performed by dynamic prioritization system  516 , generally referred to as numeral  250 .  
         [0038]    The sequence  250  is executed each time a node in a process instance is scheduled for execution, and begins with sequential steps  212  and  214 , as previously described.  
         [0039]    In step  252 , the dynamic prioritization system  166  calculates the cost of executing each just-scheduled node using the cost function corresponding to each, with the dynamic prioritization system  516  reading the required parameters from the process execution data store  112 .  
         [0040]    In step  254 , the dynamic prioritization system  516  selects the prioritization options for each node just scheduled that results in the minimum overall cost of execution.  
         [0041]    In step  256 , the process instances of work queues  174  are reordered in correspondence with the prioritization options selected in step  254 .  
         [0042]    In further consideration of the system  170 , the dynamic prioritization system  516  communicates newly prioritized (i.e., scheduled) nodes to messaging system  172 , by way of communications link  182 . The messaging system  172  is configured to route nodes to their assigned destinations—users  118  or automated resources  120 —by way of respective data links  178  and  180 . This routing is automatic in response to receiving nodes from the dynamic prioritization system  516 , and is not responsive to a request from user interfaces  118  or automated resources  120 . This scheme is therefore known as a ‘push’ model, as assigned nodes are pushed to their respective assignees rather than being passed upon request.  
         [0043]    [0043]FIG. 5 is a block diagram of a business system according to another embodiment of the invention, generally referred to as numeral  190 . The system  190  includes previously described elements  112 ,  114 ,  118 ,  120 ,  124 , and  172 . Further included is a dynamic processing system  616 . The system  190  does not include a worklist manager, as the dynamic prioritization system  616  pushes assigned nodes to corresponding user interfaces  118  and automated resources  120  upon scheduling; thus, no worklist manager is required as user interfaces  118  and automated resources  120  do not request assignments. In one embodiment, a processor executes the functions of the process engine  124 , the messaging system  172 , and the dynamic prioritization system  616 . Other embodiments are possible.  
         [0044]    Concurrent reference is now made to FIGS. 5 and 8. FIG. 8 is a flowchart of the operations performed by the dynamic prioritization system  616 , with the sequence generally referred to as numeral  270 .  
         [0045]    The sequence  270  begins with the sequential execution of steps  212  and  214 , which perform as previously described.  
         [0046]    In step  272 , the dynamic prioritization system  616  computes the cost of executing each process instance, for each respective prioritization option. As before, the parameters required for the cost computation are taken from the data store  114 , by way of data communications link  132 . In computing the costs, the dynamic prioritization system  616  assumes that all process instances are assigned their default priorities.  
         [0047]    In step  274 , the dynamic prioritization system  616  selects the default priorities for all work nodes that provide the minimum cost of execution for each active process instance.  
         [0048]    In step  276 , the dynamic prioritization system  616  alters the default priorities of the of each work item (i.e., node) to reflect the minimum-cost selections of step  274 . The dynamic prioritization system  616  then stores the selected nodes in data store  112 , where they are read by the process engine  124  by way of data link  138 . The process engine  124  then sends the selected node to messaging system  172  by way of path  192 , which in turns pushes (i.e., transmits) them to corresponding user interfaces  118  and automated resources  120  by way of respective links  178  and  180 . System  190  is selectively executed each time a node is completed, each time a node is scheduled, or periodically, as desired by a system administrator.  
         [0049]    In addition to the systems and sequences just described, various embodiments provide for a number of work prioritization schemes, which contribute to identifying the appropriate priority order to optimize overall process instance performance. These include, for example:  
         [0050]    a1) Prediction of work item execution time, which refers to the prediction of execution time for a work item by the resource to which it is assigned, also depending on the process instance, the time in which the work item is executed, and other parameters.  
         [0051]    a2) Prediction of process execution time, which is the prediction of the remainder of the process instance, selectively based on a given priority assignment.  
         [0052]    a3) Prediction of the process load, which is the prediction of how many process instances will be activated  
         [0053]    a4) Prediction of process instance execution path, which predicts the flow subgraphs required by a process instance, and specifically predictions of which nodes will be activated, and when, and how many times.  
         [0054]    a5) Prediction of resource load, which is the prediction of how many work items will be assigned to a given resource at a future time.  
         [0055]    Through the use of schemes a1, a2, a3, a4 and a5, the predictions process is dynamic and ongoing, taking into account both past process execution predictions as well as actual process instance performance, so that the business system of the present invention is adaptive in nature. Once the above variables have been predicted, then the DPS can compute the cost function using these predicted values. The cost function is used when evaluating the different prioritization schemes.  
         [0056]    The protection sought is not to be limited to the disclosed embodiments, which are given by way of example only, but instead is to be limited only by the scope of the appended claims.

Technology Category: 3