Scheduler

• US 20060173723A1
• Filed: 01/28/2005
• Published: 08/03/2006
• Est. Priority Date: 01/28/2005
• Status: Abandoned Application

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Fisher, David Charles
• Application Number:
  US11/045,419
• Publication Number:
  US 20060173723A1
• Time in Patent Office: Days
• US Class Current: 705/8
• 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/06314 Calendaring for a resource

Abstract

Provided is a method for scheduling activities. The method includes receiving an activity having a designated priority, a life span, a preferred implementation time, and a scheduling time budget. The schedule is searched to determine the availability of the preferred implementation time and amount of available execution time. The activity is inserted in the schedule if the preferred implementation time if the time is available and life span is less than or equal to available execution time. If the implementation time is unavailable or the life span is greater than the available execution time, the schedule is modified. Modification of the schedule preserves scheduled activities with equal or higher priority. The method will exit when the activity is scheduled or the elapsed scheduling time exceeds the scheduling time budget.

Claims

1. A method for scheduling activities comprising the steps of:

receiving an activity having a designated priority, a life span, a preferred implementation time, and a scheduling time budget;

searching the schedule to. determine the availability of the preferred implementation time and amount of available execution time;

inserting the activity at the preferred implementation time if the time is available and life span is less than or equal to available execution time;

a method for modifying the schedule in response to the implementation time being unavailable or the life span being greater than the available execution time, the method preserving scheduled activities with equal or higher priority; and

exiting the method when elapsed scheduling time exceeds the scheduling time budget.

2. The scheduling method of claim 1, wherein the method for modifying the schedule includes:

randomly selecting an alternative implementation time;

querying the alternative time to determine quantity of available execution time and the presence of a blocking activity;

requesting, in response to the determination of a blocking activity, the blocking activity to move to a different implementation time in the schedule and increase available execution time;

comparing the available execution time to the life span of the activity;

inserting the activity at the randomly selected alternative implementation time when the life span is less than or equal to the available execution time; and

repeating the random selection of an alternative implementation time when the available time is less than the life span until the activity is inserted or elapsed scheduling time exceeds the scheduling time budget.

3. The scheduling method of claim 1, wherein the activity further has at least one designated resource need.

4. 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 activities.

5. A computer-implemented method for scheduling activities comprising the steps of:

receiving an activity having a designated priority, a life span, a preferred implementation time, and a scheduling time budget;

searching the schedule to determine the availability of the preferred implementation time and the quantity of available execution time;

inserting the activity at the preferred implementation time if the time is available and the life span is less than or equal to the available execution time;

initiating, in response to the implantation time being unavailable or the life span being greater than the available execution time, a schedule modification, the schedule modification including;

randomly selecting an alternative implementation time;

querying the alternative time to determine quantity of available execution time and the presence of a blocking activity;

requesting, in response to the determination of a blocking activity, the blocking activity to move to a different implementation time in the schedule and increase available execution time;

comparing the available execution time to the life span of the activity;

inserting the activity at the randomly selected alternative implementation time when the life span is less than or equal to the available execution time; and

repeating the random selection of an alternative implementation time when the available time is less than the life span until the activity is inserted or elapsed scheduling time exceeds the scheduling time budget.

6. The computer-implemented scheduling method of claim 5, wherein the schedule modification is recursive.

7. The computer-implemented scheduling method of claim 5, wherein scheduled activities with equal or higher priority are preserved within the schedule.

8. The computer-implemented scheduling method of claim 5, wherein the priority of the new activity is assumed by the blocking activity requested to move if the blocking activity has a greater priority, the blocking activity with assumed priority initiating a schedule modification.

9. The computer-implemented scheduling method of claim 5, wherein multiple instantiations of schedule modification occur substantially concurrently.

10. The computer-implemented scheduling method of claim 5, wherein the scheduling time budget is divided into at least two portions, and wherein lower priority blocking activities are marked when encountered in the first portion, marked lower priority blocking activities are deleted in the second portion.

11. The computer-implemented scheduling method of claim 5, wherein each blocking activity moved is remembered as to its original implementation time, each moved blocking activity being restored to its original implantation time as best as possible following insertion of the activity.

12. The computer-implemented scheduling method of claim 5, wherein each blocking activity moved is remembered as to its original implementation time, each moved blocking activity being restored to its original implantation time when elapsed scheduling time exceeds scheduling budget time.

13. The computer-implemented scheduling method of claim 5, wherein the life span includes a minimum life duration and a maximum life duration.

14. The computer-implemented scheduling method of claim 13, wherein activities are inserted for their minimum life duration.

15. The computer-implemented scheduling method of claim 13, further including fluffing activities towards maximum life duration.

16. A computer-readable medium on which is stored a computer program for adding activities to a schedule, the computer program comprising instructions which, when executed by a computer, perform the steps of:

receiving an activity having a designated priority, a life span, a preferred implementation time, and a scheduling time budget;

searching the schedule to determine the availability of the preferred implementation time and the quantity of available execution time;

inserting the activity at the preferred implementation time if the time is available and the life span is less than or equal to the available execution time;

initiating, in response to the implantation time being unavailable or the life span being greater than the available execution time, a schedule modification, the schedule modification including;

randomly selecting an alternative implementation time;

querying the alternative time to determine quantity of available execution time and the presence of a blocking activity;

requesting, in response to the determination of a blocking activity, the blocking activity to move to a different implementation time in the schedule and increase available execution time;

comparing the available execution time to the life span of the activity;

inserting the activity at the randomly selected alternative implementation time when the life span is less than or equal to the available execution time; and

repeating the random selection of an alternative implementation time when the available time is less than the life span until the activity is inserted or elapsed scheduling time exceeds the scheduling time budget.

17. The computer-readable medium of claim 16, wherein the schedule modification is recursive.

18. The computer-readable medium of claim 16, wherein scheduled activities with equal or higher priority are preserved within the schedule.

19. The computer-readable medium of claim 16, wherein the priority of the new activity is assumed by the blocking activity requested to move if the blocking activity has a greater priority, the blocking activity with assumed priority initiating a schedule modification.

20. The computer-readable medium of claim 16, wherein multiple instantiations of schedule modification occur substantially concurrently.

21. The computer-readable medium of claim 16, wherein the scheduling time budget is divided into at least two portions, and wherein lower priority blocking activities are marked when encountered in the first portion, marked lower priority blocking activities are deleted in the second portion.

22. The computer-readable medium of claim 16, wherein each blocking activity moved is remembered as to its original implementation time, each moved blocking activity being restored to its original implantation time as best as possible following insertion of the activity.

23. The computer-readable medium of claim 16, wherein each blocking activity moved is remembered as to its original implementation time, each moved blocking activity being restored to its original implantation time when elapsed scheduling time exceeds scheduling budget time.

24. The computer-readable medium of claim 16, wherein the life span includes a minimum life duration and a maximum life duration.

25. The computer-readable medium of claim 24, wherein activities are inserted for their minimum life duration.

26. The computer-readable medium of claim 24, further including fluffing activities towards maximum life duration.

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

an output device coupled to the processing unit;

the processing unit being operative to;

receiving an activity having a designated priority, a life span, a preferred implementation time, and a scheduling time budget;

searching the schedule to determine the availability of the preferred implementation time and the quantity of available execution time;

inserting the activity at the preferred implementation time if the time is available and the life span is less than or equal to the available execution time;

initiating, in response to the implantation time being unavailable or the life span being greater than the available execution time, a schedule modification, the schedule modification including;

randomly selecting an alternative implementation time;

querying the alternative time to determine quantity of available execution time and the presence of a blocking activity;

requesting, in response to the determination of a blocking activity, the blocking activity to move to a different implementation time in the schedule and increase available execution time;

comparing the available execution time to the life span of the activity;

inserting the activity at the randomly selected alternative implementation time when the life span is less than or equal to the available execution time; and

repeating the random selection of an alternative implementation time when the available time is less than the life span until the activity is inserted or elapsed scheduling time exceeds the scheduling time budget.

28. The computer system of claim 27, wherein the schedule modification is recursive.

29. The computer system of claim 27, wherein scheduled activities with equal or higher priority are preserved within the schedule.

30. The computer system of claim 27, wherein the priority of the new activity is assumed by the blocking activity requested to move if the blocking activity has a greater priority, the blocking activity with assumed priority initiating a schedule modification.

31. The computer system of claim 27, wherein multiple instantiations of schedule modification occur substantially concurrently.

32. A computer-readable medium on which is stored a computer program for adding activities to a schedule, the computer program comprising:

an input routine operatively associated with an input device for permitting a user to enter an activity, the user specifying a priority, a life span, a preferred implementation time, and a scheduling time budget for the activity;

a search routine for searching a schedule file to determine availability of the preferred implementation time or an alternative implementation time, the quantity of available execution time, and the possible presence of a blocking activity;

an insertion routine to insert the activity at the determined available preferred implementation time or the alternative implementation time when available execution time is equal to or greater than the life span;

a relocation routine operating in response to the determination of a blocking activity scheduled proximate to the preferred implementation time or the alternative implementation time to relocate a blocking activity to an alternative implementation time;

a randomizing routine for selecting an alternative implementation time for the activity or a blocking activity, the randomizing routine invoked by the relocation routine;

a timing routine for comparing elapsed scheduling time to the scheduling time budget and ending the program execution when elapsed scheduling time exceeds the scheduling time budget.

33. The computer-readable medium of claim 32, wherein the program is recursive.

34. The computer-readable medium of claim 32, wherein multiple instantiations of the routines execute substantially concurrently.

35. The computer-readable medium of claim 32, wherein scheduled activities with equal or higher priority are preserved within the schedule.

36. The computer-readable medium of claim 32, further including a deletion routine operating to delete a lower priority blocking activity scheduled proximate to a preferred implementation time or an alternative implementation time.

37. The computer-readable medium of claim 32, further including a tracking routine to track the original implementation time of each relocated activity;

and a cleanup routine operating to restore each relocated activity to approximately each original implementation time.