The CLP Procedure

In many real-world scheduling problems, resources might not be available at all times, or they might have only partial capacities at some predetermined time periods (for example, because of weekends, holidays, or periods of machine maintenance). For each resource, a calendar indicates the time periods during which the resource is not available or has only partial capacity. The resource calendars impose additional restrictions on the problems.

This example illustrates the use of the cumulative constraint to model resource calendars in solving a single resource-constrained project scheduling problem.

This example considers a simple case of RCPSP/max that uses resource calendars and contains 12 uninterruptible tasks, each with fixed duration and demand. These tasks need to be scheduled on a single renewable resource that has a capacity of eight units. In addition, the resource has only half its capacity available during time period 5 and is unavailable in time period 6.

To simplify the specification, this example considers only the standard finish-to-start precedence relationships between two tasks. That is, Task i immediately precedes Task j, which implies:

More general forms of temporal relationships that involve nonstandard relationships and lags can be easily formulated using linear constraints.

Table 14 shows the durations, demands, and precedence relations of the tasks.

In order to accommodate the resource calendar, two artificial tasks, Task 13 and Task 14, are introduced, each with a duration of 1. Task 13 starts at time period 5 and uses four units of the resource, leaving half the capacity for other tasks during that period. Similarly, Task 14 starts at time period 6 and consumes the full capacity, thus making the corresponding resource unavailable to other tasks during that period.

Two additional tasks, S and T, are introduced to represent the beginning and completion of the project, respectively. The durations of both S and T are 0, and they do not require any of the resources. Note that the start time and the end time are equal for these two tasks. To simplify the notation, you can use S as the start-time variable of the project and T as the end-time variable. The makespan of the project can be expressed as T – S. Without loss of generality, the start time of the project is assumed to be 0, so that the objective of the problem is to minimize T.

There are two ways to declare start-time variables and specify temporal constraints:

This example illustrates using the Constraint data set, which is created by merging three data sets. The StartTime data set, shown in Output 2.15.1, specifies the lower and upper bounds of the start-time variables for the real and artificial tasks. Note that the domains of artificial variables Start13, Start14, and S are fixed. A lower bound on variable T is determined by considering the (Task 6, Task 12) subpath, and an upper bound on T is determined by aggregating the durations of Task 1 through Task 14. The lower and upper bounds for the other variables are temporarily set to the lower bound of S and the upper bound of T, respectively, for convenience. Tighter bounds will be determined by the precedence constraints.

The Precedence data set shown in Output 2.15.2 specifies linear constraints that represent the precedence relations between tasks.

Finally, the Objective data set shown in Output 2.15.3 specifies the objective function of this problem.

The following statements merge these three data sets to create the Constraint data set that the CLP procedure uses to find a schedule that minimizes the makespan.

data ConData;
   set StartTime Precedence Objective;
run;

proc clp condata=ConData out=OutData usecondatavars=1;
   /* set lower and upper bounds for the objective function */
   obj lb=10 ub=40;

   /* Post a cumulative constraint for the resource */
   cumulative (start=(Start1-Start14)
               duration=(1 2 2 6 3 6 1 3 3 4 2 4 1 1)
               demand=(4 2 3 3 2 3 1 2 2 1 2 2 4 8)
               capacity=8);
run;

The USECONDATAVARS=1 specification in the PROC CLP statement indicates that all variables are implicitly defined in the Constraint data table ConData. The OBJ statement specifies the lower and upper bounds on the objective function. In this example, they are actually the lower and upper bounds of variable T, the completion time of the project. The CUMULATIVE statement defines the task start times, task durations, and task demands, and it enforces the constraint that the cumulative resource usage of Task 1 though Task 14 not exceed the resource capacity at any point in time.

The table in Output 2.15.4, which is derived from the solution table, shows a corresponding schedule for the 12 tasks.

The Gantt chart shown in Output 2.15.5 reports the resource demand and displays the resource-constrained schedule for each of the 12 tasks. The chart also overlays a plot of the resource capacity with time and a histogram of the resource demand with time. The resource quantity axis is on the right. Notice the decreased consumption in time periods 5 and 6.

Output 2.15.5: Gantt Chart Showing Task Schedule and Resource Consumption

The second part of this example illustrates how you can use the cumulative constraint to model optional tasks. Optional tasks are tasks that might or might not occur; they can arise in scenarios such as project selection, job contracting, and so on.

Consider the previous resource-constrained project scheduling problem with calendars that completed in 14 time periods. Suppose that the project must now be completed in 12 time periods and can assign certain tasks to external contractors at additional cost in order to complete in fewer time periods. Assume that Task 1, Task 2, Task 3, Task 4, and Task 5 can be contracted out subject to the following pairwise conditions:

The objective is to minimize the total cost, subject to finishing the project within 12 time periods.

The StartTime2 data set shown in Output 2.15.6 specifies the new lower and upper bounds of the start-time variables for all tasks. Note that the variable T is now fixed to 12 to reflect the new makespan restriction. Although not necessary, the upper bounds of all variables Start1 to Start12 can also be set to 12.

One way to model the fact that tasks might or might not be executed in-house is to introduce a demand variable for each such task. The lower bound for this demand variable is equal to 0, and its upper bound is equal to the demand it would have had if it had been processed in-house. The demand variable for a task is assigned to its lower bound if the task is contracted out, or to its upper bound if the task is not contracted out. The usage variables are declared in the Demand data set as shown in Output 2.15.7.

A binary variable is created for each task that can be contracted out. The value of the binary variable is 1 if the corresponding task is contracted out, or 0 if is not contracted out. The relationship between the binary variable and demand variable for task i can be expressed by the linear constraint

where is the demand for the task i.

Because Tasks 1 and 4 and Tasks 2 and 5 must be jointly processed, the number of binary variables can be reduced to three.

The Binary data set shown in Output 2.15.8 declares these three binary variables.

The Usage data set shown in Output 2.15.9 contains the linear constraints that relate the binary variables and the demand variables.

Finally, the objective function shown in Output 2.15.10 defines the total contracting cost of the project that is to be minimized.

As before, the data sets are merged to create the Constraint data table, and the CLP procedure is invoked to find the best solution as follows:

data ConData2;
   set StartTime2 Precedence Demand Binary Usage Objective2;
run;

proc clp condata=ConData2 out=OutData2 usecondatavars=1;
   /* set lower and upper bounds for the objective function */
   obj lb=0 ub=32;

   /* Define a cumulative constraint for the resource */
   cumulative (start=(Start1-Start14)
               demand=(Demand1-Demand14)
               dur=(1 2 2 6 3 6 1 3 3 4 2 4 1 1)
               capacity=8);
run;

The table in Output 2.15.11, derived from the Solution data set, displays the optimal schedule that has a makespan of 11 time periods and contracts out Task 1 and Task 4.