Chapter Contents
Chapter Contents
Previous
Previous
Next
Next
The CPM Procedure

Resource Usage and Allocation

Often the activities in a project use several resources. If you assume that these resources are available in unlimited quantities, then the only restrictions on the start and finish times of the activities in the project are those imposed by precedence constraints and dates specified for alignment of the activities. In most practical situations, however, there are limitations on the availability of resources; as a result, neither the early start schedule nor the late start schedule (nor any intermediate schedule for that matter) may be feasible. In such cases, the project manager is faced with the task of scheduling the activities in the project subject to constraints on resource availability in addition to the precedence constraints and constraints on the start and finish times of certain activities in the project. This problem is known as resource allocation.

You can use PROC CPM to schedule the activities in a project subject to resource constraints. To perform resource allocation, you must specify the resource requirements for each activity in the project and also specify the amount of resources available on each day under consideration. The resource requirements are given in the Activity data set, with the variable names identified to PROC CPM through the RESOURCE statement. The levels of resources available on different dates, as well as other information regarding the resources, such as the type of resource, the priority of the resource, and so forth, are obtained from the RESOURCEIN= data set. Specifying resource requirements is described in detail in the "Specifying Resource Requirements" section, and the description of the format of the Resource data set is given in the "RESOURCEIN= Input Data Set" section, which follows. The "Scheduling Method" section describes how you can use the SCHEDRULE= and DELAY= options (and other options) in conjunction with certain special observations in the Resource data set to control the process of resource allocation to suit your needs. Subsequent sections describe the different scheduling rules, supplementary resources, activity splitting, progress updating, and alternate resources.

RESOURCEIN= Input Data Set

The RESOURCEIN data set (referred to as the Resource data set) contains all of the necessary information about the resources that are to be used by PROC CPM to schedule the project. Typically, the Resource data set contains the resource variables (numeric), a type identifier variable (character) that identifies the type of information in each observation, a period variable (numeric and usually a SAS time, date, or datetime variable) and a RESID variable that is used to specify alternate resources.

The value of the type identifier variable in each observation tells CPM how to interpret that observation. Valid values for this variable are RESLEVEL, RESTYPE, RESPRTY, SUPLEVEL, ALTPRTY, ALTRATE, RESRCDUR, and CALENDAR. If the value of the type identifier variable in a particular observation is RESLEVEL, then that observation contains the levels available for each resource from the time specified in the period variable. Missing values are not allowed for the period variable in an observation containing the levels of the resources. Note that, for consumable resources, the observation indicates the total availability and not the increase in the availability. Likewise, for replenishable resources, the observation indicates the new level and not the change in the level of the resource.

Each resource can be classified as either consumable or replenishable. A consumable resource is one that is used up by the job (such as bricks or money), while a replenishable resource becomes available again once a job using it is over (such as manpower or machinery). If the value of the type identifier variable is RESTYPE, then that observation identifies the nature (consumable or replenishable) of the resource. The observation contains a value 1 for a replenishable resource and a value 2 for a consumable one. A missing value in this observation is treated as 1. In fact, if there is no observation in the Resource data set with the type identifier variable equal to RESTYPE, then all resources are assumed to be replenishable.

Sometimes, it may be useful to include resources in the project that are to be used only for aggregation purposes. You can indicate that a given resource is to be used for aggregation, and not for resource allocation, by specifying the values 3 or 4, depending on whether the resource is replenishable or consumable. In other words, use 3 for replenishable aggregate resources and 4 for consumable aggregate resources.

One of the scheduling rules that can be specified using the SCHEDRULE= option is RESPRTY, which requires ordering the resources according to some priority (details are given in the "Scheduling Rules" section). If this option is used, there must be an observation in the Resource data set with the type identifier variable taking the value RESPRTY. This observation specifies the ordering of the resources.

If the type identifier variable is given as SUPLEVEL, the observation denotes the amount of extra resource that is available for use throughout the duration of the project. This extra resource is used only if the activity cannot be scheduled without delaying it beyond its late start time. See the "Secondary Levels of Resources" section for details about the use of supplementary levels of resources in conjunction with the DELAY= and ACTDELAY= options.

If the type identifier variable is specified as ALTRATE or ALTPRTY, the Resource data set must also have a RESID variable that is used to identify the name of a resource for which the current observation lists the possible alternate resources. See the "Specifying Alternate Resources" section for details.

If the value of the type identifier variable is RESRCDUR, that observation specifies the effect of the resource on an activity's duration. Valid values for the resource variables in such an observation are 0, 1, and 2. A value 0 indicates that the resource uses a fixed duration (specified by the DURATION variable); in other words, the activity's duration is not affected by changing the rate of the resource. A value 1 indicates that the WORK variable for an activity specifies the total amount of work required by the resource that is used to calculate the time required by the resource to complete its work on that activity; such a resource is referred to as a driving resource. The value 2 indicates a third type of resource; such a resource (referred to as a spanning resource) is required throughout the activity's duration, no matter which resource is working on it. For example, an activity might require 10 percent of a "supervisor," or the use of a particular room, throughout its duration. For such an activity, the duration used for the spanning resource is computed after determining the span of the activity for all the other resources.

If the value of the type identifier variable is CALENDAR, that observation specifies the calendar that is followed by each resource. If no calendar is specified for a given resource, the relevant activity's calendar is used instead. Note that this use of the calendar requires that the calendar variable in the Activity and other data sets be numeric.

The period variable must have nonmissing values for observations specifying the levels of the resources (that is, with type identifier equal to RESLEVEL). However, the period variable does not have any meaning when the type identifier variable has any value other than RESLEVEL; if the period variable has nonmissing values in these observations, it is ignored. The Resource data set must be sorted in order of increasing values of the period variable.

Multiple observations are allowed for each type of observation. If there is a conflict in the values specified, only the first nonmissing value is honored; for example, if there are two observations of the type RESTYPE and a resource variable has value 1 in the first and 2 in the second of these observations, the resource type is assumed to be 1 (replenishable). On the other hand, if the value is missing in the first observation but set to 2 in the second, the resource type is assumed to be 2 (consumable).

A resource is available at the specified level from the time given in the first observation with a nonmissing value for the resource. Its level changes (to the new value) whenever a new observation is encountered with a nonmissing value, and the date of change is the date specified in this observation.

The following example illustrates the details about the Resource data set. Consider the following Resource data:

         OBS   OBSTYPE    DATE    WORKERS    BRICKS

          1    RESTYPE     .         1           2
          2    RESPRTY     .        10          10
          3    SUPLEVEL    .         1           .
          4    RESLEVEL  1JUL92      .        1000
          5    RESLEVEL  5JUL92      4           .
          6    RESLEVEL  9JUL92      .        1500

There are two resources in these data, WORKERS and BRICKS. The variable OBSTYPE is the type identifier, and the variable DATE is the period variable. The first observation (because OBSTYPE has value `RESTYPE') indicates that WORKERS is a replenishable resource and BRICKS is a consumable resource. The second observation indicates that both resources have equal priority. In the third observation, a value `1' under WORKERS indicates that a supplementary level of 1 worker is available if necessary, while no reserve is available for the resource BRICKS.

The next three observations indicate the resource availability profile. The resource WORKERS is unavailable until July 5, 1992, when the level jumps from `0' to `4' and remains at that level through the end of the project. The resource BRICKS is available from July 1, 1992, at level `1000'. On July 9, an additional 500 bricks are made available to increase the total availability to 1500. Note that missing values in observations 5 and 6 indicate that there is no change in the availability for the respective resources.

As another example, suppose that you want to treat BRICKS as an aggregate resource (one that is not to be included in resource allocation.) Then consider the following data from a Resource data set:

         OBSTYPE      BRICKS    PAINTER     SUPERV

         RESTYPE        4          1          1
         RESRCDUR       0          1          2
         CALENDAR       1          0          0

The first observation indicates that the resource BRICKS is consumable and is to be used only for aggregation while the other two resources are replenishable and are to be treated as constrained resources during resource allocation.

The second observation, with the keyword `RESRCDUR', specifies the effect of the resource on an activity's duration. The value `0' for the resource BRICKS implies that this resource does not affect the duration of an activity. On the other hand, the value `1' identifies the resource PAINTER as a driving resource; this means that by increasing the number of painters, an activity's duration can be decreased. Note that the procedure uses this information about the nature of the resource only if a particular observation in the Activity data set has valid values for both the WORK and the DURATION variables. Otherwise, if you specify a value only for the WORK variable, the procedure assumes that the resource specifications in that observation drive the activity's duration. Likewise, if you specify a value only for the DURATION variable, the procedure assumes that the resources specified in that observation require a fixed duration.

In the Resource data set specifications, the second observation also identifies the resource SUPERV to be of the spanning type. In other words, such a resource is required by an activity whenever any of the other resources are working on the same activity.

The third observation indicates the calendar to be used in calculating the activity's start and finish times for the particular resource. If you do not specify a calendar, the procedure uses the activity's calendar.

Specifying Resource Requirements

To perform resource allocation or to summarize the resource utilization, you must specify the amount of resources required by each activity. In this section, the format for this specification is described. The amount required by each activity for each of the resources listed in the RESOURCE statement is specified in the Activity data set. The requirements for each activity are assumed to be constant throughout the activity's duration. A missing value for a resource variable in the Activity data set indicates that the particular resource is not required for the activity in that observation.

The interpretation of the specification depends on whether or not the resource is replenishable. Suppose that the value for a given resource variable in a particular observation is `x'. If the resource is replenishable, it indicates that x units of the resource are required throughout the duration of the activity specified in that observation. On the other hand, if the resource is consumable, it indicates that the specified resource is consumed at the rate of x units per unit interval, where interval is the value specified in the INTERVAL= option in the PROC CPM statement. For example, consider the following specification:

       OBS   ACTIVITY    DUR     WORKERS     BRICKS

        1       A         5        .          100
        2       B         4        2           .

Here, ACTIVITY denotes the activity under consideration, DUR is the duration in days (assuming that INTERVAL=DAY), and the resource variables are WORKERS and BRICKS. A missing value for WORKERS in observation 1 indicates that activity `A' does not need the resource WORKERS, while the same is true for the resource BRICKS and activity `B'. You can assume that the resource WORKERS has been identified as replenishable, and the resource BRICKS has been identified as consumable in a Resource data set. Thus, a value `100' for the consumable resource BRICKS indicates that 100 bricks per day are required for each of the 5 days of the duration of activity `A', and a value `2' for the replenishable resource WORKERS indicates that 2 workers are required throughout the duration (4 days) of activity `B'.

Scheduling Method

PROC CPM uses the serial-parallel (serial in time and parallel in activities) method of scheduling. In this section, the basic scheduling algorithm is described. (Modifications to the algorithm if an ACTUAL statement is used, if activity splitting is allowed, or if alternate resources are specified, are described later.) The basic algorithm proceeds through the following steps:
  1. An initial tentative schedule describing the early and late start and finish times is determined without taking any resource constraints into account. This schedule does, however, reflect any restrictions placed on the start and finish times by the use of the ALIGNDATE and ALIGNTYPE statements. As much as possible, PROC CPM tries to schedule each activity to start at its E_START time (e_start, as calculated in this step). Set time=min(e_start), where the minimum is taken over all the activities in the network.
  2. All of the activities whose e_start values coincide with time are arranged in a waiting list that is sorted according to the rule specified in the SCHEDRULE= option. (See the "Scheduling Rules" section for details on the valid values of this option.) The SCHEDRULE2= option can be used to break ties. PROC CPM tries to schedule the activities in the same order as on this list. For each activity the procedure checks to see if the required amount of each resource will be available throughout the activity's duration; if enough resources are available, the activity is scheduled to start at time. Otherwise, the resource availability profile is examined to see if there is likely to be an increase in resources in the future. If none is perceived until l_start + delay, the procedure tries to schedule the activity to start at time using supplementary levels of the resources (if there is an observation in the Resource data set specifying supplementary levels of resources); otherwise, it is postponed. (Note that if the AWAITDELAY option is specified, and there are not enough resources at time, the activity is not scheduled at time using supplementary resources). If time is equal to or greater than the value of l_start + delay, and the activity cannot be scheduled (even using supplementary resources), PROC CPM stops with an error message, giving a partial schedule. You can also specify a cut-off date (using the STOPDATE= option) when resource constrained scheduling is to stop. Note that once an activity that uses a supplementary level of a replenishable resource is over, the supplementary level that was used is returned to the reservoir and is not used again until needed. For consumable resources, if supplementary levels were used on a particular date, PROC CPM attempts to bring the reservoir back to the original level at the earliest possible time. In other words, the next time the primary availability of the resource increases, the reservoir is first used to replenish the supplementary level of the resource. (See Example 2.16, "Using Supplementary Resources"). Adjustment is made to the resource availability profile to account for any activity that is scheduled to start at time.

  3. All of the activities in the waiting list that were unable to be scheduled in Step 2 are postponed and are tentatively scheduled to start at the time when the next change takes place in the resource availability profile (that is, their e_start is set to the next change date in the availability of resources). time is advanced to the minimum e_start time of all unscheduled activities.

Steps 1, 2, and 3 are repeated until all activities are scheduled or the procedure stops with an error message.

Some important points to keep in mind are:

Scheduling Rules

The SCHEDRULE= option specifies the criterion to use for determining the order in which activities are to be considered while scheduling them subject to resource constraints. As described in the the "Scheduling Method" section, at a given time specified by time, all activities whose tentative e_start coincides with time are arranged in a list ordered according to the scheduling rule, schedrule. The SCHEDRULE2= option can be used to break ties caused by the SCHEDRULE= option; valid values for schedrule2 are the same as for schedrule. However, if schedrule is ACTPRTY, then schedrule2 cannot be RESPRTY, and vice versa.

The following is a list of the six valid values of schedrule, along with a brief description of their respective effects.

ACTPRTY
specifies that PROC CPM should sort the activities in the waiting list in the order of increasing values of the variable specified in the ACTIVITYPRTY= option in the RESOURCE statement. This variable specifies a user-assigned priority to each activity in the project (low value of the variable indicates high priority).

Note: If SCHEDRULE is specified as ACTPRTY, the RESOURCE statement must contain the specification of the variable in the Activity data set that assigns priorities to the activities; if the variable name is not specified through the ACTIVITYPRTY= option, then CPM ignores the specification for the SCHEDRULE= option and uses the default scheduling rule, LST, instead.

DELAYLST
specifies that the activities in the waiting list are sorted in the order of increasing L_START + ACTDELAY, where ACTDELAY is the value of the ACTDELAY variable for that activity.

LFT
specifies that the activities in the waiting list are sorted in the order of increasing L_FINISH time.

LST
specifies that the activities in the waiting list are sorted in the order of increasing L_START time. Thus, this option causes activities that are closer to being critical to be scheduled first. This is the default rule.

RESPRTY
specifies that PROC CPM should sort the activities in the waiting list in the order of increasing values of the resource priority for the most important resource used by each activity. In order for this scheduling rule to be valid, there must be an observation in the Resource data set identified by the value RESPRTY for the type identifier variable and specifying priorities for the resources. PROC CPM uses these priority values (once again, low values indicate high priority) to order the activities; then, the activities in the waiting list are ordered according to the highest priority resource that they use. In other words, the CPM procedure uses the resource priorities to assign priorities to the activities in the project; these activity priorities are then used to order the activities in the waiting list (in increasing order). If this option is specified, and there is no observation in the Resource data set specifying the resource priorities, PROC CPM ignores the specification for the SCHEDRULE= option and uses the default scheduling rule, LST, instead.



SHORTDUR
specifies that the activities in the waiting list are sorted in the order of increasing durations. Thus, PROC CPM tries to schedule activities with shorter durations first.

Secondary Levels of Resources

There are two factors that you can use to control the process of scheduling subject to resource constraints: time and resources. In some applications, time is the most important factor, and you may be willing to use extra resources in order to meet project deadlines; in other applications, you may be willing to allow the project completion to be delayed by an arbitrary amount of time if insufficient resources warrant doing so. The DELAY= and ACTDELAY= options and the availability of supplementary resources enable you to choose either method or a combination of the two approaches.

In the first case, where you do not want the project to be delayed, specify the availability of supplementary resources in the Resource data set and set DELAY=0. In the latter case, where extra resources are unavailable and you are willing to delay project completion time, set the DELAY= option to some very large number or leave it unspecified (in which case it is assumed to be + INFINITY). You can achieve a combination of both effects (using supplementary levels and setting a limit on the delay allowed) by specifying an intermediate value for the DELAY= option and including an observation in the Resource data set with supplementary levels.

You can also use the INFEASDIAGNOSTIC option which is equivalent to specifying infinite supplementary levels for all the resources under consideration. In this case, the DELAY= value is assumed to equal the default value of +INFINITY, unless it is specified otherwise. See Example 2.17, "Use of the INFEASDIAGNOSTIC Option," for an illustration.

Note that the DELAY= option presupposes that all the activities can be subjected to the same amount of delay. In some situations, you may want to control the amount of delay for each activity on the basis of some criterion, say the amount of float present in the activity. The ACTDELAY= option enables you to specify a variable amount of delay for each activity.

Resource-Driven Durations and Resource Allocation

If resource driven durations or resource calendars are specified, the procedure computes the start and finish times for each resource separately for each activity. An activity is considered to be completed only when all the resources have completed their work on that activity. Thus an activity's start (finish) time is computed as the minimum (maximum) of the start (finish) times for all the resources used by that activity.

During resource-constrained scheduling, an activity enters the list of activities waiting for resources when all its precedence constraints have been satisfied. As before, this list is ordered using the scheduling rule specified. At this point, a tentative start and finish time is computed for each of the resources required by the activity using the resource's duration and calendar. An attempt is made to schedule all of this activity's resources at these calculated times using the available resources. If the attempt is successful, the activity is scheduled to start at the given time with the appropriate resource schedule times, and the required resources are reduced from the resource availabilities. Otherwise, the procedure attempts to schedule the next activity in the list of activities waiting for resources. When all activities have been considered at the given time, the procedure continues to the next event and continues the allocation process. Note that, at a given point of time, the procedure schedules the activity only if all the required resources are available for that activity to start at that time (or at the nearest time per that resource's calendar), unless you specify the INDEPENDENTALLOC option.

The INDEPENDENTALLOC option allows each resource to be scheduled independently for the activity. Thus, when an activity enters the list of activities waiting for resources, each resource requirement is considered independently, and a particular resource can be scheduled for that activity even if none of the other resources are available. However, the spanning type of resources must always be available throughout the activity's duration. Note that the activity is considered to be finished (and its successors can start) only after all the resources for that activity have been scheduled. Note also that this option is valid even if all activities have fixed durations and calendars are not associated with resources.

Activity Splitting

As mentioned in the "Scheduling Method" section, PROC CPM assumes that activities cannot be preempted once they have started. Thus, an activity is scheduled only if it can be assured of enough resources throughout its entire duration. Sometimes, you may be able to make better use of the resources by allowing activities to be split. PROC CPM enables you to specify the maximum number of segments that an activity can be split into as well as the minimum duration of any segment of the activity. Suppose that for a given activity, d is its duration, maxn is the maximum number of segments allowed, and dmin is the minimum duration allowed for a segment. If one or the other of these values is not given, it is calculated appropriately based on the duration of the activity. The scheduling algorithm described earlier is modified as follows:

Note that splitting may not always reduce project completion time; it is designed to make better use of resources. In particular, if there are gaps in resource availability, it allows activities to be split and scheduled around the gaps, thus using the resources more efficiently.

If activity splitting is allowed, a new variable is included in the Schedule data set called SEGMT_NO (segment number). If splitting does occur, the Schedule data set has more observations than the Activity data set. Activities that are not split are treated as before, except that the value of the variable SEGMT_NO is set to missing. For split activities, the number of observations output is one more than the number of disjoint segments created.

The first observation corresponding to such an activity has SEGMT_NO set to missing, and the S_START and S_FINISH times are set to be equal to the start and finish times, respectively, of the entire activity. That is, S_START is equal to the scheduled start time of the first segment, and S_FINISH is equal to the scheduled finish time of the last segment that the activity is split into. Following this observation, there are as many observations as the number of disjoint segments in the activity. All values for these additional obervations are the same as the corresponding values for the first observation for this activity, except for the variables SEGMT_NO, S_START, S_FINISH, and the DURATION variable. SEGMT_NO is the index of the segment, S_START and S_FINISH are the resource-constrained start and finish times for this segment, and DURATION is the duration of this segment.

Actual Dates and Resource Allocation

The resource-constrained scheduling algorithm uses the early start schedule as the base schedule to determine possible start times for activities in the project. If an ACTUAL statement is used in the invocation of PROC CPM, the early start schedule (as well as the late start schedule) reflects the progress information that is specified for activities in the project, and thus affects the resource constrained schedule also. Further, activities that are already completed or in progress are scheduled at their actual start without regard to resource constraints. If the resource usage profile for such activities indicates that the resources are insufficient, a warning is issued to the log, but the activities are not postponed beyond their actual start time. The Usage data set contains negative values for the availability of the insufficient resources. These extra amounts are assumed to have come from the supplementary levels of the resources (if such a reservoir existed); for details on supplementary resources, see the "Secondary Levels of Resources" section. If activity splitting is allowed (either through the specification of the MINSEGMTDUR or MAXNSEGMT variable or the SPLITFLAG or TIMENOWSPLT option), activities that are currently in progress may be split at TIMENOW if resources are insufficient; then the second segment of the split activity is added to the list of activities that need to be scheduled subject to resource constraints. Starting from TIMENOW, all activities that are still unscheduled are treated as described in the "Scheduling Method" section.

Specifying Alternate Resources

PROC CPM enables you to identify alternate resources that can be substituted for any given resource that is insufficient. Thus, for example, you can specify that if programmer John is unavailable for a given task, he can be substituted by programmer David or Robert. This information is passed to PROC CPM via the Resource data set.

As with other aspects of the Resource data set, each observation is identified by a keyword indicating the type of information in that observation. Two keywords, ALTRATE and ALTPRTY, enable you to specify the rate of substitution and a prioritization of the alternate resources when a resource has more than one substitution (lower value indicates higher priority). Further, a new variable (identified to PROC CPM via the RESID= option) is used to identify the resource for which alternates are being specified in the current observation. Consider the following Resource data:

 OBS  OBSTYPE   RES_NAME  RES_DATE   JOHN   DAVID   ROBERT

  1   RESTYPE                   .      1     1.0      1.0
  2   ALTRATE     JOHN          .      1     0.5      0.5
  3   ALTPRTY     JOHN          .      1     2.0      3.0
  4   RESLEVEL            15FEB91      1     1.0      1.0

In these Resource data, the second observation indicates that John can be substituted by David or Robert; however, either David or Robert can accomplish John's tasks with half the effort. In other words, if an activity requires 1 unit of John, it can also be accomplished with 0.5 units of David. Also, the third observation, with OBSTYPE = `ALTPRTY', indicates that if John is unavailable, PROC CPM should first try to use David and if he, too, is unavailable, then should use Robert. This set up allows a wide range of control for specifying alternate resources.

In other words, the mechanism for specifying alternate resources is as follows: for each resource, specify a list of possible alternatives along with a conversion rate and an order in which the alternatives are to be considered. In the Resource data set, add another variable (identified by the RESID= option) to specify the name of the resource variable for which alternatives are being specified (the variable RES_NAME in the example above). Let OBSTYPE = `ALTRATE' for the observation that specifies the rate of conversion for each possible alternate resource (missing implies the particular resource cannot be substituted). Let OBSTYPE = `ALTPRTY' for the observation that specifies a prioritization for the resources. Note that all substitute resources must be of the same type (replenishable or consumable) as the primary resource. The specification of the RESID= option triggers the use of alternate resources. If alternate resources are used, the Schedule data set contains new variables that specify the actual resources that are used; the names of these variables are obtained by prefixing the resource names by `U'. When activities are allowed to be split and alternate resources are allowed, different segments of the activity can use a different set of resources. If this is the case, the Schedule data set contains a different observation for every segment that uses a different set of resources, even if these segments are contiguous in time. Note that contiguous segments, even if they use different sets of resources, are not treated as true splits for the purpose of counting the number of splits allowed for the activity.

See Example 2.20 for an illustration of the use of alternate resources.

Chapter Contents
Chapter Contents
Previous
Previous
Next
Next
Top
Top

Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.