Quality of service aware scheduling for composite web service workflows

• US 9,020,829 B2
• Filed: 05/07/2008
• Issued: 04/28/2015
• Est. Priority Date: 05/07/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Li, Wen-Syan, Phan, Thomas
• Primary Examiner(s): Pats, Justin M
• Assistant Examiner(s): CHOY, PAN G
• Application Number:
  US12/116,812
• Publication Number:
  US 20090281818A1
• Time in Patent Office: 2,547 Days
• Field of Search: 705/7.12, 705/7.13
• US Class Current: 705/7.12
• 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:

sending a web service request from a requesting computer to a first network;

sending the web service request from the first network to a network server;

sending the web service request from the network server to an application server;

performing by a computer processor on the application server;

decomposing, by the computer processor, a web service request received by the application server from the first network into a plurality of workflows;

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

associating, by the computer processor, a plurality of web service types with each of the plurality of business processes, wherein the web service types describe one of the plurality of web service providers;

assigning, by the computer processor, a business value including average completion time of one of the business processes to each of the plurality of business processes;

evaluating, by the computer processor, the plurality of web service types with respect to the business value of each of the plurality of business processes;

maximizing, by the computer processor, the business value for one of the plurality of business processes by selecting one of the plurality of business processes;

creating, by the computer processor, an aggregated business process by combining partially completed ones of the plurality of business processes with an unstarted one of the plurality of business processes;

queueing, by the computer processor, the plurality of business processes for execution, in response to the queueing, searching for an assignment of said plurality of business processes and the aggregated business process to said plurality of service providers based on a minimum completion time for executing the web service request across all service providers, wherein the searching further comprises solving a combinatorial optimization problem utilizing a genetic search algorithm comprising;

selecting initial chromosomes, wherein a chromosome is an assignment of one of the plurality of business processes to one of the plurality of service providers;

mutating the selected chromosomes responsive to a mutation rate, wherein the selected chromosomes mutate only when a random number generator provides a non-negative integer that is less than or equal to a current number of the plurality of workflows; and

iteratively,

recombining the mutated chromosomes;

evaluating a cost for recombined chromosomes;

selecting recombined chromosomes with a lowest value of the cost;

until all the workflows have been evaluated;

performing, by the computer processor, those of the plurality of workflows that are independent of each other in non-sequential order using the assigned one of said plurality of service providers;

adjusting, by the computer processor, workload for one of the plurality of workflows among the plurality of service providers by balancing the workload for the one of the plurality of workflows on a plurality of web servers based on a maximum concurrency of the plurality of workflows, wherein for workloads that exceed the maximum concurrency, an expected average completion time for the workload varies with expected completion time, workload size, and average performance under workload;

categorizing, by the computer processor, a first one of the plurality of workflows as a success when a completion time of the one of the plurality of workflows is less than a predetermined quality value; and

categorizing, by the computer processor, a second one of the plurality of workflows as a failure when the completion time of the one of the plurality of workflows is greater than a constant times the predetermined quality value, and

outputting, by the computer processor, the plurality of business processes to a second network.

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 including one of:

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

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

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

8. The method of claim 1, wherein the selecting of initial chromosomes is selecting at random.

9. The method of claim 1, 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.

10. The method of claim 9, further comprising:

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

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

12. A computer program product for assigning a web service request to a plurality of service providers, the computer program product comprising:

a non-transitory computer readable storage medium on an application server computer having computer readable program code embodied therewith, when executed by a computer processor causes the computer processor to receive computer executable instructions from a first network, and causes the computer processor to perform the steps comprising;

decomposing a web service request into a plurality of workflows, wherein the web service request is received from a requesting computer through a first network to a network server, and from the network server to the application server computer;

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

associating a plurality of web service types with each of the plurality of business processes, wherein the web service types describe one of the plurality of service providers;

assigning a business value including average completion time to each of the plurality of business processes;

evaluating the plurality of web service types with respect to the business value of each of the plurality of business processes;

maximizing the business value for one of the plurality of business processes by selecting one of the plurality of web service types for one of the plurality of business processes;

creating an aggregated business process by combining partially completed ones of the plurality of business processes with an unstarted one of the plurality of business processes;

queueing the plurality of business processes for execution, in response to the queueing, searching for an assignment of said plurality of business processes and the aggregated business process to said plurality of service providers based on a minimum completion time for executing the web service request across all of the plurality of service providers, wherein the searching further comprises solving a combinatorial optimization problem utilizing a genetic search algorithm comprising;

selecting initial chromosomes wherein a chromosome is an assignment of one of the plurality of business processes to one of the plurality of service providers;

mutating the selected chromosomes responsive to a mutation rate, wherein the selected chromosomes mutate only when a random number generator provides a non-negative integer that is less than or equal to a current number of the plurality of workflows; and

iteratively,

recombining the mutated chromosomes;

evaluating a cost for the recombined chromosomes;

selecting recombined chromosomes with lowest value of the cost;

until all the workflows have been evaluated;

performing the plurality of workflows that are independent of each other in non-sequential order;

adjusting workload for one of the plurality of workflows and balancing the workload on a plurality of web servers based on a maximum concurrency of the plurality of workflows, wherein for workloads that exceed the maximum concurrency of the plurality of workflows, an expected average completion time for the workload varies with expected completion time, workload size, and average performance under workload;

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

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

wherein the computer processor is configured to output the plurality of business processes to a second network.

13. The computer program product of claim 12, wherein at least one of said service providers provides more than one web service type.

14. The computer program product of claim 12, wherein at least one of said service providers offers a plurality of tiers of service.

15. The computer program product of claim 12, wherein the plurality of workflows includes non-sequential workflows.

16. The computer program product of claim 12, wherein the searching is performed using a genetic search algorithm.

17. The computer program product of claim 12, wherein the searching is performed using one of:

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

18. The computer program product of claim 12, wherein the plurality of workflows includes at least one conditional workflow.

19. The computer program product of claim 16, wherein the selecting of initial chromosomes is selecting at random.

20. The computer program product of claim 12, that includes:

computer readable program code configured to accept a plurality of input workflows and an initial mapping of the plurality of business processes to the service providers;

computer readable program code configured to an initialize variables including initializing the overall business value;

computer readable program code configured to assign the plurality of business processes to the plurality of service providers;

computer readable program code configured to calculate completion times for the plurality of workflows; and

iteratively,

increments completion times for the plurality of workflows;

categorizes workflow completion times for the plurality of workflows; and

increments the business value for the plurality of workflows;

until the plurality of workflows has been processed.

21. The computer program product of claim 12, further comprising:

computer readable program code configured to increase said mutation rate when chromosomes under evaluation fail to improve the overall business value.

22. The computer program product of claim 12, wherein the searching is responsive to a service provider'"'"'s method of queuing business processes for execution.

23. An electronic commerce system comprising:

a requesting computer configured to send a web service request with respect to a web service through a first network to a network server computer;

an application server computer configured to support the web service;

the network server computer configured to output computer executable instructions from the first network to the application server computer;

a memory device configured to store the computer executable instructions, that when stored on the application server computer and executed by the application server computer, the computer executable instructions comprise;

a decomposition module that is configured to decompose a web service request into a plurality of workflows;

an analysis module that is configured to analyze the plurality of workflows using a computer to determine a plurality of business processes;

an association module that is configured to associate a plurality of web service types with each of the plurality of business processes;

an assignment module that is configured to assign a business value including average completion time to each of the plurality of business processes;

an evaluation module configured to select one of the plurality of web service types for each of the plurality of business processes, and maximize the business value for one of the plurality of business processes by selecting one of the plurality of web service types for one of the plurality of business processes;

an aggregation module configured to create an aggregated business process by combining partially completed ones of the plurality of business processes with an unstarted one of the plurality of business processes;

a search module that is configured to queue the plurality of business processes for execution, in response to the queue, searching for an assignment of said plurality of business processes and the aggregated business process to a plurality of service providers based on a minimum completion time executing the web service request across all the plurality of service providers, wherein the searching further includes solving a combinatorial optimization problem utilizing a genetic search algorithm comprising;

selecting initial chromosomes, wherein a chromosome is an assignment of one of the plurality of business processes to one of the plurality of service providers;

mutating the selected chromosomes responsive to a mutation rate, wherein the selected chromosomes mutate only when a random number generator provides a non-negative integer that is less than or equal to a current number of the plurality of workflows; and

iteratively,

recombining the mutated chromosomes;

evaluating a cost for the recombined chromosomes;

selecting recombined chromosomes with lowest value of the cost;

until all the workflows have been evaluated;

a performance module that is configured to perform the plurality of workflows that are independent of each other in non-sequential order, wherein the performance module performs workload balancing by performing the plurality of workflows among a plurality of web servers in a balanced manner;

an adjustment module that is configured to adjust workload for one of the plurality of workflows based on a maximum concurrency of the plurality of workflows, wherein for workloads that exceed the maximum concurrency, an expected average completion time for the workload varies with expected completion time, workload size, and average performance under workload;

a categorization module that is configured to categorize a first one of the plurality of workflows as a success when a completion time of the one of the plurality of workflows is less than a predetermined quality value; and

the categorization module further is configured to categorize a second one of the plurality of workflows as a failure when the completion time of the one of the plurality of workflows is greater than a constant times the predetermined quality value,

wherein the performance module outputs the plurality of business processes for execution on a second network.

24. The electronic system of claim 23, wherein at least one of said plurality of service providers provides more than one web service type.

25. The electronic system of claim 23, wherein at least one of said plurality of service providers offers a plurality of tiers of service, wherein decreasing a number of business processes for each of the plurality of workflows results in an increased aggregate business value.