Task scheduling method and system

• US 8,893,130 B2
• Filed: 03/26/2007
• Issued: 11/18/2014
• Est. Priority Date: 03/26/2007
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Smith, Gary S., White, Joseph P., Stahlberg, Michael J., Koller, Christopher B.
• Primary Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US11/691,361
• Publication Number:
  US 20080244584A1
• Time in Patent Office: 2,794 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

Provided is a method for scheduling activities. The method includes partitioning tasks provided for scheduling. The partitioning is accomplished by receiving at least one task including at least one data type. The data type is reviewed to determine at least one scheduling criteria and the task is routed to a queue based on the determined scheduling criteria. Each queue also has at least one queue characteristic. The method also includes scheduling the partitioned tasks. The scheduling is accomplished by retrieving the at least one task from the queue in response to a trigger. The retrieved task is routed to at least one scheduler. In a first instance the routing is based on the queue characteristic. In a second instance the routing is based on at least one scheduler characteristic. A scheduling system for performing this method is also provided.

Claims

1. A task scheduling method, comprising:

partitioning tasks provided for scheduling, the partitioning including

receiving at least one task including at least one type of data for schedulable tasks from users, wherein the at least one type of data includes a preferred task implementation time or a geographic location associated with a corresponding task of the tasks;

formatting the task data in a compliant form for schedulers,

reviewing the task data to determine a user-configurable scheduling criteria of at least one data element in the task data, and

routing the task to a queue of a plurality of queues, each queue having a characteristic, based on the determined user-configurable scheduling criteria being consistent with the characteristic of the queue, wherein the characteristic of each queue includes a task implementation time and a task geographic location; and

scheduling the partitioned tasks, the scheduling including

retrieving the at least one task from the queue in response to a trigger,

determining the characteristics of the queues and characteristics of the schedulers, wherein the schedulers include a first scheduler configured to implement a first scheduling algorithm and a second scheduler configured to implement a second scheduling algorithm different from the first scheduling algorithm, the characteristics of the schedulers including speed and precision of scheduling performance of a respective scheduling algorithm implemented by the scheduler, and

routing the at least one task to the first scheduler based upon the queue characteristic being consistent with the, scheduler characteristic of the first scheduler.

2. The scheduling method of claim 1, wherein the trigger is selected from a group consisting of the passage of time, exceeding a threshold of tasks within the queue, a flag attached to the task and combinations thereof.

3. The scheduling method of claim 1, wherein the partitioning is performed by at least one task manager, at least one queue router and at least one queue;

the scheduling performed by at least one schedule manager and at least one scheduler.

4. The scheduling method of claim 3, wherein multiple instantiations of task managers, queue routers, queues, schedule managers and schedulers are operable concurrently.

5. The scheduling method of claim 1, wherein partitioned tasks are scheduled in parallel.

6. The scheduling method of claim 1, wherein the method is stored on a computer-readable medium as a computer program which, when executed by a computer will perform the steps of scheduling tasks.

7. The scheduling method of claim 1, wherein the scheduler is selected from the group consisting of an off-the-shelf solver, randomized algorithms, genetic algorithms, hybrid dynamic programming, English Auction, greedy impact, squeaky wheel optimization, ant colony, simulated annealing, and combinations thereof.

8. A task scheduling system for conserving one or more resources comprising:

a plurality of schedulers for scheduling utilization of the one or more resources, each scheduler having at least one characteristic, wherein the schedulers include a first scheduler configured to implement a first scheduling algorithm and a second scheduler configured to implement a second scheduling algorithm different from the first scheduling algorithm the characteristic of a respective scheduler including speed and precision of scheduling performance of a respective scheduling algorithm implemented by the scheduler;

a task manager operable to accept task data for schedulable tasks from users, the task manager being configured to format the task data in a compliant form for the schedulers, wherein the task data includes a preferred task implementation time or a geographic location associated with a corresponding task of the tasks;

a queue router operable to receive the tasks from the task manager, the queue router reviewing the task data to determine a user-configurable scheduling criteria of at least one data element in the task data;

a plurality of queues, each queue having a characteristic and operable to receive a task of the tasks from the queue router, wherein the characteristic of each queue includes a task implementation time and a task geographic location, the queue router being configured to route the task to a respective queue based upon the determined user-configurable scheduling criteria being consistent with the characteristic of the queue;

a schedule manager operable to determine the characteristics of the queues and characteristics of the schedulers, receive the task from one of the queues and provide the task to one of the schedulers based on the characteristic of the queue being consistent with the characteristic of the scheduler; and

a trigger operable to trigger the schedule manager to retrieve the task from the queue.

9. The scheduling system of claim 8, wherein the trigger is operable in response to an event selected from the group of passage of time, exceeding a threshold of tasks within the queue, a flag attached to the task and combinations thereof.

10. The scheduling system of claim 8, wherein the queue router is further operable to receive a task from the schedule manager, the task having failed to schedule.

11. The scheduling system of claim 8, wherein multiple instantiations of queues, schedule managers and schedulers are operable concurrently.

12. The scheduling system of claim 8, wherein multiple schedulers are operable in parallel.

13. The scheduling system of claim 8, wherein routing the task to a queue includes routing the task to at least one additional router.

14. The scheduling system of claim 8, further including a resource manager operable to maintain the state of resources over time, the resources including elements necessary for the task and elements of the scheduling system available for the scheduling of the task.

15. The scheduling system of claim 8, wherein the system is operable to perform scheduling as a two task process to homogenize the tasks scheduled by a respective scheduler;

task one including partitioning provided tasks for scheduling, the partitioning including;

receiving at least one task including at least one type of data;

reviewing the data to determine at least one scheduling criteria;

routing the task to a queue based on the determined scheduling criteria, the queue having at least one queue characteristic; and

task two including scheduling the partitioned tasks, the scheduling including;

retrieving the at least one task from the queue in response to a trigger; and

routing the at least one task to a scheduler, the scheduler routing being based in a first instance upon the at least one queue characteristic, and in a second instance upon the at least one scheduler characteristic.

16. The scheduling system of claim 15, wherein for a provided set of related tasks, multiple partitioning tasks and scheduling tasks are performed in parallel for at least a subset of the related tasks.

17. A non-transitory computer-readable medium on which is stored a computer program for scheduling tasks, the computer program comprising instructions which, when executed by a computer, perform the steps of:

partitioning tasks provided for scheduling, the partitioning including

receiving at least one task including at least one type of data for scheduling tasks from users, wherein the at least one type of data includes a preferred task implementation time or a geographic location associated with a corresponding task of the tasks;

formatting the task data in a compliant form for schedulers,

reviewing the task data to determine a user-configurable scheduling criteria of at least one data element in the task data, and

routing the task to a queue of a plurality of queues, each queue having a characteristic, based on the determined user-configurable scheduling criteria being consistent with the characteristic of the queue, wherein the characteristic of each queue includes a task implementation time and a task geographic location; and

scheduling the partitioned tasks, the scheduling including

retrieving the at least one task from the queue in response to a trigger,

determining the characteristics of the queues and characteristics of the schedulers, wherein the schedulers include a first scheduler configured to implement a first scheduling algorithm and a second scheduler configured to implement a second scheduling algorithm different from the first scheduling algorithm, the characteristics of the schedulers including speed and precision of scheduling performance of a respective scheduling algorithm implemented by the scheduler, and

routing the at least one task to the first scheduler based upon the queue characteristic being consistent with the, scheduler characteristic of the first scheduler.

18. The computer-readable medium of claim 17, wherein for a provided set of related tasks, multiple partitioning tasks and scheduling tasks are performed in parallel for at least a subset of the related tasks.

19. The computer-readable medium of claim 17, wherein the trigger is selected from a group consisting of the passage of time, exceeding a threshold of tasks within the queue, a flag attached to the task and combinations thereof.

20. The computer-readable medium of claim 17, wherein the partitioning is performed by at least one task manager, at least one queue router and at least one queue;

the scheduling performed by at least one schedule manager and at least one scheduler.

21. The computer-readable medium of claim 17, wherein multiple instantiations of task managers, queue routers, queues, schedule managers and schedulers are operable concurrently.

22. A computer system for scheduling activities comprising:

a processing unit;

a memory storage device coupled to the processing unit;

an input device coupled to the processing unit; and

an output device coupled to the processing unit;

the processing unit being operative to;

partition tasks provided for scheduling, the partitioning including

receive at least one task including at least one type of data for schedulable tasks

from users, wherein the at least one type of data includes a preferred task implementation time or a geographic location associated with a corresponding task of the tasks;

format the task data in a compliant form for schedulers,

review the task data to determine a user-configurable scheduling criteria of at least one data element in the task data, and

route the task to a queue of a plurality of queues, each queue having a characteristic, based on the determined user-configurable scheduling criteria being consistent with the characteristic of the queue, wherein the characteristic of each queue includes a task implementation time and a task geographic location; and

schedule the partitioned tasks, the scheduling including

retrieve the at least one task from the queue in response to a trigger,

determine the characteristics of the queues and characteristics of the schedulers, wherein the schedulers include a first scheduler configured to implement a first scheduling algorithm and a second scheduler configured to implement a second scheduling algorithm different from the first scheduling algorithm, the characteristics of the schedulers including speed and precision of scheduling performance of a respective scheduling algorithm implemented by the scheduler, and

route the at least one task to the first scheduler based upon the queue characteristic being consistent with the, scheduler characteristic of the first scheduler.

23. The computer system of claim 22, wherein for a provided set of related tasks, multiple partitioning tasks and scheduling tasks are performed in parallel for at least a subset of the related tasks.

24. The computer system of claim 22, wherein multiple instantiations of task managers, queue routers, queues, schedule managers and schedulers are operable concurrently.

25. The computer system of claim 22, wherein the partitioning is performed by at least one task manager, at least one queue router and at least one queue;

the scheduling performed by at least one schedule manager and at least one scheduler.