QUALITY OF SERVICE AWARE SCHEDULING FOR COMPOSITE WEB SERVICE WORKFLOWS

• US 20090281818A1
• Filed: 05/07/2008
• Published: 11/12/2009
• Est. Priority Date: 05/07/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: PHAN, THOMAS, LI, WEN-SYAN
• Granted Patent: US 9,020,829 B2
• Time in Patent Office: Days
• US Class Current: 705/301
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• 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/103 Workflow collaboration or project management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A method of assigning web service requests to service providers includes searching for an optimal assignment from all possible assignments using a genetic algorithm (GA) that represents possible assignments as chromosomes, and converging towards an assignment of web service request to service providers that maximizes overall business value for all workflows to the service providers. An adaptive mutation scheme is used to introduce mutation into populations of chromosomes. The mutation scheme includes a mutation rate that increases when chromosomes under evaluation fail to improve its workload against the metric over a certain number of generations.

Claims

1. A computer-implemented method of assigning a web service request to a plurality of service providers comprising:

decomposing a web service request into a plurality of workflows;

analyzing the plurality of workflows using a computer to determine a plurality of business processes;

associating a web service type with each of the plurality of business processes;

assigning a business value to each of the plurality of business processes;

searching for an optimal assignment of said plurality of business processes to said plurality of service providers, said optimal assignment responsive to an overall business value of executing the web service request, wherein the searching further includes solving a combinatorial optimization problem;

categorizing a first one of the plurality of workflows as a success if a completion time of the one of the plurality of workflows is less than a predetermined quality of service value; and

categorizing a second one of the plurality of workflows as a failure if the completion time of the one of the plurality of workflows is greater than a constant times the predetermined quality of service value.

2. The method of claim 1, wherein at least one of said service providers provides more than one web service type.

3. The method of claim 1, wherein at least one of said service providers offers a plurality of tiers of service.

4. The method of claim 1, wherein the plurality of workflows includes non-sequential workflows.

5. The method of claim 1, wherein the searching is performed using a genetic search algorithm.

6. The method of claim 1, wherein the searching is performed using one of:

a greedy algorithm, a round-robin algorithm or a random-proportional algorithm.

7. The method of claim 1, wherein the plurality of workflows includes at least one nested workflow.

8. The method of claim 1, wherein the plurality of workflows includes at least one conditional workflow.

9. The method of claim 5, wherein the genetic search algorithm comprises:

selecting initial chromosomes;

mutating chromosomes responsive to a mutation rate; and

iteratively,

recombining chromosomes;

evaluating a cost for chromosomes;

selecting chromosomes with lowest value of the cost;

until all the workflows have been evaluated.

10. The method of claim 9, wherein the selecting of initial chromosomes is selecting at random.

11. The method of claim 9, wherein the evaluating chromosomes comprises:

accepting a plurality of input workflows and an initial mapping of the plurality of business processes to the service providers;

initializing variables including initializing the overall business value;

assigning the plurality of business processes to the plurality of service providers;

calculating completion times for the plurality of workflows; and

iteratively,

incrementing completion times for the plurality of workflows;

categorizing workflow completion times for the plurality of workflows; and

incrementing the business value for the plurality of workflows;

until the plurality of workflows has been processed.

12. The method of claim 11, further comprising:

increasing said mutation rate when chromosomes under evaluation fail to improve the overall business value.

13. The method of claim 11, wherein the searching is responsive to a service provider'"'"'s method of queuing business processes for execution.

14. A computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to execute a scheduling process for assigning web service requests to a plurality of service providers, said computer program product including:

computer usable program code for decomposing the web service request into a plurality of workflows and a plurality of business processes;

computer usable program code for generating a plurality of mappings between the plurality of business processes and a plurality of web service types;

computer usable program code for assigning a plurality of business values;

computer usable program code for searching for an optimal assignment of the plurality of business processes to a plurality of service providers;

computer usable program code for determining a predetermined quality of service upper bound for average execution time of each of the plurality of web service types;

computer usable program code for determining an increased estimate of execution time based on historical averages of service delays; and

wherein said optimal assignment is responsive to an overall business value calculated using the plurality of business values.

15. The computer program product of claim 14, further comprising;

computer usable program code for accepting a plurality of quality of service agreements for the plurality of web service types from the plurality of service providers.

16. The computer program product of claim 14, further comprising

computer usable program code for communicating with an application server;

and

computer usable program code for communicating with a database server.

17. The computer program product of claim 14, further comprising;

computer usable program code for classifying said plurality of workflows in one of sequential or non-sequential classes.

18. The computer program product of claim 14, further comprising;

computer usable program code for searching for the optimal assignment using one or more of;

a genetic search algorithm, a greedy algorithm, a round-robin algorithm or a random-proportional algorithm.

19. The computer program product of claim 18, wherein the genetic search algorithm comprises:

selecting initial chromosomes; and

iteratively,

recombining chromosomes;

evaluating a cost for chromosomes;

selecting chromosomes with lowest value of the cost;

until all the workflows have been evaluated.

20. The computer program product of claim 19, further comprising

computer usable program code for accepting a plurality of input workflows and an initial mapping of the plurality of business processes to the service providers;

computer usable program code for computing an initial overall business value responsive to the initial mapping;

computer usable program code for calculating candidate assignments of the plurality of business processes to the plurality of service providers;

computer usable program code for calculating completion times for the plurality of workflows; and

computer usable program code for iteratively,

incrementing completion times for the plurality of workflows;

comparing the completion times with a plurality of quality of service agreements; and

incrementing the business value for the plurality of workflows;

until the plurality of workflows has been processed.

21. An electronic commerce system comprising:

a web server for receiving a web service request; and

a plurality of service providers'"'"' servers;

wherein the web server is configured to execute a request assignment program;

the request assignment program comprising;

a decomposition module for decomposing the web service request into a plurality of business processes;

an assignment module for calculating an optimal assignment of the plurality of business processes to the plurality of service providers'"'"' servers to minimize an overall business value of executing the web service request;

a calculation module for calculating completion times for each of the plurality of service providers based on a plurality of service agreements between the plurality of business processes and the plurality of service providers;

an equivalency module for determining equivalency of a plurality of service provider types for service determined to be equivalent based on an agreement between business processes and the plurality of service providers;

a utilization module for utilizing an equivalent service provider type in place of one of the plurality of service provider types; and

wherein the overall business value is responsive to sum of duration of execution of all business processes of the web service request.

22. The system of claim 21, wherein the calculating comprises:

selecting a first candidate assignment of the plurality of business processes to the plurality of service providers'"'"' servers;

selecting a second candidate assignment from the first candidate assignment by using an optimization algorithm; and

iterating the optimization algorithm over all business processes of the web service request.

23. The system of claim 22, wherein the optimization algorithm is a genetic search algorithm that uses mutation.