Resources

The Car Sequencing Problem (clp7)

/***************************************************************/
/*                                                             */
/*          S A S   S A M P L E   L I B R A R Y                */
/*                                                             */
/*    NAME: clp7                                               */
/*   TITLE: The Car Sequencing Problem (clp7)                  */
/* PRODUCT: OR                                                 */
/*  SYSTEM: ALL                                                */
/*    KEYS: OR                                                 */
/*   PROCS: CLP, GANTT, SQL                                    */
/*    DATA:                                                    */
/*                                                             */
/* SUPPORT:                             UPDATE:                */
/*     REF:                                                    */
/*    MISC: Example 7 from the CLP Procedure chapter of the    */
/*          Constraint Programming book.                       */
/*                                                             */
/***************************************************************/


/*

First line: number of cars; number of options; number of classes.

Second line: for each option, the maximum number of cars with that
   option in a block.

Third line: for each option, the block size to which the maximum
   number refers.

Then for each class: index no.; no. of cars in this class; for each
   option, whether or not this class requires it (1 or 0).

*/


data input;
   input col1 col2 col3 col4 col5 col6 col7;
   datalines;
10 5 6 . . . .
1 2 1 2 1 . .
2 3 3 5 5 . .
0 1 1 0 1 1 0
1 1 0 0 0 1 0
2 2 0 1 0 0 1
3 2 0 1 0 1 0
4 2 1 0 1 0 0
5 2 1 1 0 0 0
;
run;

 %macro car_sequencing_data(indata);

 %global
     Ncars   /* number of cars     */
     Nops    /* number of options  */
     Nclss;  /* number of classes  */

 /* Read input data set */
 data _null_;
    set &indata;
    if _n_=1 then do;
       call symput('Ncars', strip(put(col1,best.)));
       call symput('Nops', strip(put(col2,best.)));
       call symput('Nclss', strip(put(col3,best.)));
    end;
 run;

 %do i = 1 %to &Nops;
    %global
       Max_&i        /* Maximum number of cars with option &i in a  */
                     /*   block of size BlSz_i                      */
       BlSz_&i       /* For option &i, the block size corresponding */
                     /*   to Max_i                                  */
       list_&i       /* class indicator list for option &i          */
       cars_opts_&i; /* Number of cars requiring option &i          */
 %end;

 %do i = 1 %to &Nclss;
    %global
       class_&i      /* class index number of class &i */
       cars_cls_&i;  /* number of cars in class &i     */
 %end;

 data _null_;
    set &indata;
    if _n_=2 then do;
       %do i = 1 %to &Nops;
          call symput("Max_&i", put(col&i,best.));
       %end;
    end;

    if _n_=3 then do;
       %do i = 1 %to &Nops;
          call symput("BlSz_&i", put(col&i,best.));
       %end;
    end;

    if _n_>=4 then do;
       call symput("class_"||strip(put(_n_-3,best.)), put(col1+1,best.));
       call symput("cars_cls_"||strip(put(_n_-3,best.)), put(col2,best.));
       %do i = 1 %to &Nops;
          call symput("cars_opts_&i", put(col2*col%eval(&i+2),best.) );
       %end;
    end;
 run;

 /* Create list of columns to generate option lists. */
 data input1;
    set &indata;
    if _n_<=3 then delete;
 run;

 proc sql noprint;
    %do i=1 %to &Nops;
       select col%eval(&i+2) into :list_&i separated by "," from input1;
       select sum( col2 * col%eval(&i+2) ) into: cars_opts_&i from input1;
    %end;
 quit;

%mend car_sequencing_data;
%car_sequencing_data(input);



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



%macro car_sequencing_gantt;

/* map classes to colors */
%let class1 = red;
%let class2 = blue;
%let class3 = gray;
%let class4 = blue;
%let class5 = cyan;
%let class6 = yellow;

/* set patterns */
%do i=1 %to 6;
    pattern&i. v=s color=&&class&i.;
%end;

proc sort data=sequence_out;
   by
   %do j = 1 %to 10;
      S_&j
   %end;
   ;
run;

data carseq_ds(keep=S_1-S_10);
   set sequence_out;
run;

proc format;
   value stage
      0.5 = '1'
      9.5 = '10'
      10.5 = ' '
      ;
run;

data schedule;
   format _label $8.;
   format s_start stage.;
   label solution='Solution';
   set carseq_ds;
   keep _pattern _label segmt_no solution s_start s_finish;
   retain solution 1;
   %do i = 1 %to 10;
      s_start=%eval(&i-1)+0.5;
      s_finish=&i+0.5;
      segmt_no = &i;
      nextpat = 0; /* ensure no match */
      %do j = 1 %to 6;
         if S_&i eq &j then do;
            _label = "Class %eval(&j)";
            _pattern = &j;
         end;
         if S_&i eq %eval(&j+1) then do;
            nextpat = &j;
         end;
      %end;
      if mod(nextpat - _pattern,4) ne 0 then do;
         s_finish = s_finish - 0.05;
      end;
      output;
   %end;
   solution = solution + 1;
run;

data labels;
   _y=-1;
   _lvar="_label";
   _xvar="s_start";
   _hlabel=1.0;
   _yoffset = -0.6;
   _xoffset = 0.25;
run;
goptions htext=1.5;
title1 j=c h=5pct 'Car Sequencing Problem';
title2 j=c h=3pct 'Assembly Sequence for All Six Solutions';
proc gantt data=schedule labdata=labels;
   chart /
      pcompress
      skip=3
      nojobnum
      nolegend
      mindate=0.5
      useformat
      labsplit='/'
      increment=1
      barht=2
      baroff=0.8
      ;
   id solution;
run;

%mend car_sequencing_gantt;
%car_sequencing_gantt;