Workflow execution plans through completion condition critical path analysis

• US 8,108,868 B2
• Filed: 12/18/2007
• Issued: 01/31/2012
• Est. Priority Date: 12/18/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Toub, Stephen, Shukla, Dharma
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): SWIFT, CHARLES M
• Application Number:
  US11/958,758
• Publication Number:
  US 20090158289A1
• Time in Patent Office: 1,505 Days
• Field of Search: 718/100, 718/102, 718/103, 718/104
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

Optimizing workflow execution. A method includes identifying a completion condition. The completion condition is specified as part of the overall workflow. The method further includes identifying a number of activities that could be executed to satisfy the completion condition. One or more activities from the number of activities is ordered into an execution plan and assigned system resources based on an analysis of activities in the number of activities and the completion condition.

Claims

1. In a computing environment comprising a workflow runtime, a method for optimizing workflow execution, the method comprising:

at one or more processors of a computing system, identifying a workflow that includes a plurality of activities, along with a completion condition defining one or more states of execution of the plurality of activities that represent completion of the workflow;

at one or more processors of the computing system, prior to initially executing the workflow, developing an optimized execution plan for executing the workflow to achieve the completion condition, comprising;

identifying the plurality of activities of the workflow that could be executed to satisfy the completion condition, the plurality of activities including a first activity and a second activity that could be alternatively executed to satisfy the completion condition, at least in part; and

ordering one or more activities from the plurality of activities into the execution plan and assigning system resources to the one or more activities based on an analysis of the plurality of activities and the completion condition, including ordering the first activity into the exclusion plan to the exclusion of the second activity based on the analysis preferring the first activity over the second activity for satisfying the completion condition; and

at one or more processors of the computing system, subsequent to developing the optimized execution plan, executing the workflow according to the execution plan.

2. The method of claim 1, wherein the analysis of the plurality of activities comprises identifying a priority assigned to each activity by a developer.

3. The method of claim 1, wherein the analysis of the plurality of activities comprises an analysis of system resources.

4. The method of claim 3, wherein the analysis of system resources comprises identifying that hardware optimized for a particular activity of the plurality of activities has already been assigned to another activity ordering the particular activity below at least one other activity in the execution plan based on the hardware being in use.

5. The method of claim 3, wherein the analysis of system resources comprises identifying a particular activity of the plurality of activities that is optimized for hardware present in the computing system and preferring the particular activity over at least one other activity when ordering the one or more activities into the execution plan based on the presence of the hardware.

6. The method of claim 1, further comprising:

at one or more processors of the computing system, subsequent to executing the workflow, performing a subsequent analysis of the plurality of activities, the subsequent analysis of the plurality of activities comprising an analysis of at least one of the one or more activities in the execution plan that have already executed.

7. The method of claim 6, wherein the subsequent analysis of the plurality of activities comprises an analysis of execution feedback received from the at least one of the one or more activities in the execution plan that have already executed.

8. The method of claim 6, further comprising:

at one or more processors of the computing system, in response to performing the subsequent analysis of the plurality of activities, re-ordering previously ordered activities in the execution plan and reassigning previously assigned resources.

9. The method of claim 8, wherein re-ordering previously ordered activities and reassigning previously assigned resources comprises removing a previously ordered activity from the execution plan and un-assigning resources associated with the activity.

10. The method of claim 6, wherein the subsequent analysis of the plurality of activities comprises an analysis of Boolean propositional satisfyability using activities already executed, and wherein the method further comprises, prior to executing the first activity, removing the first activity from the execution plan and ordering the second activity into the exclusion plan to the exclusion of the first activity.

11. The method of claim 6, wherein the subsequent analysis considers one or more of a number of activities executed or a percentage of activities executed.

12. The method of claim 1, wherein the analysis of the plurality of activities comprises an estimation of time to execute one or more of the plurality of activities.

13. The method of claim 12, wherein the estimation of time to execute one or more of the plurality of activities is based on historical data.

14. The method of claim 12, wherein the estimation of time to execute one or more activities is based on execution feedback from one or more activities.

15. The method of claim 12, wherein the estimation of time to execute one or more of the plurality of activities is based on developer estimate data provided by a developer of an activity.

16. In a computing environment comprising a workflow runtime, a system including programmatic modules configured to optimize workflow execution, the system comprising:

a processor;

a computer readable memory medium comprising computer executable instructions, the computer executable instruction comprising functional modules including;

an analysis module configured to identify a workflow that includes a plurality of activities, and to identify a completion condition defining one or more states of execution of the plurality of activities that represent completion of the workflow; and

a scheduling module configured to, prior to initial execution of the workflow by the processor, develop an optimized execution plan for executing the workflow and to achieve the completion condition, comprising;

identifying the plurality of activities of the workflow that could be executed to satisfy the completion condition, the plurality of activities including a first activity and a second activity that could be alternatively executed to satisfy the completion condition, at least in part; and

ordering one or more activities from the plurality of activities into the execution plan and assigning system resources based on an analysis of activities in the plurality of activities and the completion condition, including ordering the first activity into the exclusion plan to the exclusion of the second activity based on the analysis preferring the first activity over the second activity for satisfying the completion condition.

17. In a computing environment comprising a workflow runtime, a computer readable storage device comprising computer executable instructions configured to optimize workflow execution, the computer readable storage device comprising:

computer executable instructions that when executed by a processor are configured to perform a critical path analysis based on identifying one or more completion conditions defining one or more states of execution of a plurality of activities of a workflow that represent completion of the workflow; and

computer executable instructions that when executed by the processor are configured, prior to initially executing the workflow, to develop an optimized execution plan for executing the workflow to achieve the one or more completion conditions, comprising;

identifying the plurality of activities of the workflow that could be executed to satisfy the one or more completion conditions, the plurality of activities including a first activity and a second activity that could be alternatively executed to satisfy the one or more completion conditions, at least in part; and

ordering an optimized set of activities from the plurality of activities into the optimized execution plan and assign system resources based on an analysis the plurality of activities and the one or more completion conditions, including ordering the first activity into the optimized exclusion plan to the exclusion of the second activity based on the analysis preferring the first activity over the second activity for satisfying the one or more completion conditions; and

computer executable instructions that when executed by the processor are configured, subsequent to developing the optimized execution plan, to execute the workflow according to the optimized execution plan.

18. The computer readable storage device of claim 17, further comprising:

computer executable instructions that when executed by the processor are configured to analyze feedback from executing activities and to modify the optimized execution plan according to the feedback.

19. The computer readable storage device of claim 17, wherein the computer executable instructions that when executed by the processor are configured to perform the critical path analysis, are configured to evaluate system hardware that the workflow will be executing on.

20. The computer readable storage device of claim 17, wherein the computer executable instructions that when executed by the processor are configured to evaluate data provided by a developer of an activity.

21. The computer readable storage device of claim 17, wherein the computer executable instructions that when executed by the processor are configured to evaluate activities in a workflow that has already executed.