Scheduling system

Abstract

A scheduler combines characteristics of a forward and backward schedulers to determine a schedule for activities that require the use of resources. The system handles conflicting requirements for resources by considering target dates and the relative priority of the activities. As a result, higher priority activities are more likely to be scheduled to complete on or before their target date than are lower priority activities.

1 . A method for scheduling comprising: 
 receiving information relating to activities to be performed and information relating to the availability of resources needed to perform the activities; and    processing the information with a processor to create a schedule with a sequence of activities and a selection of resources for each activity, including: 
 performing a backward scheduling process to schedule activities based on a desired completion time for each activity, a time to complete each activity, and a last time that each activity can be started to meet the desired completion time for each activity (target period), the backward scheduling process further determining the availability of resources to perform the activities for each of a number of time periods, the backward scheduling process producing a list of activities arranged at least in part based on the latest period that the activity is to be started, and  
 automatically proceeding from the backward scheduling process to a forward scheduling process including defining a set of scheduling zones with activities to be performed during each zone and determining an order in which the activities should be scheduled using the results of the backward scheduling process starting with activities with earlier target periods and allocating resources forward in time.  
   
     
     
         2 . The method of  claim 1 , wherein the backward scheduling process further includes sorting the activities by relative priority level and starting the backward scheduling process with the highest priority activities.  
     
     
         3 . The method of  claim 1 , wherein each resource takes as inputs start, end, and rate of availability, wherein the rate can vary over time.  
     
     
         4 . The method of  claim 1 , wherein there is a single alternative resource set for each activity.  
     
     
         5 . The method of  claim 1 , wherein there are multiple alternative resource sets to satisfy an activity.  
     
     
         6 . The method of  claim 5 , wherein, as long as there is an unsatisfied balance of resources required for an activity, the process is repeated by testing the ability of each of the alternative resource sets to satisfy some portion of the activity.  
     
     
         7 . The method of  claim 1 , wherein, for each zone, the forward scheduling process allocates resources to an activity starting at the later of the earliest period in which the resource can be allocated (ready period) and the earliest period the backward scheduling process tried to allocate the resource to an activity within the zone (earliest resource period).  
     
     
         8 . The method of  claim 1 , further comprising determining whether an activity with a higher priority was scheduled later than the target period and thus is a late activity, and if one or more activities with lower priority have been scheduled before the late activity within the same zone as the late activity, then repeating forward scheduling having first moved such one or more lower priority activities to follow the late activity in the list of activities to forward schedule.  
     
     
         9 . The method of  claim 1 , wherein activities can use resources at different rates.  
     
     
         10 . The method of  claim 1 , further comprising, in response to a determination that an activity will be completed late, splitting the times during which resources are allocated to the activity such that a portion of the activity is completed on time.  
     
     
         11 . A method for scheduling comprising: 
 receiving information relating to activities to be performed and information relating to the availability of resources needed to perform the activities; and    processing the information with a processor in an automated manner to create a schedule with a sequence of activities and a selection of resources for each activity, including: 
 performing a backward scheduling process to schedule activities based on a last time that each activity can be started to meet the desired completion time (target time),  
 automatically proceeding from the backward scheduling process to a forward scheduling process including defining a set of scheduling zones with activities to be performed during each zone and determining an order in which the activities should be scheduled using the results of the backward scheduling process and starting with the activities with earlier target dates, and  
 after the forward scheduling process, determining whether an activity with a higher priority was scheduled later than the latest period to complete the activity within the desired completion time and thus is a late activity, and if an activity with a lower priority and target date has been scheduled before the late activity within the same zone as the late activity, then repeating forward scheduling having moved every such lower priority activity to follow the late activity in the list of activities to schedule.  
   
     
     
         12 . The method of  claim 11 , wherein the backward scheduling process further includes sorting the activities by relative priority level and starting the backward scheduling process with the highest priority activities.  
     
     
         13 . The method of  claim 11 , wherein there is a single alternative resource set for each activity.  
     
     
         14 . The method of  claim 11 , wherein there are multiple alternative resource sets to satisfy an activity.  
     
     
         15 . The method of  claim 14 , wherein, as long as there is an unsatisfied balance of resources required for an activity, the process is repeated by testing the ability of each of the alternative resource sets to satisfy some portion of the activity.  
     
     
         16 . The method of  claim 11 , wherein, for each zone, the forward scheduling process allocates resources to an activity starting at the later of the earliest period in which the resource can be allocated (ready period) and the earliest period the backward scheduling process tried to allocate the resource to an activity within the zone (earliest resource period).  
     
     
         17 . The method of  claim 11 , wherein activities can use resources at different rates.  
     
     
         18 . The method of  claim 11 , further comprising, in response to a determination that an activity will be completed late, splitting the times during which resources are allocated to the activity such that a portion of the activity is completed on time.  
     
     
         19 . A scheduling system comprising: 
 storage for storing information relating to activities to be performed and to the availability of resources needed to perform the activities; and    a processor for processing the information to create a schedule with a sequence of activities and a selection of resources for each activity, including: 
 performing a backward scheduling process to schedule activities based on a desired completion time for each activity for producing a list of activities arranged at least in part based on a target period indicating when that the activity are to be started to be completed on time, and  
 automatically proceeding from the backward scheduling process to a forward scheduling process including defining a set of scheduling zones with activities to be performed during each zone and determining an order in which the activities should be scheduled using the results of the backward scheduling process starting with activities with earlier target periods and allocating resources forward in time.  
   
     
     
         20 . The system of  claim 19 , wherein during the backward scheduling process the processor sorts the activities by relative priority level and starting the backward scheduling process with the highest priority activities.  
     
     
         21 . The system of  claim 19 , wherein the processor schedules for a single alternative resource set for each activity.  
     
     
         22 . The system of  claim 19 , wherein the processor schedules for multiple alternative resource sets to satisfy an activity.  
     
     
         23 . The system of  claim 19 , wherein the processor further determines whether an activity with a higher priority was scheduled later than the target period and thus is a late activity, and if one or more activities with lower priority have been scheduled before the late activity within the same zone as the late activity, then moving such one or more lower priority activities to follow the late activity.  
     
     
         24 . The system of  claim 19 , wherein the processor, in response to a determination that an activity will be completed late, splits the times during which resources are allocated to the activity such that a portion of the activity is completed on time.  
     
     
         25 . A computer readable medium having software for performing the process of  claim 1 .  
     
     
         26 . A computer readable medium having software for performing the process of  claim 11.