Exploitation of workflow solution spaces to account for changes to resources

• US 8,180,658 B2
• Filed: 01/30/2007
• Issued: 05/15/2012
• Est. Priority Date: 01/30/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hamadi, Youssef, Quimper, Claude-Guy
• Primary Examiner(s): FLEISCHER, MARK A
• Application Number:
  US11/669,064
• Publication Number:
  US 20080183517A1
• Time in Patent Office: 1,932 Days
• Field of Search: 705/7.11, 705/7.13
• US Class Current: 705/7.11
• 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/063 Operations research, analysis or management
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change

Abstract

It is difficult for managers or other operators to decide how best to modify an available pool of resources used for their workflows. Methods for achieving this by improving the robustness of workflows are described. The more robust a workflow, the better its ability to withstand detrimental changes to its associated pool of resources. It is recognized here that the size of the solution space for the problem of allocating resources to tasks in a workflow provides a useful indicator of robustness of a workflow. In general, the greater the size of the solution space the more robust the workflow. A constraint optimization problem is specified for the problem of how best to modify resource characteristics of a pool of resources in order to maximize a size of a solution space. The solution space is that for the problem of allocating resources from the pool to tasks in a workflow.

Claims

1. A method comprising:

under control of one or more processors configured with executable instructions;

accessing objectives associated with execution of a workflow comprising a plurality of tasks that are combined to form the workflow;

accessing information about a solution space, the solution space being for allocation of resources from a resource pool to tasks in the workflow in view of policy information;

specifying a constraint optimization problem to find target resource characteristics for resources of the resource pool, the constraint optimization problem being specified such that the allocation of resources is based in part on assigning tasks to a worker that has not used a required skill set within a specified period of time;

sending the specified constraint optimization problem to a constraint programming problem solver;

receiving a response comprising target resource characteristics for resources of the resource pool; and

storing the target resource characteristics in memory.

2. A method as claimed in claim 1 which further comprises accessing cost information comprising, for each resource in the resource pool, a cost associated with making a specified change to a resource characteristic of that resource.

3. A method as claimed in claim 1 wherein the accessed information about objectives comprises information about a budget for changing resource characteristics of resources in the resource pool.

4. A method as claimed in claim 2 wherein the accessed information about objectives comprises information about a budget for changing resource characteristics of resources in the resource pool.

5. A method as claimed in claim 3 wherein the budget is a training budget for changing skill levels of human resources in the resource pool.

6. A method as claimed in claim 1 wherein the step of accessing information about the solution space is carried out after the associated allocation of resources from a resource pool to tasks in the workflow.

7. A method as claimed in claim 1 wherein the step of specifying the constraint optimization problem comprises specifying at least one constraint on the basis of the structure of the workflow.

8. A method as claimed in claim 1 which is carried out at an analysis tool in communication with a workflow engine having a constraint programming problem solver and wherein the information about the solution space is accessed from the workflow engine and wherein the specified constraint optimization problem is sent to the constraint programming problem solver at the workflow engine.

9. A method as claimed in claim 1 which is carried out at an analysis tool connected to a workflow engine having a constraint programming problem solver and wherein the step of accessing information about the solution space comprises using the workflow engine to allocate resources to tasks of the workflow such that the associated solution space is identified.

10. A method comprising:

under control of one or more processors configured with executable instructions;

accessing objectives associated with execution of a workflow comprising a plurality of tasks;

computing information about a constraint programming solution space, the solution space being for allocation of resources from a resource pool to tasks in the workflow in view of policy information;

accessing cost information comprising, for each resource in the resource pool, a plurality of costs associated with making changes to resource characteristics of each resource and a budget for changing resource characteristics of resources in the resource pool;

specifying a constraint optimization problem to find target resource characteristics for resources of the resource pool, that constraint optimization problem being specified such that the allocation of resources is based in part on assigning tasks to a worker that has not used a required skill set within a specified period of time;

using a constraint programming problem solver to find a solution to the specified constraint optimization problem comprising target resource characteristics for resources of the resource pool; and

storing the target resource characteristics in memory.

11. A method as claimed in claim 10 wherein the step of computing information about the constraint programming solution space is carried out after the associated allocation of resources from a resource pool to tasks in the workflow.

12. A method as claimed in claim 10 wherein the step of specifying the constraint optimization problem comprises specifying at least one constraint on the basis of the structure of the workflow.

13. A system comprising:

an interface arranged to access information about objectives associated with execution of a workflow comprising a plurality of tasks, the interface also being arranged to access information about a solution space, that solution space being for allocation of resources from a resource pool to tasks in the workflow in view of specified policy information;

a processor arranged to specify a constraint optimization problem to find target resource characteristics for resources of the resource pool, the processor being arranged to specify the constraint optimization problem such that the allocation of resources is based in part on assigning tasks to a worker that has not used a required skill set within specified a period of time;

the interface being arranged to send the specified constraint optimization problem to a constraint programming problem solver and receiving a response comprising target resource characteristics for resources of the resource pool; and

a memory arranged to store the target resource characteristics.

14. The system as claimed in claim 13 further comprising a workflow engine having a constraint programming problem solver.

15. The system as claimed in claim 14 wherein the interface is arranged to access information about the solution space from the workflow engine and wherein the interface is arranged to send the specified constraint optimization problem to the constraint programming problem solver.

16. The system as claimed in claim 13 wherein the interface is arranged to be connected to a workflow engine having a constraint programming problem solver.