TASK SCHEDULING METHOD

• US 20080244584A1
• Filed: 03/26/2007
• Published: 10/02/2008
• 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., Koller, Christopher B., Stahlberg, Michael J.
• Granted Patent: US 8,893,130 B2
• Time in Patent Office: Days
• 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;

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

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.

2. The scheduling method of claim 1, wherein the data is selected from the group consisting of a designated priority, a life span, a preferred implementation time, a geographic location, a complexity level, a resource requirement, a scheduling time budget, a precedence indicator, a separator, and combinations thereof.

3. 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.

4. The scheduling method of claim 1, wherein for each queue the queue characteristic is selected from the group consisting of task urgency, task geographic location, task complexity, task resources, and combinations thereof.

5. 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.

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

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

8. 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.

9. 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.

10. A scheduling system comprising:

a queue router operable to receive a task having at least one type of data, the queue router reviewing the data to determine at least one scheduling criteria and routing the task to a queue based upon the determined scheduling criteria;

a queue operable to receive the task from the queue router and provide the task to a schedule manager, the queue having at least one characteristic;

a schedule manager operable to retrieve the task from the queue and provide the task to a scheduler;

a scheduler having at least one characteristic, the scheduler operable to receive the task from the schedule manager; and

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

11. The scheduling system of claim 10, wherein the schedule manager routes the retrieved task to a scheduler based on the at least one characteristic of the queue.

12. The scheduling system of claim 10, wherein the schedule manager routes the retrieved task to a scheduler based on the characteristic of the scheduler.

13. The scheduling system of claim 12, 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

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

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

16. The scheduling system of claim 10, wherein multiple scheduler'"'"'s are operable in parallel.

17. The scheduling system of claim 10, wherein the queue router further includes a task manager, the task manager operable to receive the task, confirm compliance of the task and task data to predetermined parameters, and provide the confirmed task and task data to the queue router.

18. The scheduling system of claim 17, wherein the task manager is operable to translate the task data to a scheduler compliant format.

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

20. The scheduling system of claim 10, 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.

21. The scheduling system of claim 10, wherein the system is operable to perform scheduling as a two task process;

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.

22. The scheduling system of claim 21, 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.

23. A 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;

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

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.

24. The computer-readable medium of claim 23, 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.

25. The computer-readable medium of claim 23, the data is selected from the group consisting of a designated priority, a life span, a preferred implementation time, a geographic location, a complexity level, a resource requirement, a scheduling time budget, a precedence indicator, a separator, and combinations thereof.

26. The computer-readable medium of claim 23, 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.

27. The computer-readable medium of claim 23, for each queue the queue characteristic is selected from the group consisting of task urgency, task geographic location, task complexity, task resources, and combinations thereof.

28. The computer-readable medium of claim 23, 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.

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

30. 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;

partitioning tasks provided 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

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.

31. The computer system of claim 30, 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.

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

33. The computer system of claim 30, wherein the data is selected from the group consisting of a designated priority, a life span, a preferred implementation time, a geographic location, a complexity level, a resource requirement, a scheduling time budget, a precedence indicator, a separator, and combinations thereof.

34. The computer system of claim 30, 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.