Probabilistic scheduling

Claim 2

A computer-implemented method comprising: receiving a plurality of task containers, each said task container representing a task to be scheduled at a computer, where each said task container includes a grouping of a plurality of resources containers, wherein each said resource container includes resource information that specifies one or more resources required for the represented task and selection criteria to select from the one or more resources, and wherein each said task container further includes an interface function that, when called, determines a pair-wise probability that the task represented by another task container will influence the task represented by the called task container based on a current schedule state of scheduled tasks, selection criteria specified in resource containers of the another task container, and selection criteria specified in resource containers of the called task container; generating a total cost for each task based on pair-wise costs for each task calculated from determined pair-wise probabilities that the task will influence each other task in the plurality of task containers; and scheduling the task with the least total cost.

Claim 3

A method as recited in claim 1 wherein the each selection criteria specifies a relationship selected from a group consisting of: an “AND” relationship indicating that all of a plurality of the resources are required to complete the represented task; an “XOR” relationship indicating that only one of the one or more resources is required to complete the represented task; and an “OR” relationship indicating that one or more of the resources are required to complete the represented task.

Claim 4

A method as recited in claim 1 further comprising: receiving a timeslot definition associated with each of the plurality of tasks or resources, the timeslot definition defining a required timeslot for the associated task or resource.

Claim 5

A method as recited in claim 3 wherein the timeslot definition comprises an early start indicator, a late finish indicator, and a duration indicator.

Claim 6

A method as recited in claim 1 further comprising: receiving a constraint describing a time constraint between two tasks in the plurality of tasks; and scheduling the two tasks based on the constraint.

Claim 7

A method as recited in claim 1 further comprising: determining the pair-wise probability for a pair of tasks that a first task in the pair of tasks influences a second task in the pair of tasks based on the resource information; and adjusting the pair-wise cost of the pair of tasks based on a function of the pair-wise probability that the first task in the pair of tasks influences the second task in the pair of tasks.

Claim 8

A method as recited in claim 1 further comprising: determining the pair-wise probability for a pair of tasks that a first task in the pair of tasks supports a second task in the pair of tasks based on the resource information; and if the first task supports the second task, reducing the pair-wise cost of the pair of tasks based on a function of the pair-wise probability that the first task supports the second task.

Claim 9

A method as recited in claim 1 further comprising: determining the pair-wise probability for a pair of tasks that a first task in the pair of tasks competes with a second task in the pair of tasks based on the resource information; and if the first task competes with the second task, increasing the pair-wise cost of the pair of tasks based on a function of the pair-wise probability that the first task competes with the second task.

Claim 10

A method as recited in claim 1 wherein the generating comprises: selecting a first task from among the plurality of tasks; querying the task container of the first task for the pair-wise probabilities; and summing the pair-wise probabilities to form the total cost associated with the first task.

Claim 11

A method as recited in claim 1 wherein the resource information comprises preference information describing preferences of the one or more resources.

Claim 12

A method as recited in claim 1 wherein the generating comprises applying preference values to the tasks.

Claim 13

A method as recited in claim 1 wherein the generating comprises tabulating the pair-wise cost associated with each pair of tasks.

Claim 14

A method as recited in claim 1 further comprising: removing the scheduled task from a main task log; adjusting pair-wise probabilities associated with resources remaining in the main task log based on the scheduled task; and re-generating the total cost for each task based on pair-wise costs for each task calculated from adjusted pair-wise probabilities that the task will influence each other task in the plurality of tasks task containers.

Claim 15

A computer-readable storage medium storing processor-executable instructions for performing a method comprising: receiving a plurality of first resource identifiers identifying first resources associated with a first candidate task and selection criteria defining how the first resources are to be selected from the plurality of first resources; receiving a second resource identifier identifying a second resource associated with a second candidate task; receiving a current schedule state of scheduled tasks and scheduled resources; querying a task container that includes an interface function that, when called, determines a pair-wise probability that the first candidate task will influence the second candidate task based on the current schedule state of scheduled tasks, the first resources, the second resource, and the selection criteria; calculating a pair-wise cost of scheduling the first candidate task based on the determined pair-wise probability; and scheduling one or more of the first candidate task and the second candidate task based on the pair-wise cost.

Claim 16

A computer-readable storage medium storing processor-executable instructions for performing a method comprising: receiving a plurality of first resource identifiers identifying first resources associated with a first candidate task and selection criteria defining how the first resources are to be selected from the plurality of first resources; receiving a second resource identifier identifying a second resource associated with a second candidate task; receiving a current schedule state of scheduled tasks and scheduled resources; querying a task container that includes an interface function that, when called, determines a pair-wise probability that the first candidate task will influence the second candidate task based on the current schedule state of scheduled tasks, the first resources, the second resource, and the selection criteria; calculating a pair-wise cost of scheduling the first candidate task based on the determined pair-wise probability; and scheduling one or more of the first candidate task and the second candidate task based on the pair-wise cost.

Claim 17

A computer-readable storage medium as recited in claim 14 wherein the scheduling comprises: identifying one or more of the first resources that are not the same as the second resource and that satisfy the selection criteria.

Claim 18

A computer-readable storage medium as recited in claim 14 further comprising: determining whether the first candidate task and the second candidate task are viable based on the current schedule state; and eliminating one or more of the first or second candidate task from consideration if the one or more of the first or second candidate task is not viable.

Claim 21

A system as recited in claim 17 wherein the resource selection logic is selected from a group consisting of: an “AND” function indicating that all of the plurality of resources are required; an “XOR” function indicating that one and only one of the plurality of resources is required; and an “OR” function indicating that at least one of the plurality of resources is required.

Claim 22

A system as recited in claim 17 wherein the cost generator is further operable to calculate the pair-wise costs associated with each of the tasks.

Claim 23

A system as recited in claim 17 wherein the cost generator is further operable to tabulate the pair-wise costs associated with each of the tasks.

Claim 24

A system as recited in claim 17 wherein the task object further comprises time constraint information indicating at least one time constraint between two of the tasks.

Claim 25

A system as recited in claim 17 wherein the task log further comprises a hierarchical arrangement of the task objects and the resource objects.

Claim 26

A system as recited in claim 17 wherein each task object is operable to return a pair-wise probability that the task object competes with another task object.

Claim 27

A computer implemented method comprising: determining pair-wise probabilities for a plurality of tasks to be scheduled at a computer that each task in a plurality of tasks will influence each other task in the plurality of tasks; calculating pair-wise costs associated with the plurality of tasks from determined pair-wise probabilities for the plurality of tasks; generating a total cost associated with each of a the plurality of tasks to be scheduled based on the pair-wise costs for each task, wherein each task requires one or more resources, and wherein at least one of the tasks requires a plurality of resources, and wherein generating the total cost of the at least one task is based on pair-wise costs for the at least one task calculated from determined pair-wise probabilities that other tasks require one or more of the plurality of resources required by the at least one task; executing a minimum total cost task including allocating resources to the minimum total cost task; scheduling the minimum total cost task if the minimum total cost task successfully executes; and reversing side-effects from the executing including deallocating resources from the minimum total cost task if the minimum total cost task fails to execute.

Claim 28

A computer implemented method comprising: determining pair-wise probabilities for a plurality of tasks to be scheduled at a computer that each task in a plurality of tasks will influence each other task in the plurality of tasks; calculating pair-wise costs associated with the plurality of tasks from determined pair-wise probabilities for the plurality of tasks; generating a total cost associated with each of a the plurality of tasks to be scheduled based on the pair-wise costs for each task, wherein each task requires one or more resources, and wherein at least one of the tasks requires a plurality of resources, and wherein generating the total cost of the at least one task is based on pair-wise costs for the at least one task calculated from determined pair-wise probabilities that other tasks require one or more of the plurality of resources required by the at least one task; executing a minimum total cost task including allocating resources to the minimum total cost task; scheduling the minimum total cost task if the minimum total cost task successfully executes; and reversing side-effects from the executing including deallocating resources from the minimum total cost task if the minimum total cost task fails to execute.

Claim 29

A method as recited in claim 24 further comprising determining a pair-wise probability representing a probability that a first task in the plurality of tasks conflicts with a second task in the plurality of tasks.

Claim 30

A method as recited in claim 25 further comprising adjusting the pair-wise probability in response to scheduling the minimum total cost task.

Claim 31

A method as recited in claim 24 further comprising determining the total costs based upon preference weights assigned to the plurality of tasks.

Claim 32

A method as recited in claim 24 further comprising determining viability of each task in the plurality of tasks.

Claim 33

A method as recited in claim 24 , wherein reversing side-effects comprises deallocating any resources allocated during the executing and de-scheduling any tasks that were scheduled during the executing.