Resources

The Car Sequencing Problem (oclpe07)

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

data class_data;
   input class cars_cls;
   datalines;
1 1
2 1
3 2
4 2
5 2
6 2
;

data option_data;
   input option max blSz class1-class6;
   datalines;
1 1 2 1 0 0 0 1 1
2 2 3 0 0 1 1 0 1
3 1 3 1 0 0 0 1 0
4 2 5 1 1 0 1 0 0
5 1 5 0 0 1 0 0 0
;

%macro car_sequencing(outdata);
   proc optmodel;
      set CLASSES;
      num nClasses = card(CLASSES);
      num cars_cls {CLASSES};
      read data class_data into CLASSES=[class] cars_cls;

      set OPTIONS;
      num max {OPTIONS};
      num blSz {OPTIONS};
      num list {OPTIONS, CLASSES};
      num cars_opt {i in OPTIONS} = sum {k in CLASSES} cars_cls[k] * list[i,k];
      read data option_data into OPTIONS=[option] max blSz
         {k in CLASSES} <list[option,k]=col('class'||k)>;

      num nCars = sum {k in CLASSES} cars_cls[k];
      set SLOTS = 1..nCars;

      /* Declare Variables */
      /* Slot variables: S[i] - class of car assigned to Slot i */
      var S {SLOTS} integer >= 1 <= nClasses;

      /* Option variables: O[i,j]
      - indicates if class assigned to Slot i needs Option j */
      var O {SLOTS, OPTIONS} binary;

      /* Capacity Constraints: for each option j */
      /* Install in at most max[j] out of every sequence of blSz[j] cars */
      con CapacityCon {j in OPTIONS, i in 0..(nCars-blSz[j])}:
         sum {k in 1..blSz[j]} O[i+k,j] <= max[j];

      /* Demand Constraints: for each class k */
      /* Exactly cars_cls[k] cars */
      con MeetDemandCon:
         gcc(S, setof{k in CLASSES} <k,cars_cls[k],cars_cls[k]>);

      /* Element Constraints: For each slot i and each option j */
      /* relate the slot variable to the option variables.      */
      /* O[i,j] = list[j,S[i]]                                  */
      con OptionsAtSlotCon {i in SLOTS, j in OPTIONS}:
         element(S[i], {k in CLASSES} list[j,k], O[i,j]);

      /* 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                                    */
      con BoundRemainingCon {j in OPTIONS, i in 1..(nCars/blSz[j])}:
         sum {k in 1..(nCars-i*blSz[j])} O[k,j] >= cars_opt[j] - i * max[j];

      solve with CLP / varselect=minrmaxc findall;

      /* Replicate typical PROC CLP output from PROC OPTMODEL arrays */
      create data &outdata.(drop=sol) from [sol]=(1.._NSOL_)
         {i in SLOTS} <col('S_'||i)=S[i].sol[sol]>
         {i in SLOTS, j in OPTIONS} <col('O_'||i||'_'||j)=O[i,j].sol[sol]>;
   quit;
%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;