The CLP Procedure

This example is an instance of a category of problems known as the car sequencing problem. There is a considerable amount of literature related to this problem (Dincbas, Simonis, and Van Hentenryck 1988; Gravel, Gagne, and Price 2005; Solnon et al. 2008).

A number of cars are to be produced on an assembly line. Each car is customized to include a specific set of options, such as air conditioning, a sunroof, a navigation system, and so on. The assembly line moves through several workstations for installation of these options. The cars cannot be positioned randomly, because each workstation has limited capacity and needs time to set itself up to install the options as the car moves in front of the station. These capacity constraints are formalized using constraints of the form m out of N, which indicates that the workstation can install the option on m out of every sequence of N cars. The car sequencing problem is to determine a sequencing of the cars on the assembly line that satisfies the demand constraints for each set of car options and the capacity constraints for each workstation.

This example comes from Dincbas, Simonis, and Van Hentenryck (1988). Ten cars need to be customized with five possible options. A class of car is defined by a specific set of options; there are six classes of cars.

The instance data are presented in Table 5.

For example, car class 4 requires installation of option 2 and option 4, and two cars of this class are required. The workstation for option 2 can process only two out of every sequence of three cars. The workstation for option 4 has even less capacity—two out of every five cars.

The data for this problem are used to create a SAS data set, which in turn is processed to generate the SAS macro variables shown in Table 6 that are used in the CLP procedure. The assembly line is treated as a sequence of slots, and each car must be allocated to a single slot.

The decision variables for this problem are shown in Table 7.

The following SAS statements express the workstation capacity constraints by using a set of linear constraints for each workstation. A single GCC constraint expresses the demand constraints for each car class. An element constraint for each option variable expresses the relationships between slot variables and option variables.

Finally, a set of redundant constraints are introduced to improve the efficiency of propagation. The idea behind the redundant constraint in this model is the following realization: if the workstation for option j has capacity r out of s, then at most r cars in the sequence can have option j, where n is the total number of cars. Consequently, at least cars in the sequence must have option j, where is the number of cars that have option j. Generalizing this further, at least cars in the sequence must have option j, .

 %macro car_sequencing(outdata);

 proc clp out=&outdata varselect=minrmaxc findall;

    /* Declare Variables */
    var
       /* Slot variables: Si - class of car assigned to Slot i */
       %do i = 1 %to &Ncars;
           S_&i = [1, &Nclss]
       %end;

       /* Option variables: Oij
          - indicates if class assigned to Sloti needs Option j */
       %do i = 1 %to &Ncars;
           %do j = 1 %to &Nops;
               O_&i._&j = [0, 1]
           %end;
       %end;
       ;

    /* Capacity Constraints: for each option j */
    /* Installed in at most Max_j cars out of every sequence of BlSz_j cars */
    %do j = 1 %to &Nops;
       %do i = 0 %to %eval(&Ncars-&&BlSz_&j);
          lincon 0
          %do k=1 %to &&BlSz_&j;
             + O_%eval(&i+&k)_&j
          %end;
          <=&&Max_&j;
       %end;
    %end;

    /* Demand Constraints: for each class i */
    /* Exactly cars_cls_i cars */
    gcc (S_1-S_&Ncars) = (
       %do i = 1 %to &Nclss;
          (&&class_&i, &&cars_cls_&i, &&cars_cls_&i)
       %end;
       );

    /* Element Constraints: For each slot i and each option j */
    /* relate the slot variable to the option variables.      */
    /*  O_i_j is the S_i th element in list_j.                */
    %do i = 1 %to &Ncars;
       %do j = 1 %to &Nops;
          element (S_&i, (&&list_&j), O_&i._&j);
       %end;
    %end;


    /* Redundant Constraints to improve efficiency - for every  */
    /*    option j.                                             */
    /* At most &&Max_&j out of every sequence of &&BlSz_&j cars */
    /*    requires option j.                                    */
    /* All the other slots contain at least cars_opt_j - Max_j  */
    /*    cars with option j                                    */
    %do j = 1 %to &Nops;
       %do i = 1 %to %eval(&Ncars/&&BlSz_&j);
          lincon 0
          %do k=1 %to %eval(&Ncars-&i*&&BlSz_&j);
             + O_&k._&j
          %end;
          >= %eval(&&cars_opts_&j-&i*&&Max_&j);
       %end;
    %end;
 run;

 %mend;
 %car_sequencing(mycas.sequence_out);

This problem has six solutions, as shown in Output 4.4.1.

Output 4.4.1: Car Sequencing

Although constraints can usually help performance, this is not necessarily always the case. Consider the instance shown in Table 8 with 100 cars, 5 options, and 18 classes from Dincbas, Simonis, and Van Hentenryck (1988).

Using the same formulation as before, the CLP procedure was unable to find a solution in 10 seconds. However, removing the redundant constraints resulted in a solution being found almost immediately.

Two different views of the solution that was found are shown in Output 4.4.2 and Output 4.4.3. The horizontal axis in each chart represents the assembly sequence. The assembly sequence by class is shown in Output 4.4.2.

Output 4.4.2: Car Sequencing by Class

The assembly sequence by option is shown in Output 4.4.3. You can use this chart to quickly verify that the capacity constraints are satisfied. For example, from the corresponding block patterns in each row, it is evident that option 1 is never processed on consecutive cars, option 2 is never processed on three consecutive cars, and so on.

Output 4.4.3: Car Sequencing by Option

Finally, the two solution summaries shown in Output 4.4.4 and Output 4.4.5 contrast the number of solutions that are found in two different modes in the same time period, using the FINDALL option.