SYSTEM TO AVOID POLICY-BASED DEADLOCKS IN WORKFLOW EXECUTION

• US 20090198548A1
• Filed: 02/05/2008
• Published: 08/06/2009
• Est. Priority Date: 02/05/2008
• Status: Abandoned Application

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Kohler, Mathias, Schaad, Andreas
• Application Number:
  US12/025,889
• Publication Number:
  US 20090198548A1
• Time in Patent Office: Days
• US Class Current: 705/7.27
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0633 Workflow analysis

Abstract

A computer-implemented method avoids policy-based deadlocks in execution of a workflow. The method includes receiving information describing a workflow. The workflow includes tasks, roles, site of tasks and security constraints related to the tasks. A data structure, representative of relationships between the tasks and the security constraints is automatically generated. An automated, design-time evaluation is performed using the data structure to determine a minimal number of resources to be assigned to the roles in order to execute the tasks of the workflow, and to avoid deadlock in execution of the tasks of the workflow as a result of security constraints.

Claims

1. A computer-implemented method comprising:

retrieving information describing a workflow including tasks, roles assigned to the tasks and security constraints related to the tasks;

automatically generating at least one data structure representative of relationships between the tasks and the security constraints; and

performing an automated, design-time evaluation, using the at least one data structure, to determine a minimal number of resources to be assigned to the roles in order to execute the tasks of the workflow and to avoid deadlock in execution of the tasks of the workflow as a result of the security constraints.

2. The computer-implemented method of claim 1, wherein the workflow is a business process, the tasks are business process activities, and the security constraints are at least one of a separation of duty constraint or a binding of duty constraint.

3. The computer-implemented method of claim 1, wherein the automated generation of the at least one data structure includes reflecting, in the at least one data structure, a relationship between the first and second tasks of the workflow having a common security constraint.

4. The computer-implemented method of claim 1, wherein the automated generation of the at least one data structure includes removing a first security constraint relating third and fourth tasks of the workflow to which different roles are assigned.

5. The computer-implemented method of claim 1, wherein the automated generation of the least one data structure includes:

identifying multiple role assignments with respect to a task of the workflow;

generating multiple data structures based on the at least one data structure, each of the multiple data structures representing a single role assignment of the multiple role assignments with respect to the task of the workflow.

6. The computer-implement method of claim 5, wherein the at least one data structure is a constraint-based relation graph which reflects the relationship between the common security constraint and the first and second tasks of the workflow.

7. The computer-implemented method of claim 6, wherein the generating of the multiple data structures comprises transforming the constraint-based relation graph into a set of graphs, each graph of the set of graphs having a unique set of role-task assignments.

8. The computer-implemented method of claim 7, wherein the performance of the automated, design-time evaluation includes applying at least one of graph coloring, general operations research or search algorithms to each graph of the set of graphs to identify a number of resources to be assigned to each role

9. The computer-implemented method of claim 1, wherein the performance of the automated, design-time evaluation includes generating a set of placeholder resources to be assigned to the tasks as placeholders for a later mapping of at run-time available resources.

10. The computer-implemented method of claim 1, including, at run-time:

performing a determination whether the minimal number of resources are available to be assigned to the roles in order to avoid deadlock in the execution of the tasks of the workflow; and

assigning actual resources to the roles.

11. The computer-implemented method of claim 1, including, at run-time, executing the tasks of the workflow.

12. A computer-implemented system comprising:

a first component to retrieve information describing a workflow including tasks, roles assigned to the tasks and security constraints related to the tasks, and to automatically generate at least one data structure representative of relationships between the tasks and the security constraints; and

a second component to perform an automated, design-time evaluation, using the at least one data structure, to determine a minimal number of resources to be assigned to the roles in order to execute the tasks of the workflow and to avoid deadlock in execution of the tasks of the workflow as a result of the security constraints.

13. The computer-implemented system of claim 12, wherein the workflow is a business process, the tasks are business process activities, and the security constraints are at least one of a separation of duty constraint or a binding of duty constraint.

14. The computer-implemented system of claim 12, wherein the second component is to generate the at least one data structure to reflect a relationship between the first and second tasks of the workflow having a common security constraint.

15. The computer-implemented system of claim 12, wherein the second component is automatically to generate the at least one data structure by removing a first security constraint relating third and fourth tasks of the workflow to which different roles are assigned.

16. The computer-implemented system of claim 12, wherein the second component is automatically to generate the at least one data structure by:

identifying multiple role assignments with respect to a task of the workflow;

generating multiple data structures based on the at least one data structure, each of the multiple data structures representing a single role assignment of the multiple role assignments with respect to the task of the workflow.

17. The computer-implement system of claim 16, wherein the at least one data structure is a constraint-based relation graph which reflects the relationship between the common security constraint and the first and second tasks of the workflow.

18. The computer-implemented system of claim 16, wherein the generating of the multiple data structures comprises transforming the constraint-based relation graph into a set of graphs, each graph of the set of graphs having a unique set of role-task assignments.

19. The computer-implemented system of claim 18, wherein the second component is to applying at least one of graph coloring, operations research or search algorithms to each graph of the set of graphs to identify a number of resources to be assigned to each role

20. The computer-implemented system of claim 12, wherein the second component is to generate a set of placeholder resources to be assigned to the tasks as placeholders for a later mapping of at run-time available resources.

21. The computer-implemented system of claim 12, including a third component to:

perform a determination whether the minimal number of resources are available to be assigned to the roles in order to avoid deadlock in the execution of the tasks of the workflow; and

assign actual resources to the roles.

22. The computer-implemented system of claim 12, including a fourth component, at run-time, to execute the tasks of the workflow.

23. A computer system comprising:

a memory; and

a processor, communicatively coupled to the memory, to;

retrieve information describing a workflow including tasks, roles assigned to the tasks and security constraints related to the tasks;

automatically generate at least one data structure representative of relationships between the tasks and the security constraints; and

perform an automated, design-time evaluation, using the at least one data structure, to determine a minimal number of resources to be assigned to the roles in order to execute the tasks of the workflow and to avoid deadlock in execution of the tasks of the workflow as a result of the security constraints.

24. A machine-readable medium storing instructions that, when executed by a processor, cause the processor to:

retrieve information describing a workflow including tasks, roles assigned to the tasks and security constraints related to the tasks;

automatically generate at least one data structure representative of relationships between the tasks and the security constraints; and

perform an automated, design-time evaluation, using the at least one data structure, to determine a minimal number of resources to be assigned to the roles in order to execute the tasks of the workflow and to avoid deadlock in execution of the tasks of the workflow as a result of the security constraints.