Workflow job distribution in a data processing system with agent time window constraints

• US 10,031,776 B2
• Filed: 11/21/2016
• Issued: 07/24/2018
• Est. Priority Date: 11/21/2016
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Inventors: Raj, Apurv
• Primary Examiner(s): CAO, DIEM K
• Application Number:
  US15/356,884
• Publication Number:
  US 20180143851A1
• Time in Patent Office: 610 Days
• Field of Search: None
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• 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
• CPC Class Codes: G06F 9/5044 considering hardware capabilities

Abstract

A method of scheduling jobs includes receiving a plurality of jobs that require execution, identifying a plurality of agents that are configured to execute at least one of the plurality of jobs, identifying a plurality of time windows in which the plurality of agents are, available to execute the plurality of jobs, identifying a constraint rule on the execution of the plurality of jobs, and identifying a plurality of possible execution paths. Execution paths that do not comply with the constraint;rule are removed from the plurality of possible execution paths to provide a preferred set of execution paths. The method further includes calculating a metric for each of the preferred set of execution paths, selecting an execution path in response to the metric, and causing the plurality of jobs to be executed by at least one of the agents according to the selected execution path.

Claims

1. A method, comprising:

performing operations as follows on a processor of a computing device;

receiving a plurality of jobs that require execution;

identifying a plurality of agents that are configured to execute at least one of the plurality of jobs;

identifying a plurality of time windows in which the plurality of agents are available to execute the plurality of jobs;

identifying a constraint rule on the execution of the plurality of jobs;

identifying a plurality of possible execution paths, wherein each of the execution paths comprises a possible set of selected ones of the time windows in which respective ones of the plurality of agents in the execution path can execute at least one job of the plurality of jobs and wherein the respective ones of the plurality of agents in the execution path can collectively execute all of the plurality of jobs;

removing execution paths from the plurality of possible execution paths that do not comply with the constraint rule to provide a preferred set of execution paths;

calculating a metric for each of the preferred set of execution paths;

selecting an execution path in response to the metric; and

causing the plurality of jobs to be executed by at least one of the agents according to the selected execution path.

2. The method of claim 1, wherein the metric comprises an execution time, and wherein selecting an execution path in response to the metric comprises selecting an execution path that has a smallest execution time.

3. The method of claim 2, wherein selecting the execution path that has the smallest execution time comprises:

determining an execution time for each execution path in the preferred set of execution paths;

determining an average execution time for each execution path in the preferred set of execution paths; and

discarding execution paths for which the execution time is greater than the average execution time.

4. The method of claim 3, further comprising:

determining agent capacities for each execution path in the preferred set of execution paths;

determining an average agent capacity for each execution path in the preferred set of execution paths; and

discarding execution paths for which the agent loading is greater than the average agent loading.

5. The method of claim 1, wherein the metric comprises an execution completion time, and wherein selecting an execution path in response to the metric comprises selecting an execution path that has an earliest execution completion time.

6. The method of claim 1, wherein the constraint rule comprises a number of concurrently executable jobs by the plurality of agents.

7. The method of claim 1, wherein the constraint rule comprises a start time of a time window, an end time of a time window and/or a network latency between at least two of the plurality of agents.

8. The method of claim 1, wherein the metric comprises an execution path time, wherein the execution path time is calculated as:

ExecutionPathTime=Σ

JobExecTime+Σ

WaitingTime+Σ

NetworkLatency

where Σ

JobExecTime is the sum of execution times of all of the jobs, Σ

WaitingTime is the sum of times between time windows in the execution path and Σ

NetworkLateney is the sum of network latencies between agents in the execution path.

9. The method of claim 1, wherein the constraint comprises a requirement that a start time of a current time window in the execution path is later than a sum of an end time of a previous time window in the execution path plus a network latency between a current agent associated with the current time window and a previous agent associated with the previous time window.

10. The method of claim 1, further comprising:

generating a directed graph having vertices corresponding to the time windows and edges corresponding to transitions between the time windows; and

generating the plurality of possible execution paths as traversals of the directed graph from a start point to an end point.

11. The method of claim 10, wherein generating the plurality of possible execution paths comprises performing a depth first traversal of the directed graph from the start point.

12. A computer program product, comprising:

a non.-transitory computer readable storage medium comprising computer readable program code embodied in the medium that when executed by a processor of a computing device causes the processor to perform operations comprising;

receiving a plurality of jobs that require execution;

identifying a plurality of agents that are configured to execute at least one of the plurality of jobs;

identifying a plurality of time windows in which the plurality of agents are available to execute the plurality of jobs;

identifying a constraint rule on the execution of the plurality of jobs;

identifying a plurality of possible execution paths, wherein each of the execution paths comprises a possible set of selected ones of the time windows in which respective ones of the plurality of agents can execute at least one job of the plurality of jobs and wherein the respective ones of the plurality of agents can collectively execute all of the plurality of jobs;

removing execution paths from the plurality of possible execution paths that do not comply with the constraint rule to provide a preferred set of execution paths;

calculating a metric for each of the preferred set of execution paths;

selecting art execution path in response to the metric; and

causing the plurality of jobs to be executed by at least one of the agents according to the selected execution path.

13. The computer program product of claim 12, wherein the metric comprises an execution time, and wherein selecting an execution path in response to the metric comprises selecting an execution path that has a smallest execution time.

14. The computer program product of claim 13, wherein selecting the execution path that has the smallest execution time comprises:

determining an execution time for each execution path in the preferred set of execution paths;

determining an average execution time for each execution path in the preferred set of execution paths; and

discarding execution paths for which the execution time is greater than the average execution time.

15. The computer program product of claim 14, wherein the program code, further causes the processor to perform operations comprising:

determining agent capacities for each execution path in the preferred set of execution paths;

determining an average agent capacity for each execution path in the preferred set of execution paths; and

discarding execution paths for which the agent loading is greater than the average agent loading.

16. The computer program product of claim 12, wherein the metric comprises an execution completion time, and wherein selecting an execution path in response to the metric comprises selecting an execution path that has an earliest execution completion time.

17. The computer program product of claim 12, wherein the constraint rule comprises a number of concurrently executable jobs by the plurality of agents.

18. The computer program product of claim 12, wherein the constraint rule comprises a start time of a time window, an end time of a time window and/or a network latency between at least two of the plurality of agents.

19. The computer program product of claim 12, wherein the metric comprises an execution path time, wherein the execution path time is calculated as:

ExecutionPathTime=Σ

JobExecTime+Σ

WaitingTime+Σ

NetworkLatency

where Σ

JobExecTime is the sum of execution times of all of the jobs, Σ

WaitingTime is the sum of times between time windows in the execution path and Σ

NetworkLatency is the sum of network latencies between agents in the execution path.

20. The computer program product of claim 12, wherein the constraint comprises a requirement that a start time of a current time window in the execution path is later than a sum of an end time of a previous time window in the execution path plus a network latency between a current agent associated with the current time window and a previous agent associated with the previous time window.