Example 3.7 Car Sequencing Problem

This problem 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 where each car is customized with a specific set of options such as air-conditioning, sunroof, navigation, and so on. The assembly line moves through several workstations for installation of these options. The cars cannot be positioned randomly since each of these workstations have limited capacity and need time to set up the options as the assembly line is moving in front of the station. These capacity constraints are formalized using constraints of the form out of , which indicates that the workstation can install the option on out of every sequence of 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 3.9.

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 instance data for this problem is used to create a SAS data set, which in turn is processed to generate the SAS macro variables shown in Table 3.10 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 3.11.

In the following SAS statments, the workstation capacity constraints are expressed using a set of linear constraints for each workstation. The demand constraints for each car class are expressed using a single GCC constraint. The relationships between slot variables and option variables are expressed using an element constraint for each option variable. Finally, a set of redundant constraints are introduced to improve the efficiency of propagation. The idea behind the redundant constraint is the following realization: if the workstation for option has capacity out of , then at most cars in the sequence can have option where is the total number of cars. Consequently at least cars in the sequence must have option , where is the number of cars with option . Generalizing this further, at least cars in the sequence must have option , .

 %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(sequence_out);
 

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

Output 3.7.1 Car Sequencing