ITERATIVE RESOURCE SCHEDULING

• US 20080215409A1
• Filed: 12/28/2007
• Published: 09/04/2008
• Est. Priority Date: 01/03/2007
• Status: Abandoned Application

• Current Assignee: Victorware LLC
• Original Assignee: Victorware LLC
• Inventors: Van Matre, Brian C.
• Application Number:
  US11/966,756
• Publication Number:
  US 20080215409A1
• 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/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations

Abstract

A request is received to accomplish a task by using a plurality of resources. Once the task is received, attributes of the resources are retrieved from a memory including constraints associated with those resources. These constraints can include hard constraints and soft constraints. A first schedule is then created using a subset of the plurality of resources that complies with each task and resource hard constraint. A score based on the degree of compliance of each soft constraint is determined for the first schedule score. Thereafter the first schedule is modified to form a second schedule, again complying with each hard constraint. A second schedule score is determined associated with the second schedule. These scores are compared so as to determine and select the more optimal schedule. The process continues iteratively until modifications of the schedule no longer yield an improving schedule.

Claims

1. A method for resource scheduling, the method comprising:

receiving a request to accomplish a task by using a plurality of resources;

retrieving from a memory constraints associated with the task, wherein constraints includes hard constraints and soft constraints;

creating a first schedule for use of a subset of the plurality of resources to accomplish the task wherein the first schedule complies with each hard constraint;

determining a first schedule score based on soft constraint compliance by the first schedule;

modifying the first schedule to form a second schedule wherein the second schedule complies with each hard constraint;

determining a second schedule score associated with the second schedule based on soft constraint compliance by the second schedule; and

selecting an optimal schedule by comparing the first schedule score to the second schedule score.

2. The method of claim 1 wherein each of the plurality of resources is associated with resource constraints.

3. The method of claim 1 wherein resource constraints include hard resource constraints and soft resource constraints.

4. The method of claim 1 wherein basis of the first schedule score includes compliance with soft resource constraints.

5. The method of claim 1 wherein basis of the second schedule score includes a degree of compliance with soft resource constraints.

6. The method of claim 5 wherein soft resource constraints include a resource importance indicator.

7. The method of claim 6 wherein the resource importance indicator for each soft resource constraint reflects that soft resource constraint'"'"'s influence on schedule scores.

8. The method of claim 6 wherein a portion of the basis of the first and second schedule score is based on a combination of the resource importance indicator and the degree of compliance of each soft resource constraint of each resource used to accomplish the task.

9. The method of claim 1 wherein hard resource constraints must be complied with for the resource to be scheduled to accomplish the task.

10. The method of claim 1 wherein hard constraints include mandatory task requirements.

11. The method of claim 1 wherein violation of at least one hard constraint will result in schedule failure.

12. The method of claim 1 wherein soft constraints include optional requirements.

13. The method of claim 1 wherein each soft constraint includes an importance indicator.

14. The method of claim 13 wherein the importance indicator for each soft constraint reflects that soft constraint'"'"'s influence on schedule scores.

15. The method of claim 14 wherein a portion of the basis of the first and second schedule score is based on a combination of the importance indicator and a degree of compliance of each soft constraint of each resource used to accomplish the task.

16. The method of claim 1 wherein modifying includes altering the subset of the plurality of resources associated with accomplishing the task.

17. The method of claim 1 wherein modifying includes changing at least one attribute of at least one resource of the subset of plurality of resources associated with accomplishing the task.

18. The method of claim 1 wherein selecting includes the first schedule score exceeding the second schedule score for a predetermined number of modifying iterations.

19. The method of claim 1 further comprising, responsive to the second schedule score exceeding the first schedule score, iteratively replacing the first schedule with the second schedule and repeating the modifying step.

20. The method of claim 19 wherein the task is associated with time including a start time and a duration of time over which the task is accomplished.

21. The method of claim 19 wherein repeating includes altering time associated with the task.

22. The method of claim 19 wherein repeating includes changing the subset of the plurality of resources.

23. The method of claim 19 wherein changing is based on a probability of creating an improved first schedule.

24. A method for resource scheduling, the method comprising:

generating a first schedule for use of a plurality of resources to accomplish a task wherein the first schedule complies with a plurality of requirements and satisfies a degree of desired conditions; and

modifying the first schedule to create a second schedule wherein the degree of satisfied desired conditions of the second schedule as compared to the first schedule is increased while compliance with the plurality of requirements by the second schedule is maintained.

25. The method of claim 24 wherein responsive to the second schedule'"'"'s degree of satisfied desired conditions being larger than the first schedule'"'"'s degree of satisfied desired conditions, replacing the first schedule with the second schedule.

26. The method of claim 25 wherein modifying continues iteratively until the second schedule'"'"'s degree of satisfied desired conditions fails to be larger than the first schedule'"'"'s degree of satisfied desired conditions for a predetermined number of iterations.

27. The method of claim 24 wherein modifying includes changing the plurality of resources used to accomplish the task.

28. The method of claim 24 wherein modifying includes changing an attribute of at least one of the plurality of resources used to accomplish the task.

29. A computer system for resource scheduling, the computer system comprising:

a machine capable of executing instructions embodied as software; and

a plurality of software portions stored in a memory, wherein;

one of said software portions is configured to receive a request to accomplish a task using a plurality of resources;

one of said software portions is configured to retrieve from a memory constraints associated with the task, wherein constraints includes hard constraints and soft constraints;

one of said software portions is configured to create a first schedule for use of a subset of the plurality of resources wherein the first schedule complies with each hard constraint;

one of said software portions is configured to determine a first schedule score based on soft constraint compliance by the first schedule;

one of said software portions is configured to modify the first schedule to form a second schedule wherein the second schedule complies with each hard constraint;

one of said software portions is configured to determine a second schedule score associated with the second schedule based on soft constraint compliance by the second schedule; and

one of said software portions is configured to select an optimal schedule by comparing the first schedule score to the second schedule score.